abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
absRpm.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [absRpm.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Abstraction package.]
8 
9  Synopsis [Structural reparameterization.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: absRpm.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "abs.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 ////////////////////////////////////////////////////////////////////////
26 /// DECLARATIONS ///
27 ////////////////////////////////////////////////////////////////////////
28 
29 static inline int Gia_ObjDom( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Vec_IntEntry(p->vDoms, Gia_ObjId(p, pObj)); }
30 static inline void Gia_ObjSetDom( Gia_Man_t * p, Gia_Obj_t * pObj, int d ) { Vec_IntWriteEntry(p->vDoms, Gia_ObjId(p, pObj), d); }
31 
32 static int Abs_ManSupport2( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp );
33 static int Abs_GiaObjDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode );
34 static int Abs_GiaObjRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode );
35 
36 ////////////////////////////////////////////////////////////////////////
37 /// FUNCTION DEFINITIONS ///
38 ////////////////////////////////////////////////////////////////////////
39 
40 /**Function*************************************************************
41 
42  Synopsis [Computes one-node dominators.]
43 
44  Description [For each node, computes the closest one-node dominator,
45  which can be the node itself if the node has no other dominators.]
46 
47  SideEffects []
48 
49  SeeAlso []
50 
51 ***********************************************************************/
52 void Gia_ManAddDom( Gia_Man_t * p, Gia_Obj_t * pObj, int iDom0 )
53 {
54  int iDom1, iDomNext;
55  if ( Gia_ObjDom(p, pObj) == -1 )
56  {
57  Gia_ObjSetDom( p, pObj, iDom0 );
58  return;
59  }
60  iDom1 = Gia_ObjDom( p, pObj );
61  while ( 1 )
62  {
63  if ( iDom0 > iDom1 )
64  {
65  iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom1) );
66  if ( iDomNext == iDom1 )
67  break;
68  iDom1 = iDomNext;
69  continue;
70  }
71  if ( iDom1 > iDom0 )
72  {
73  iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom0) );
74  if ( iDomNext == iDom0 )
75  break;
76  iDom0 = iDomNext;
77  continue;
78  }
79  assert( iDom0 == iDom1 );
80  Gia_ObjSetDom( p, pObj, iDom0 );
81  return;
82  }
83  Gia_ObjSetDom( p, pObj, Gia_ObjId(p, pObj) );
84 }
85 void Gia_ManComputeDoms( Gia_Man_t * p )
86 {
87  Gia_Obj_t * pObj;
88  int i;
89  if ( p->vDoms == NULL )
90  p->vDoms = Vec_IntAlloc( 0 );
91  Vec_IntFill( p->vDoms, Gia_ManObjNum(p), -1 );
92  Gia_ManForEachObjReverse( p, pObj, i )
93  {
94  if ( i == 0 || Gia_ObjIsCi(pObj) )
95  continue;
96  if ( pObj->fMark1 || (p->pRefs && Gia_ObjIsAnd(pObj) && Gia_ObjRefNum(p, pObj) == 0) )
97  continue;
98  if ( Gia_ObjIsCo(pObj) )
99  {
100  Gia_ObjSetDom( p, pObj, i );
101  Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
102  continue;
103  }
104  assert( Gia_ObjIsAnd(pObj) );
105  Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
106  Gia_ManAddDom( p, Gia_ObjFanin1(pObj), i );
107  }
108 }
109 void Gia_ManTestDoms2( Gia_Man_t * p )
110 {
111  Vec_Int_t * vNodes;
112  Gia_Obj_t * pObj, * pDom;
113  abctime clk = Abc_Clock();
114  int i;
115  assert( p->vDoms == NULL );
116  Gia_ManComputeDoms( p );
117 /*
118  Gia_ManForEachPi( p, pObj, i )
119  if ( Gia_ObjId(p, pObj) != Gia_ObjDom(p, pObj) )
120  printf( "PI =%6d Id =%8d. Dom =%8d.\n", i, Gia_ObjId(p, pObj), Gia_ObjDom(p, pObj) );
121 */
122  Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
123  // for each dominated PI, when if the PIs is in a leaf of the MFFC of the dominator
124  Gia_ManCleanMark1( p );
125  Gia_ManForEachPi( p, pObj, i )
126  pObj->fMark1 = 1;
127  vNodes = Vec_IntAlloc( 100 );
128  Gia_ManCreateRefs( p );
129  Gia_ManForEachPi( p, pObj, i )
130  {
131  if ( Gia_ObjId(p, pObj) == Gia_ObjDom(p, pObj) )
132  continue;
133 
134  pDom = Gia_ManObj(p, Gia_ObjDom(p, pObj));
135  if ( Gia_ObjIsCo(pDom) )
136  {
137  assert( Gia_ObjFanin0(pDom) == pObj );
138  continue;
139  }
140  assert( Gia_ObjIsAnd(pDom) );
141  Abs_GiaObjDeref_rec( p, pDom );
142  Abs_ManSupport2( p, pDom, vNodes );
143  Abs_GiaObjRef_rec( p, pDom );
144 
145  if ( Vec_IntFind(vNodes, Gia_ObjId(p, pObj)) == -1 )
146  printf( "FAILURE.\n" );
147 // else
148 // printf( "Success.\n" );
149  }
150  Vec_IntFree( vNodes );
151  Gia_ManCleanMark1( p );
152 }
153 
154 /**Function*************************************************************
155 
156  Synopsis [Collect PI doms.]
157 
158  Description [Assumes that some PIs and ANDs are marked with fMark1.]
159 
160  SideEffects []
161 
162  SeeAlso []
163 
164 ***********************************************************************/
165 Vec_Int_t * Gia_ManCollectDoms( Gia_Man_t * p )
166 {
167  Vec_Int_t * vNodes;
168  Gia_Obj_t * pObj;
169  int Lev, LevMax = ABC_INFINITY;
170  int i, iDom, iDomNext;
171  vNodes = Vec_IntAlloc( 100 );
172  Gia_ManForEachObj( p, pObj, i )
173  {
174  if ( !pObj->fMark1 )
175  continue;
176  if ( p->pRefs && Gia_ObjRefNum(p, pObj) == 0 )
177  continue;
178  iDom = Gia_ObjDom(p, pObj);
179  if ( iDom == -1 )
180  continue;
181  if ( iDom == i )
182  continue;
183  for ( Lev = 0; Lev < LevMax && Gia_ObjIsAnd( Gia_ManObj(p, iDom) ); Lev++ )
184  {
185  Vec_IntPush( vNodes, iDom );
186  iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom) );
187  if ( iDomNext == iDom )
188  break;
189  iDom = iDomNext;
190  }
191  }
192  Vec_IntUniqify( vNodes );
193  return vNodes;
194 }
195 Vec_Int_t * Gia_ManComputePiDoms( Gia_Man_t * p )
196 {
197  Vec_Int_t * vNodes;
198  Gia_ManComputeDoms( p );
199  vNodes = Gia_ManCollectDoms( p );
200 // Vec_IntPrint( vNodes );
201  return vNodes;
202 }
203 void Gia_ManTestDoms( Gia_Man_t * p )
204 {
205  Vec_Int_t * vNodes;
206  Gia_Obj_t * pObj;
207  int i;
208  // mark PIs
209 // Gia_ManCreateRefs( p );
210  Gia_ManCleanMark1( p );
211  Gia_ManForEachPi( p, pObj, i )
212  pObj->fMark1 = 1;
213  // compute dominators
214  assert( p->vDoms == NULL );
215  vNodes = Gia_ManComputePiDoms( p );
216 // printf( "Nodes = %d. Doms = %d.\n", Gia_ManAndNum(p), Vec_IntSize(vNodes) );
217  Vec_IntFree( vNodes );
218  // unmark PIs
219  Gia_ManCleanMark1( p );
220 }
221 
222 
223 /**Function*************************************************************
224 
225  Synopsis [Counts flops without fanout.]
226 
227  Description []
228 
229  SideEffects []
230 
231  SeeAlso []
232 
233 ***********************************************************************/
234 void Gia_ManCountFanoutlessFlops( Gia_Man_t * p )
235 {
236  Gia_Obj_t * pObj;
237  int i;
238  int Counter = 0;
239  Gia_ManCreateRefs( p );
240  Gia_ManForEachRo( p, pObj, i )
241  if ( Gia_ObjRefNum(p, pObj) == 0 )
242  Counter++;
243  printf( "Fanoutless flops = %d.\n", Counter );
244  ABC_FREE( p->pRefs );
245 }
246 
247 /**Function*************************************************************
248 
249  Synopsis []
250 
251  Description []
252 
253  SideEffects []
254 
255  SeeAlso []
256 
257 ***********************************************************************/
258 void Gia_ManCountPisNodes_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vPis, Vec_Int_t * vAnds )
259 {
260  if ( Gia_ObjIsTravIdCurrent(p, pObj) )
261  return;
262  Gia_ObjSetTravIdCurrent(p, pObj);
263  if ( pObj->fMark1 )
264  {
265  Vec_IntPush( vPis, Gia_ObjId(p, pObj) );
266  return;
267  }
268  assert( Gia_ObjIsAnd(pObj) );
269  Gia_ManCountPisNodes_rec( p, Gia_ObjFanin0(pObj), vPis, vAnds );
270  Gia_ManCountPisNodes_rec( p, Gia_ObjFanin1(pObj), vPis, vAnds );
271  Vec_IntPush( vAnds, Gia_ObjId(p, pObj) );
272 }
273 void Gia_ManCountPisNodes( Gia_Man_t * p, Vec_Int_t * vPis, Vec_Int_t * vAnds )
274 {
275  Gia_Obj_t * pObj;
276  int i;
277  // mark const0 and flop output
278  Gia_ManIncrementTravId( p );
279  Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
280  Gia_ManForEachRo( p, pObj, i )
281  Gia_ObjSetTravIdCurrent( p, pObj );
282  // count PIs and internal nodes reachable from COs
283  Vec_IntClear( vPis );
284  Vec_IntClear( vAnds );
285  Gia_ManForEachCo( p, pObj, i )
286  Gia_ManCountPisNodes_rec( p, Gia_ObjFanin0(pObj), vPis, vAnds );
287 }
288 
289 /**Function*************************************************************
290 
291  Synopsis []
292 
293  Description []
294 
295  SideEffects []
296 
297  SeeAlso []
298 
299 ***********************************************************************/
300 int Abs_GiaObjDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
301 {
302  Gia_Obj_t * pFanin;
303  int Counter = 0;
304  if ( pNode->fMark1 || Gia_ObjIsRo(p, pNode) )
305  return 0;
306  assert( Gia_ObjIsAnd(pNode) );
307  pFanin = Gia_ObjFanin0(pNode);
308  assert( Gia_ObjRefNum(p, pFanin) > 0 );
309  if ( Gia_ObjRefDec(p, pFanin) == 0 )
310  Counter += Abs_GiaObjDeref_rec( p, pFanin );
311  pFanin = Gia_ObjFanin1(pNode);
312  assert( Gia_ObjRefNum(p, pFanin) > 0 );
313  if ( Gia_ObjRefDec(p, pFanin) == 0 )
314  Counter += Abs_GiaObjDeref_rec( p, pFanin );
315  return Counter + 1;
316 }
317 int Abs_GiaObjRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
318 {
319  Gia_Obj_t * pFanin;
320  int Counter = 0;
321  if ( pNode->fMark1 || Gia_ObjIsRo(p, pNode) )
322  return 0;
323  assert( Gia_ObjIsAnd(pNode) );
324  pFanin = Gia_ObjFanin0(pNode);
325  if ( Gia_ObjRefInc(p, pFanin) == 0 )
326  Counter += Abs_GiaObjRef_rec( p, pFanin );
327  pFanin = Gia_ObjFanin1(pNode);
328  if ( Gia_ObjRefInc(p, pFanin) == 0 )
329  Counter += Abs_GiaObjRef_rec( p, pFanin );
330  return Counter + 1;
331 }
332 
333 /**Function*************************************************************
334 
335  Synopsis [Returns the number of nodes with zero refs.]
336 
337  Description []
338 
339  SideEffects []
340 
341  SeeAlso []
342 
343 ***********************************************************************/
344 int Abs_GiaSortNodes( Gia_Man_t * p, Vec_Int_t * vSupp )
345 {
346  Gia_Obj_t * pObj;
347  int nSize = Vec_IntSize(vSupp);
348  int i, RetValue;
349  Gia_ManForEachObjVec( vSupp, p, pObj, i )
350  if ( i < nSize && Gia_ObjRefNum(p, pObj) == 0 && !Gia_ObjIsRo(p, pObj) ) // add removable leaves
351  {
352  assert( pObj->fMark1 );
353  Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
354  }
355  RetValue = Vec_IntSize(vSupp) - nSize;
356  Gia_ManForEachObjVec( vSupp, p, pObj, i )
357  if ( i < nSize && !(Gia_ObjRefNum(p, pObj) == 0 && !Gia_ObjIsRo(p, pObj)) ) // add non-removable leaves
358  Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
359  assert( Vec_IntSize(vSupp) == 2 * nSize );
360  memmove( Vec_IntArray(vSupp), Vec_IntArray(vSupp) + nSize, sizeof(int) * nSize );
361  Vec_IntShrink( vSupp, nSize );
362  return RetValue;
363 }
364 
365 
366 /**Function*************************************************************
367 
368  Synopsis [Computes support in terms of PIs and flops.]
369 
370  Description []
371 
372  SideEffects []
373 
374  SeeAlso []
375 
376 ***********************************************************************/
377 void Abs_ManSupport1_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
378 {
379  if ( Gia_ObjIsTravIdCurrent(p, pObj) )
380  return;
381  Gia_ObjSetTravIdCurrent(p, pObj);
382  if ( pObj->fMark1 || Gia_ObjIsRo(p, pObj) )
383  {
384  Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
385  return;
386  }
387  assert( Gia_ObjIsAnd(pObj) );
388  Abs_ManSupport1_rec( p, Gia_ObjFanin0(pObj), vSupp );
389  Abs_ManSupport1_rec( p, Gia_ObjFanin1(pObj), vSupp );
390 }
391 int Abs_ManSupport1( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
392 {
393  assert( Gia_ObjIsAnd(pObj) );
394  Vec_IntClear( vSupp );
395  Gia_ManIncrementTravId( p );
396  Abs_ManSupport1_rec( p, pObj, vSupp );
397  return Vec_IntSize(vSupp);
398 }
399 
400 /**Function*************************************************************
401 
402  Synopsis [Computes support of the MFFC.]
403 
404  Description [Should be called when pObj's cone is dereferenced.]
405 
406  SideEffects []
407 
408  SeeAlso []
409 
410 ***********************************************************************/
411 void Abs_ManSupport2_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
412 {
413  if ( Gia_ObjIsTravIdCurrent(p, pObj) )
414  return;
415  Gia_ObjSetTravIdCurrent(p, pObj);
416  if ( pObj->fMark1 || Gia_ObjIsRo(p, pObj) || Gia_ObjRefNum(p, pObj) > 0 )
417  {
418  Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
419  return;
420  }
421  assert( Gia_ObjIsAnd(pObj) );
422  Abs_ManSupport2_rec( p, Gia_ObjFanin0(pObj), vSupp );
423  Abs_ManSupport2_rec( p, Gia_ObjFanin1(pObj), vSupp );
424 }
425 int Abs_ManSupport2( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
426 {
427  assert( Gia_ObjIsAnd(pObj) );
428  Vec_IntClear( vSupp );
429  Gia_ManIncrementTravId( p );
430  Abs_ManSupport2_rec( p, Gia_ObjFanin0(pObj), vSupp );
431  Abs_ManSupport2_rec( p, Gia_ObjFanin1(pObj), vSupp );
432  Gia_ObjSetTravIdCurrent(p, pObj);
433  return Vec_IntSize(vSupp);
434 }
435 
436 /**Function*************************************************************
437 
438  Synopsis [Computes support of the extended MFFC.]
439 
440  Description []
441 
442  SideEffects []
443 
444  SeeAlso []
445 
446 ***********************************************************************/
447 int Abs_ManSupport3( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
448 {
449  Gia_Obj_t * pTemp, * pFan0, * pFan1;
450  int i, nSize0;
451  // collect MFFC
452  Abs_ManSupport2( p, pObj, vSupp );
453  // move dominated to the front
454  nSize0 = Abs_GiaSortNodes( p, vSupp );
455  assert( nSize0 > 0 );
456  // consider remaining nodes
457  while ( 1 )
458  {
459  int fChanges = 0;
460  Gia_ManForEachObjVec( vSupp, p, pTemp, i )
461  {
462  if ( i < nSize0 )
463  continue;
464  if ( !Gia_ObjIsAnd(pTemp) )
465  continue;
466  assert( !pTemp->fMark1 );
467  assert( Gia_ObjRefNum(p, pTemp) > 0 );
468  pFan0 = Gia_ObjFanin0(pTemp);
469  pFan1 = Gia_ObjFanin1(pTemp);
470  if ( Gia_ObjIsTravIdCurrent(p, pFan0) && Gia_ObjIsTravIdCurrent(p, pFan1) )
471  {
472  Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
473  fChanges = 1;
474  break;
475  }
476  if ( Gia_ObjIsTravIdCurrent(p, pFan0) )
477  {
478  Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
479  Vec_IntPush( vSupp, Gia_ObjId(p, pFan1) );
480  assert( !Gia_ObjIsTravIdCurrent(p, pFan1) );
481  Gia_ObjSetTravIdCurrent(p, pFan1);
482  fChanges = 1;
483  break;
484  }
485  if ( Gia_ObjIsTravIdCurrent(p, pFan1) )
486  {
487  Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
488  Vec_IntPush( vSupp, Gia_ObjId(p, pFan0) );
489  assert( !Gia_ObjIsTravIdCurrent(p, pFan0) );
490  Gia_ObjSetTravIdCurrent(p, pFan0);
491  fChanges = 1;
492  break;
493  }
494  }
495  if ( !fChanges )
496  break;
497  }
498  return Vec_IntSize(vSupp);
499 }
500 
501 
502 /**Function*************************************************************
503 
504  Synopsis []
505 
506  Description []
507 
508  SideEffects []
509 
510  SeeAlso []
511 
512 ***********************************************************************/
513 int Abs_GiaCofPrint( word * pTruth, int nSize, int nSize0, int Res )
514 {
515  int i, Bit;
516  int nBits = (1 << nSize);
517  int nStep = (1 << nSize0);
518  int Mark[2] = {1,1};
519  for ( i = 0; i < nBits; i++ )
520  {
521  if ( i % nStep == 0 )
522  {
523  printf( " " );
524  assert( Res || (Mark[0] && Mark[1]) );
525  Mark[0] = Mark[1] = 0;
526  }
527  Bit = Abc_InfoHasBit((unsigned *)pTruth, i);
528  Mark[Bit] = 1;
529  printf( "%d", Bit );
530  }
531  printf( "\n" );
532  assert( Res || (Mark[0] && Mark[1]) );
533  return 1;
534 }
535 
536 /**Function*************************************************************
537 
538  Synopsis [Returns 1 if truth table has no const cofactors.]
539 
540  Description [The cofactoring variables are the (nSize-nSize0)
541  most significant vars. Each cofactor depends on nSize0 vars.]
542 
543  SideEffects []
544 
545  SeeAlso []
546 
547 ***********************************************************************/
548 int Abs_GiaCheckTruth( word * pTruth, int nSize, int nSize0 )
549 {
550  unsigned char * pStr = (unsigned char *)pTruth;
551  int nStr = (nSize >= 3 ? (1 << (nSize - 3)) : 1);
552  int i, k, nSteps;
553  assert( nSize0 > 0 && nSize0 <= nSize );
554  if ( nSize0 == 1 )
555  {
556  for ( i = 0; i < nStr; i++ )
557  if ( (((unsigned)pStr[i] ^ ((unsigned)pStr[i] >> 1)) & 0x55) != 0x55 )
558  return 0;
559  return 1;
560  }
561  if ( nSize0 == 2 )
562  {
563  for ( i = 0; i < nStr; i++ )
564  if ( ((unsigned)pStr[i] & 0xF) == 0x0 || (((unsigned)pStr[i] >> 4) & 0xF) == 0x0 ||
565  ((unsigned)pStr[i] & 0xF) == 0xF || (((unsigned)pStr[i] >> 4) & 0xF) == 0xF )
566  return 0;
567  return 1;
568  }
569  assert( nSize0 >= 3 );
570  nSteps = (1 << (nSize0 - 3));
571  for ( i = 0; i < nStr; i += nSteps )
572  {
573  for ( k = 0; k < nSteps; k++ )
574  if ( ((unsigned)pStr[i+k] & 0xFF) != 0x00 )
575  break;
576  if ( k == nSteps )
577  break;
578  for ( k = 0; k < nSteps; k++ )
579  if ( ((unsigned)pStr[i+k] & 0xFF) != 0xFF )
580  break;
581  if ( k == nSteps )
582  break;
583  }
584  assert( i <= nStr );
585  return (int)( i == nStr );
586 }
587 
588 /**Function*************************************************************
589 
590  Synopsis [Returns 1 if truth table has const cofactors.]
591 
592  Description []
593 
594  SideEffects []
595 
596  SeeAlso []
597 
598 ***********************************************************************/
599 void Abs_RpmPerformMark( Gia_Man_t * p, int nCutMax, int fVerbose, int fVeryVerbose )
600 {
601  Vec_Int_t * vPis, * vAnds, * vDoms;
602  Vec_Int_t * vSupp, * vSupp1, * vSupp2;
603  Gia_Obj_t * pObj;
604  word * pTruth;
605  int Iter, i, nSize0, nNodes;
606  int fHasConst, fChanges = 1;
607  Gia_ManCreateRefs( p );
608  Gia_ManCleanMark1( p );
609  Gia_ManForEachPi( p, pObj, i )
610  pObj->fMark1 = 1;
611  vPis = Vec_IntAlloc( 100 );
612  vAnds = Vec_IntAlloc( 100 );
613  vSupp1 = Vec_IntAlloc( 100 );
614  vSupp2 = Vec_IntAlloc( 100 );
615  for ( Iter = 0; fChanges; Iter++ )
616  {
617  fChanges = 0;
618  vDoms = Gia_ManComputePiDoms( p );
619  // count the number of PIs and internal nodes
620  if ( fVerbose || fVeryVerbose )
621  {
622  Gia_ManCountPisNodes( p, vPis, vAnds );
623  printf( "Iter %3d : ", Iter );
624  printf( "PI = %5d (%6.2f %%) ", Vec_IntSize(vPis), 100.0 * Vec_IntSize(vPis) / Gia_ManPiNum(p) );
625  printf( "And = %6d (%6.2f %%) ", Vec_IntSize(vAnds), 100.0 * Vec_IntSize(vAnds) / Gia_ManAndNum(p) );
626  printf( "Dom = %5d (%6.2f %%) ", Vec_IntSize(vDoms), 100.0 * Vec_IntSize(vDoms) / Gia_ManAndNum(p) );
627  printf( "\n" );
628  }
629 // pObj = Gia_ObjFanin0( Gia_ManPo(p, 1) );
630  Gia_ManForEachObjVec( vDoms, p, pObj, i )
631  {
632  assert( !pObj->fMark1 );
633  assert( Gia_ObjRefNum( p, pObj ) > 0 );
634  // dereference root node
635  nNodes = Abs_GiaObjDeref_rec( p, pObj );
636 /*
637  // compute support of full cone
638  if ( Abs_ManSupport1(p, pObj, vSupp1) > nCutMax )
639 // if ( 1 )
640  {
641  // check support of MFFC
642  if ( Abs_ManSupport2(p, pObj, vSupp2) > nCutMax )
643 // if ( 1 )
644  {
645  Abs_GiaObjRef_rec( p, pObj );
646  continue;
647  }
648  vSupp = vSupp2;
649 // printf( "-" );
650  }
651  else
652  {
653  vSupp = vSupp1;
654 // printf( "+" );
655  }
656 */
657  if ( Abs_ManSupport2(p, pObj, vSupp2) > nCutMax )
658  {
659  Abs_GiaObjRef_rec( p, pObj );
660  continue;
661  }
662  vSupp = vSupp2;
663 
664  // order nodes by their ref counts
665  nSize0 = Abs_GiaSortNodes( p, vSupp );
666  assert( nSize0 > 0 && nSize0 <= nCutMax );
667  // check if truth table has const cofs
668  pTruth = Gia_ObjComputeTruthTableCut( p, pObj, vSupp );
669  if ( pTruth == NULL )
670  {
671  Abs_GiaObjRef_rec( p, pObj );
672  continue;
673  }
674  fHasConst = !Abs_GiaCheckTruth( pTruth, Vec_IntSize(vSupp), nSize0 );
675  if ( fVeryVerbose )
676  {
677  printf( "Nodes =%3d ", nNodes );
678  printf( "Size =%3d ", Vec_IntSize(vSupp) );
679  printf( "Size0 =%3d ", nSize0 );
680  printf( "%3s", fHasConst ? "yes" : "no" );
681  Abs_GiaCofPrint( pTruth, Vec_IntSize(vSupp), nSize0, fHasConst );
682  }
683  if ( fHasConst )
684  {
685  Abs_GiaObjRef_rec( p, pObj );
686  continue;
687  }
688  // pObj can be reparamed
689  pObj->fMark1 = 1;
690  fChanges = 1;
691  }
692  Vec_IntFree( vDoms );
693  }
694  // count the number of PIs and internal nodes
695  if ( fVeryVerbose )
696  {
697  Gia_ManCountPisNodes( p, vPis, vAnds );
698  printf( "Iter %3d : ", Iter );
699  printf( "PI = %5d (%6.2f %%) ", Vec_IntSize(vPis), 100.0 * Vec_IntSize(vPis) / Gia_ManPiNum(p) );
700  printf( "And = %6d (%6.2f %%) ", Vec_IntSize(vAnds), 100.0 * Vec_IntSize(vAnds) / Gia_ManAndNum(p) );
701 // printf( "Dom = %5d (%6.2f %%) ", Vec_IntSize(vDoms), 100.0 * Vec_IntSize(vDoms) / Gia_ManAndNum(p) );
702  printf( "\n" );
703  }
704  // cleanup
705  Vec_IntFree( vPis );
706  Vec_IntFree( vAnds );
707  Vec_IntFree( vSupp1 );
708  Vec_IntFree( vSupp2 );
709 // Gia_ManCleanMark1( p ); // this will erase markings
710  ABC_FREE( p->pRefs );
711 }
712 
713 /**Function*************************************************************
714 
715  Synopsis [Assumed that fMark1 marks the internal PIs.]
716 
717  Description []
718 
719  SideEffects []
720 
721  SeeAlso []
722 
723 ***********************************************************************/
724 Gia_Man_t * Gia_ManDupRpm( Gia_Man_t * p )
725 {
726  Vec_Int_t * vPis, * vAnds;
727  Gia_Man_t * pNew;
728  Gia_Obj_t * pObj;
729  int i;
730  // derive PIs and internal nodes
731  vPis = Vec_IntAlloc( 100 );
732  vAnds = Vec_IntAlloc( 100 );
733  Gia_ManCountPisNodes( p, vPis, vAnds );
734 
735  // duplicate AIG
736  Gia_ManFillValue( p );
737  pNew = Gia_ManStart( Gia_ManObjNum(p) );
738  pNew->pName = Abc_UtilStrsav( p->pName );
739  pNew->pSpec = Abc_UtilStrsav( p->pSpec );
740  Gia_ManConst0(p)->Value = 0;
741  // create PIs
742  Gia_ManForEachObjVec( vPis, p, pObj, i )
743  pObj->Value = Gia_ManAppendCi(pNew);
744  // create flops
745  Gia_ManForEachRo( p, pObj, i )
746  pObj->Value = Gia_ManAppendCi( pNew );
747  // create internal nodes
748  Gia_ManForEachObjVec( vAnds, p, pObj, i )
749  pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
750  // create COs
751  Gia_ManForEachCo( p, pObj, i )
752  Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
753  Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
754 
755  // cleanup
756  Vec_IntFree( vPis );
757  Vec_IntFree( vAnds );
758  return pNew;
759 }
760 
761 /**Function*************************************************************
762 
763  Synopsis [Performs structural reparametrization.]
764 
765  Description []
766 
767  SideEffects []
768 
769  SeeAlso []
770 
771 ***********************************************************************/
772 Gia_Man_t * Abs_RpmPerform( Gia_Man_t * p, int nCutMax, int fVerbose, int fVeryVerbose )
773 {
774  Gia_Man_t * pNew;
775 // Gia_ManTestDoms( p );
776 // return NULL;
777  // perform structural analysis
778  Gia_ObjComputeTruthTableStart( p, nCutMax );
779  Abs_RpmPerformMark( p, nCutMax, fVerbose, fVeryVerbose );
780  Gia_ObjComputeTruthTableStop( p );
781  // derive new AIG
782  pNew = Gia_ManDupRpm( p );
783  Gia_ManCleanMark1( p );
784  return pNew;
785 }
786 
787 ////////////////////////////////////////////////////////////////////////
788 /// END OF FILE ///
789 ////////////////////////////////////////////////////////////////////////
790 
791 
792 ABC_NAMESPACE_IMPL_END
793 
Gia_ManComputeDoms
void Gia_ManComputeDoms(Gia_Man_t *p)
Definition: absRpm.c:85
Vec_IntArray
static int * Vec_IntArray(Vec_Int_t *p)
Definition: vecInt.h:328
Abs_ManSupport3
int Abs_ManSupport3(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition: absRpm.c:447
Gia_ManAppendAnd
static int Gia_ManAppendAnd(Gia_Man_t *p, int iLit0, int iLit1)
Definition: gia.h:592
Gia_ManCreateRefs
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition: giaUtil.c:715
Abs_RpmPerformMark
void Abs_RpmPerformMark(Gia_Man_t *p, int nCutMax, int fVerbose, int fVeryVerbose)
Definition: absRpm.c:599
Abs_GiaObjDeref_rec
static int Abs_GiaObjDeref_rec(Gia_Man_t *p, Gia_Obj_t *pNode)
Definition: absRpm.c:300
Gia_ObjSetDom
static void Gia_ObjSetDom(Gia_Man_t *p, Gia_Obj_t *pObj, int d)
Definition: absRpm.c:30
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition: gia.h:1022
Gia_ObjComputeTruthTableStart
void Gia_ObjComputeTruthTableStart(Gia_Man_t *p, int nVarsMax)
Definition: giaTruth.c:282
Gia_ManCountPisNodes
void Gia_ManCountPisNodes(Gia_Man_t *p, Vec_Int_t *vPis, Vec_Int_t *vAnds)
Definition: absRpm.c:273
Gia_ManAppendCo
static int Gia_ManAppendCo(Gia_Man_t *p, int iLit0)
Definition: gia.h:703
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Gia_ObjComputeTruthTableCut
word * Gia_ObjComputeTruthTableCut(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vLeaves)
Definition: giaTruth.c:351
Gia_ObjIsTravIdCurrent
static int Gia_ObjIsTravIdCurrent(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:533
Abc_InfoHasBit
static int Abc_InfoHasBit(unsigned *p, int i)
Definition: abc_global.h:258
Abs_GiaObjRef_rec
static int Abs_GiaObjRef_rec(Gia_Man_t *p, Gia_Obj_t *pNode)
Definition: absRpm.c:317
Gia_ManAppendCi
static int Gia_ManAppendCi(Gia_Man_t *p)
Definition: gia.h:583
Gia_ManTestDoms
void Gia_ManTestDoms(Gia_Man_t *p)
Definition: absRpm.c:203
Gia_ObjComputeTruthTableStop
void Gia_ObjComputeTruthTableStop(Gia_Man_t *p)
Definition: giaTruth.c:293
Gia_ManCountFanoutlessFlops
void Gia_ManCountFanoutlessFlops(Gia_Man_t *p)
Definition: absRpm.c:234
Abs_ManSupport1_rec
void Abs_ManSupport1_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition: absRpm.c:377
Vec_IntFind
static int Vec_IntFind(Vec_Int_t *p, int Entry)
Definition: vecInt.h:895
Abs_ManSupport2
static int Abs_ManSupport2(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition: absRpm.c:425
Gia_ObjRefNum
static int Gia_ObjRefNum(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:521
Gia_ManSetRegNum
void Gia_ManSetRegNum(Gia_Man_t *p, int nRegs)
Definition: giaMan.c:628
Gia_ManForEachObjReverse
#define Gia_ManForEachObjReverse(p, pObj, i)
Definition: gia.h:994
Gia_Obj_t_::fMark1
unsigned fMark1
Definition: gia.h:84
Abs_GiaCheckTruth
int Abs_GiaCheckTruth(word *pTruth, int nSize, int nSize0)
Definition: absRpm.c:548
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
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:258
Gia_ManObj
static Gia_Obj_t * Gia_ManObj(Gia_Man_t *p, int v)
Definition: gia.h:402
Gia_Man_t_::pRefs
int * pRefs
Definition: gia.h:114
Gia_Obj_t_
Definition: gia.h:75
Gia_ManCleanMark1
void Gia_ManCleanMark1(Gia_Man_t *p)
Definition: giaUtil.c:272
Gia_ManTestDoms2
void Gia_ManTestDoms2(Gia_Man_t *p)
Definition: absRpm.c:109
memmove
char * memmove()
Gia_ObjDom
static ABC_NAMESPACE_IMPL_START int Gia_ObjDom(Gia_Man_t *p, Gia_Obj_t *pObj)
DECLARATIONS ///.
Definition: absRpm.c:29
Abs_ManSupport1
int Abs_ManSupport1(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition: absRpm.c:391
Abc_PrintTime
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
Gia_ManAndNum
static int Gia_ManAndNum(Gia_Man_t *p)
Definition: gia.h:389
Gia_ManDupRpm
Gia_Man_t * Gia_ManDupRpm(Gia_Man_t *p)
Definition: absRpm.c:724
Gia_ObjFanin0
static Gia_Obj_t * Gia_ObjFanin0(Gia_Obj_t *pObj)
Definition: gia.h:454
Gia_Man_t_::pName
char * pName
Definition: gia.h:97
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Gia_ObjFanin1Copy
static int Gia_ObjFanin1Copy(Gia_Obj_t *pObj)
Definition: gia.h:482
Gia_ObjIsRo
static int Gia_ObjIsRo(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:443
Abs_GiaCofPrint
int Abs_GiaCofPrint(word *pTruth, int nSize, int nSize0, int Res)
Definition: absRpm.c:513
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
Gia_ObjSetTravIdCurrent
static void Gia_ObjSetTravIdCurrent(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:531
Gia_ManComputePiDoms
Vec_Int_t * Gia_ManComputePiDoms(Gia_Man_t *p)
Definition: absRpm.c:195
Gia_ObjRefInc
static int Gia_ObjRefInc(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:522
Gia_Man_t_::vDoms
Vec_Int_t * vDoms
Definition: gia.h:145
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Vec_IntFill
static void Vec_IntFill(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:356
Gia_Man_t_::pSpec
char * pSpec
Definition: gia.h:98
Gia_ManStart
Gia_Man_t * Gia_ManStart(int nObjsMax)
DECLARATIONS ///.
Definition: giaMan.c:52
Vec_IntUniqify
static int Vec_IntUniqify(Vec_Int_t *p)
Definition: vecInt.h:1314
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Gia_ObjId
static int Gia_ObjId(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:410
Counter
static int Counter
Definition: extraBddMisc.c:1877
Gia_ManFillValue
void Gia_ManFillValue(Gia_Man_t *p)
Definition: giaUtil.c:328
Gia_ManForEachPi
#define Gia_ManForEachPi(p, pObj, i)
Definition: gia.h:1034
Abs_RpmPerform
Gia_Man_t * Abs_RpmPerform(Gia_Man_t *p, int nCutMax, int fVerbose, int fVeryVerbose)
Definition: absRpm.c:772
Vec_IntRemove
static int Vec_IntRemove(Vec_Int_t *p, int Entry)
Definition: vecInt.h:915
Gia_ObjFanin0Copy
static int Gia_ObjFanin0Copy(Gia_Obj_t *pObj)
Definition: gia.h:481
Gia_ObjIsCo
static int Gia_ObjIsCo(Gia_Obj_t *pObj)
Definition: gia.h:421
Gia_ManForEachObjVec
#define Gia_ManForEachObjVec(vVec, p, pObj, i)
Definition: gia.h:988
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Gia_ObjRefDec
static int Gia_ObjRefDec(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:523
Abs_GiaSortNodes
int Abs_GiaSortNodes(Gia_Man_t *p, Vec_Int_t *vSupp)
Definition: absRpm.c:344
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Rf2_Man_t_::fVerbose
int fVerbose
Definition: absRefJ.c:91
Vec_IntShrink
static void Vec_IntShrink(Vec_Int_t *p, int nSizeNew)
Definition: bblif.c:435
Abs_ManSupport2_rec
void Abs_ManSupport2_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition: absRpm.c:411
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Gia_Man_t_
Definition: gia.h:95
Gia_ObjIsAnd
static int Gia_ObjIsAnd(Gia_Obj_t *pObj)
Definition: gia.h:422
Gia_ManForEachObj
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition: gia.h:984
Gia_ManConst0
static Gia_Obj_t * Gia_ManConst0(Gia_Man_t *p)
Definition: gia.h:400
Gia_ObjFanin1
static Gia_Obj_t * Gia_ObjFanin1(Gia_Obj_t *pObj)
Definition: gia.h:455
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
Gia_ManForEachRo
#define Gia_ManForEachRo(p, pObj, i)
Definition: gia.h:1038
Gia_ManAddDom
void Gia_ManAddDom(Gia_Man_t *p, Gia_Obj_t *pObj, int iDom0)
FUNCTION DEFINITIONS ///.
Definition: absRpm.c:52
assert
#define assert(ex)
Definition: util_old.h:213
Gia_Obj_t_::Value
unsigned Value
Definition: gia.h:87
Gia_ManIncrementTravId
void Gia_ManIncrementTravId(Gia_Man_t *p)
Definition: giaUtil.c:149
Gia_ManCollectDoms
Vec_Int_t * Gia_ManCollectDoms(Gia_Man_t *p)
Definition: absRpm.c:165
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Gia_ManPiNum
static int Gia_ManPiNum(Gia_Man_t *p)
Definition: gia.h:385
Vec_IntClear
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Gia_ObjIsCi
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
Abc_UtilStrsav
char * Abc_UtilStrsav(char *s)
Definition: starter.c:47
Gia_ManObjNum
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
Gia_ManRegNum
static int Gia_ManRegNum(Gia_Man_t *p)
Definition: gia.h:387