abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaBalAig.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [giaBalance.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Scalable AIG package.]
8 
9  Synopsis [AIG balancing.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: giaBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "gia.h"
22 #include "misc/vec/vecHash.h"
23 #include "misc/vec/vecQue.h"
24 #include "opt/dau/dau.h"
25 
27 
28 
29 ////////////////////////////////////////////////////////////////////////
30 /// DECLARATIONS ///
31 ////////////////////////////////////////////////////////////////////////
32 
33 // operation manager
34 typedef struct Dam_Man_t_ Dam_Man_t;
35 struct Dam_Man_t_
36 {
37  Gia_Man_t * pGia; // user's AIG
38  Vec_Int_t * vNod2Set; // node ID into fanin set
39  Vec_Int_t * vDiv2Nod; // div ID into root node set
40  Vec_Int_t * vSetStore; // fanin set storage
41  Vec_Int_t * vNodStore; // root node set storage
42  Vec_Flt_t * vCounts; // occur counts
43  Vec_Int_t * vNodLevR; // node reverse level
44  Vec_Int_t * vDivLevR; // divisor reverse level
45  Vec_Int_t * vVisit; // visited MUXes
46  Vec_Que_t * vQue; // pairs by their weight
47  Hash_IntMan_t * vHash; // pair hash table
48  abctime clkStart; // starting the clock
49  int nLevelMax; // maximum level
50  int nDivs; // extracted divisor count
51  int nAnds; // total AND node count
52  int nGain; // total gain in AND nodes
53  int nGainX; // gain from XOR nodes
54 };
55 
56 static inline int Dam_ObjHand( Dam_Man_t * p, int i ) { return i < Vec_IntSize(p->vNod2Set) ? Vec_IntEntry(p->vNod2Set, i) : 0; }
57 static inline int * Dam_ObjSet( Dam_Man_t * p, int i ) { int h = Dam_ObjHand(p, i); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vSetStore, h); }
58 
59 static inline int Dam_DivHand( Dam_Man_t * p, int d ) { return d < Vec_IntSize(p->vDiv2Nod) ? Vec_IntEntry(p->vDiv2Nod, d) : 0; }
60 static inline int * Dam_DivSet( Dam_Man_t * p, int d ) { int h = Dam_DivHand(p, d); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vNodStore, h); }
61 
62 
63 ////////////////////////////////////////////////////////////////////////
64 /// FUNCTION DEFINITIONS ///
65 ////////////////////////////////////////////////////////////////////////
66 
67 /**Function*************************************************************
68 
69  Synopsis [Simplify multi-input AND/XOR.]
70 
71  Description []
72 
73  SideEffects []
74 
75  SeeAlso []
76 
77 ***********************************************************************/
78 void Gia_ManSimplifyXor( Vec_Int_t * vSuper )
79 {
80  int i, k = 0, Prev = -1, This, fCompl = 0;
81  Vec_IntForEachEntry( vSuper, This, i )
82  {
83  if ( This == 0 )
84  continue;
85  if ( This == 1 )
86  fCompl ^= 1;
87  else if ( Prev != This )
88  Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
89  else
90  Prev = -1, k--;
91  }
92  Vec_IntShrink( vSuper, k );
93  if ( Vec_IntSize( vSuper ) == 0 )
94  Vec_IntPush( vSuper, fCompl );
95  else if ( fCompl )
96  Vec_IntWriteEntry( vSuper, 0, Abc_LitNot(Vec_IntEntry(vSuper, 0)) );
97 }
98 void Gia_ManSimplifyAnd( Vec_Int_t * vSuper )
99 {
100  int i, k = 0, Prev = -1, This;
101  Vec_IntForEachEntry( vSuper, This, i )
102  {
103  if ( This == 0 )
104  { Vec_IntFill(vSuper, 1, 0); return; }
105  if ( This == 1 )
106  continue;
107  if ( Prev == -1 || Abc_Lit2Var(Prev) != Abc_Lit2Var(This) )
108  Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
109  else if ( Prev != This )
110  { Vec_IntFill(vSuper, 1, 0); return; }
111  }
112  Vec_IntShrink( vSuper, k );
113  if ( Vec_IntSize( vSuper ) == 0 )
114  Vec_IntPush( vSuper, 1 );
115 }
116 
117 /**Function*************************************************************
118 
119  Synopsis [Collect multi-input AND/XOR.]
120 
121  Description []
122 
123  SideEffects []
124 
125  SeeAlso []
126 
127 ***********************************************************************/
129 {
130  assert( !Gia_IsComplement(pObj) );
131  if ( !Gia_ObjIsXor(pObj) ||
132 // Gia_ObjRefNum(p, pObj) > 1 ||
133  Gia_ObjRefNum(p, pObj) > 2 ||
134  (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
135  Vec_IntSize(p->vSuper) > 100 )
136  {
137  Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
138  return;
139  }
140  assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
143 }
145 {
146  if ( Gia_IsComplement(pObj) ||
147  !Gia_ObjIsAndReal(p, pObj) ||
148 // Gia_ObjRefNum(p, pObj) > 1 ||
149  Gia_ObjRefNum(p, pObj) > 2 ||
150  (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
151  Vec_IntSize(p->vSuper) > 100 )
152  {
153  Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
154  return;
155  }
158 }
160 {
161 // int nSize;
162  if ( p->vSuper == NULL )
163  p->vSuper = Vec_IntAlloc( 1000 );
164  else
165  Vec_IntClear( p->vSuper );
166  if ( Gia_ObjIsXor(pObj) )
167  {
168  assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
171 // nSize = Vec_IntSize(vSuper);
172  Vec_IntSort( p->vSuper, 0 );
174 // if ( nSize != Vec_IntSize(vSuper) )
175 // printf( "X %d->%d ", nSize, Vec_IntSize(vSuper) );
176  }
177  else if ( Gia_ObjIsAndReal(p, pObj) )
178  {
181 // nSize = Vec_IntSize(vSuper);
182  Vec_IntSort( p->vSuper, 0 );
184 // if ( nSize != Vec_IntSize(vSuper) )
185 // printf( "A %d->%d ", nSize, Vec_IntSize(vSuper) );
186  }
187  else assert( 0 );
188 // if ( nSize > 10 )
189 // printf( "%d ", nSize );
190  assert( Vec_IntSize(p->vSuper) > 0 );
191 }
192 
193 /**Function*************************************************************
194 
195  Synopsis []
196 
197  Description []
198 
199  SideEffects []
200 
201  SeeAlso []
202 
203 ***********************************************************************/
204 void Gia_ManCreateGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper )
205 {
206  int iLit0 = Vec_IntPop(vSuper);
207  int iLit1 = Vec_IntPop(vSuper);
208  int iLit, i;
209  if ( !Gia_ObjIsXor(pObj) )
210  iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 );
211  else if ( pNew->pMuxes )
212  iLit = Gia_ManHashXorReal( pNew, iLit0, iLit1 );
213  else
214  iLit = Gia_ManHashXor( pNew, iLit0, iLit1 );
215  Vec_IntPush( vSuper, iLit );
216  Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(iLit)) );
217  // shift to the corrent location
218  for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
219  {
220  int iLit1 = Vec_IntEntry(vSuper, i);
221  int iLit2 = Vec_IntEntry(vSuper, i-1);
222  if ( Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1)) <= Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
223  break;
224  Vec_IntWriteEntry( vSuper, i, iLit2 );
225  Vec_IntWriteEntry( vSuper, i-1, iLit1 );
226  }
227 }
228 int Gia_ManBalanceGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper, int * pLits, int nLits )
229 {
230  assert( !Gia_ObjIsBuf(pObj) );
231  Vec_IntClear( vSuper );
232  if ( nLits == 1 )
233  Vec_IntPush( vSuper, pLits[0] );
234  else if ( nLits == 2 )
235  {
236  Vec_IntPush( vSuper, pLits[0] );
237  Vec_IntPush( vSuper, pLits[1] );
238  Gia_ManCreateGate( pNew, pObj, vSuper );
239  }
240  else if ( nLits > 2 )
241  {
242  // collect levels
243  int i, * pArray, * pPerm;
244  for ( i = 0; i < nLits; i++ )
245  Vec_IntPush( vSuper, Gia_ObjLevelId(pNew, Abc_Lit2Var(pLits[i])) );
246  // sort by level
247  Vec_IntGrow( vSuper, 4 * nLits );
248  pArray = Vec_IntArray( vSuper );
249  pPerm = pArray + nLits;
250  Abc_QuickSortCostData( pArray, nLits, 1, (word *)(pArray + 2 * nLits), pPerm );
251  // collect in the increasing order of level
252  for ( i = 0; i < nLits; i++ )
253  Vec_IntWriteEntry( vSuper, i, pLits[pPerm[i]] );
254  Vec_IntShrink( vSuper, nLits );
255 // Vec_IntForEachEntry( vSuper, iLit, i )
256 // printf( "%d ", Gia_ObjLevel(pNew, Gia_ManObj( pNew, Abc_Lit2Var(iLit) )) );
257 // printf( "\n" );
258  // perform incremental extraction
259  while ( Vec_IntSize(vSuper) > 1 )
260  Gia_ManCreateGate( pNew, pObj, vSuper );
261  }
262  // consider trivial case
263  assert( Vec_IntSize(vSuper) == 1 );
264  return Vec_IntEntry(vSuper, 0);
265 }
266 
267 /**Function*************************************************************
268 
269  Synopsis []
270 
271  Description []
272 
273  SideEffects []
274 
275  SeeAlso []
276 
277 ***********************************************************************/
279 {
280  int i, iLit, iBeg, iEnd;
281  if ( ~pObj->Value )
282  return;
283  assert( Gia_ObjIsAnd(pObj) );
284  assert( !Gia_ObjIsBuf(pObj) );
285  // handle MUX
286  if ( Gia_ObjIsMux(p, pObj) )
287  {
288  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
289  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin1(pObj) );
290  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin2(p, pObj) );
291  pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
292  Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
293  return;
294  }
295  // find supergate
296  Gia_ManSuperCollect( p, pObj );
297  // save entries
298  if ( p->vStore == NULL )
299  p->vStore = Vec_IntAlloc( 1000 );
300  iBeg = Vec_IntSize( p->vStore );
301  Vec_IntAppend( p->vStore, p->vSuper );
302  iEnd = Vec_IntSize( p->vStore );
303  // call recursively
304  Vec_IntForEachEntryStartStop( p->vStore, iLit, i, iBeg, iEnd )
305  {
306  Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(iLit) );
307  Gia_ManBalance_rec( pNew, p, pTemp );
309  }
310  assert( Vec_IntSize(p->vStore) == iEnd );
311  // consider general case
312  pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, Vec_IntEntryP(p->vStore, iBeg), iEnd-iBeg );
313  Vec_IntShrink( p->vStore, iBeg );
314 }
316 {
317  Gia_Man_t * pNew, * pTemp;
318  Gia_Obj_t * pObj;
319  int i;
320  Gia_ManFillValue( p );
321  Gia_ManCreateRefs( p );
322  // start the new manager
323  pNew = Gia_ManStart( Gia_ManObjNum(p) );
324  pNew->pName = Abc_UtilStrsav( p->pName );
325  pNew->pSpec = Abc_UtilStrsav( p->pSpec );
326  pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
327  pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
328  // create constant and inputs
329  Gia_ManConst0(p)->Value = 0;
330  Gia_ManForEachCi( p, pObj, i )
331  pObj->Value = Gia_ManAppendCi( pNew );
332  // create internal nodes
333  Gia_ManHashStart( pNew );
334  Gia_ManForEachBuf( p, pObj, i )
335  {
336  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
337  pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
338  Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
339  }
340  Gia_ManForEachCo( p, pObj, i )
341  {
342  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
343  pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
344  }
345  assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
346  Gia_ManHashStop( pNew );
347  Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
348  // perform cleanup
349  pNew = Gia_ManCleanup( pTemp = pNew );
350  Gia_ManStop( pTemp );
351  return pNew;
352 }
353 
354 /**Function*************************************************************
355 
356  Synopsis []
357 
358  Description []
359 
360  SideEffects []
361 
362  SeeAlso []
363 
364 ***********************************************************************/
365 Gia_Man_t * Gia_ManBalance( Gia_Man_t * p, int fSimpleAnd, int fVerbose )
366 {
367  Gia_Man_t * pNew, * pNew1, * pNew2;
368  if ( fVerbose ) Gia_ManPrintStats( p, NULL );
369  pNew = fSimpleAnd ? Gia_ManDup( p ) : Gia_ManDupMuxes( p, 2 );
370  if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
371  pNew1 = Gia_ManBalanceInt( pNew );
372  if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
373  Gia_ManStop( pNew );
374  pNew2 = Gia_ManDupNoMuxes( pNew1 );
375  if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
376  Gia_ManStop( pNew1 );
377  return pNew2;
378 }
379 
380 
381 
382 
383 
384 /**Function*************************************************************
385 
386  Synopsis []
387 
388  Description []
389 
390  SideEffects []
391 
392  SeeAlso []
393 
394 ***********************************************************************/
396 {
397  Dam_Man_t * p;
398  p = ABC_CALLOC( Dam_Man_t, 1 );
399  p->clkStart = Abc_Clock();
400  p->vVisit = Vec_IntAlloc( 1000 );
401  p->pGia = pGia;
402  return p;
403 }
405 {
406  Vec_IntFreeP( &p->vVisit );
407  Vec_IntFreeP( &p->vDivLevR );
408  Vec_IntFreeP( &p->vNodLevR );
409  Vec_IntFreeP( &p->vNod2Set );
410  Vec_IntFreeP( &p->vDiv2Nod );
411  Vec_IntFreeP( &p->vSetStore );
412  Vec_IntFreeP( &p->vNodStore );
413  Vec_FltFreeP( &p->vCounts );
414  Vec_QueFreeP( &p->vQue );
415  Hash_IntManStop( p->vHash );
416  ABC_FREE( p );
417 }
418 
419 /**Function*************************************************************
420 
421  Synopsis [Collect initial multi-input gates.]
422 
423  Description []
424 
425  SideEffects []
426 
427  SeeAlso []
428 
429 ***********************************************************************/
431 {
432  Gia_Obj_t * pObj;
433  int i, iBeg, iEnd, iLit;
434  if ( Dam_ObjHand(p, Id) || Id == 0 )
435  return;
436  pObj = Gia_ManObj(p->pGia, Id);
437  if ( Gia_ObjIsCi(pObj) )
438  return;
439  if ( Gia_ObjIsBuf(pObj) )
440  {
441  Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) );
442  return;
443  }
444  if ( Gia_ObjIsMux(p->pGia, pObj) )
445  {
446  if ( pObj->fMark0 )
447  return;
448  pObj->fMark0 = 1;
449  Vec_IntPush( p->vVisit, Id );
450  Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) );
451  Dam_ManCollectSets_rec( p, Gia_ObjFaninId1(pObj, Id) );
452  Dam_ManCollectSets_rec( p, Gia_ObjFaninId2(p->pGia, Id) );
453  p->nAnds += 3;
454  return;
455  }
456  Gia_ManSuperCollect( p->pGia, pObj );
457  Vec_IntWriteEntry( p->vNod2Set, Id, Vec_IntSize(p->vSetStore) );
458  Vec_IntPush( p->vSetStore, Vec_IntSize(p->pGia->vSuper) );
459  p->nAnds += (1 + 2 * Gia_ObjIsXor(pObj)) * (Vec_IntSize(p->pGia->vSuper) - 1);
460  // save entries
461  iBeg = Vec_IntSize( p->vSetStore );
462  Vec_IntAppend( p->vSetStore, p->pGia->vSuper );
463  iEnd = Vec_IntSize( p->vSetStore );
464  // call recursively
465  Vec_IntForEachEntryStartStop( p->vSetStore, iLit, i, iBeg, iEnd )
467 }
469 {
470  Gia_Obj_t * pObj;
471  int i;
472  Gia_ManCreateRefs( p->pGia );
473  p->vNod2Set = Vec_IntStart( Gia_ManObjNum(p->pGia) );
474  p->vSetStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) );
475  Vec_IntPush( p->vSetStore, -1 );
476  Vec_IntClear( p->vVisit );
477  Gia_ManForEachCo( p->pGia, pObj, i )
478  Dam_ManCollectSets_rec( p, Gia_ObjFaninId0p(p->pGia, pObj) );
479  ABC_FREE( p->pGia->pRefs );
480  Gia_ManForEachObjVec( p->vVisit, p->pGia, pObj, i )
481  pObj->fMark0 = 0;
482 }
483 
484 /**Function*************************************************************
485 
486  Synopsis [Create divisors.]
487 
488  Description []
489 
490  SideEffects []
491 
492  SeeAlso []
493 
494 ***********************************************************************/
495 int Dam_ManDivSlack( Dam_Man_t * p, int iLit0, int iLit1, int LevR )
496 {
497  int Lev0 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit0)));
498  int Lev1 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit1)));
499  int Slack = p->nLevelMax - LevR - Abc_MaxInt(Lev0, Lev1) - 1 - (int)(iLit0 > iLit1);
500  return Abc_MinInt( Slack, 100 );
501 }
502 void Dam_ManCreateMultiRefs( Dam_Man_t * p, Vec_Int_t ** pvRefsAnd, Vec_Int_t ** pvRefsXor )
503 {
504  Vec_Int_t * vRefsAnd, * vRefsXor;
505  Gia_Obj_t * pObj;
506  int i, k, * pSet;
507  vRefsAnd = Vec_IntStart( 2 * Gia_ManObjNum(p->pGia) );
508  vRefsXor = Vec_IntStart( Gia_ManObjNum(p->pGia) );
509  Gia_ManForEachAnd( p->pGia, pObj, i )
510  {
511  if ( !Dam_ObjHand(p, i) )
512  continue;
513  pSet = Dam_ObjSet(p, i);
514  if ( Gia_ObjIsXor(pObj) )
515  for ( k = 1; k <= pSet[0]; k++ )
516  {
517  assert( !Abc_LitIsCompl(pSet[k]) );
518  Vec_IntAddToEntry( vRefsXor, Abc_Lit2Var(pSet[k]), 1 );
519  }
520  else if ( Gia_ObjIsAndReal(p->pGia, pObj) )
521  for ( k = 1; k <= pSet[0]; k++ )
522  Vec_IntAddToEntry( vRefsAnd, pSet[k], 1 );
523  else assert( 0 );
524  }
525  *pvRefsAnd = vRefsAnd;
526  *pvRefsXor = vRefsXor;
527 }
528 void Dam_ManCreatePairs( Dam_Man_t * p, int fVerbose )
529 {
530  Gia_Obj_t * pObj;
531  Hash_IntMan_t * vHash;
532  Vec_Int_t * vRefsAnd, * vRefsXor, * vSuper, * vDivs, * vRemap, * vLevRMax;
533  int i, j, k, Num, FanK, FanJ, nRefs, iNode, iDiv, * pSet;
534  int nPairsAll = 0, nPairsTried = 0, nPairsUsed = 0, nPairsXor = 0;
535  int nDivsAll = 0, nDivsUsed = 0, nDivsXor = 0;
536  Dam_ManCollectSets( p );
537  vSuper = p->pGia->vSuper;
538  vDivs = Vec_IntAlloc( Gia_ManObjNum(p->pGia) );
539  vHash = Hash_IntManStart( Gia_ManObjNum(p->pGia)/2 );
540  vLevRMax = Vec_IntStart( 1000 );
541  Dam_ManCreateMultiRefs( p, &vRefsAnd, &vRefsXor );
542  Gia_ManForEachAnd( p->pGia, pObj, i )
543  {
544  if ( !Dam_ObjHand(p, i) )
545  continue;
546  pSet = Dam_ObjSet(p, i);
547  nPairsAll += pSet[0] * (pSet[0] - 1) / 2;
548  Vec_IntClear(vSuper);
549  if ( Gia_ObjIsXor(pObj) )
550  {
551  for ( k = 1; k <= pSet[0]; k++ )
552  if ( Vec_IntEntry(vRefsXor, Abc_Lit2Var(pSet[k])) > 1 )
553  Vec_IntPush( vSuper, pSet[k] );
554  }
555  else if ( Gia_ObjIsAndReal(p->pGia, pObj) )
556  {
557  for ( k = 1; k <= pSet[0]; k++ )
558  if ( Vec_IntEntry(vRefsAnd, pSet[k]) > 1 )
559  Vec_IntPush( vSuper, pSet[k] );
560  }
561  else assert( 0 );
562  if ( Vec_IntSize(vSuper) < 2 )
563  continue;
564  // enumerate pairs
565  nPairsTried += Vec_IntSize(vSuper) * (Vec_IntSize(vSuper) - 1) / 2;
566  Vec_IntPush( vDivs, -i ); // remember node
567  Vec_IntForEachEntry( vSuper, FanK, k )
568  Vec_IntForEachEntryStart( vSuper, FanJ, j, k+1 )
569  {
570  if ( (FanK > FanJ) ^ Gia_ObjIsXor(pObj) )
571  Num = Hash_Int2ManInsert( vHash, FanJ, FanK, 0 );
572  else
573  Num = Hash_Int2ManInsert( vHash, FanK, FanJ, 0 );
574  if ( Hash_Int2ObjInc( vHash, Num ) == 1 )
575  {
576  nDivsUsed++;
577  nDivsXor += Gia_ObjIsXor(pObj);
578  }
579  Vec_IntPush( vDivs, Num ); // remember devisor
580  // update reverse level
581  if ( Num >= Vec_IntSize(vLevRMax) )
582  Vec_IntFillExtra( vLevRMax, 3 * Vec_IntSize(vLevRMax) / 2, 0 );
583  Vec_IntUpdateEntry( vLevRMax, Num, Vec_IntEntry(p->vNodLevR, i) );
584  }
585  }
586  Vec_IntFree( vRefsAnd );
587  Vec_IntFree( vRefsXor );
588 // Hash_IntManProfile( vHash );
589  // remove entries that appear only once
590  p->vHash = Hash_IntManStart( 3 * nDivsUsed /2 );
591  p->vCounts = Vec_FltAlloc( 2 * nDivsUsed ); Vec_FltPush( p->vCounts, ABC_INFINITY );
592  p->vQue = Vec_QueAlloc( Vec_FltCap(p->vCounts) );
593  Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) );
594  // mapping div to node
595  p->vDiv2Nod = Vec_IntAlloc( 2 * nDivsUsed ); Vec_IntPush( p->vDiv2Nod, ABC_INFINITY );
596  p->vNodStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); Vec_IntPush( p->vNodStore, -1 );
597  nDivsAll = Hash_IntManEntryNum(vHash);
598  vRemap = Vec_IntStartFull( nDivsAll+1 );
599  for ( i = 1; i <= nDivsAll; i++ )
600  {
601  nRefs = Hash_IntObjData2(vHash, i);
602  if ( nRefs < 2 )
603  continue;
604  nPairsUsed += nRefs;
605  if ( Hash_IntObjData0(vHash, i) > Hash_IntObjData1(vHash, i) )
606  nPairsXor += nRefs;
607  Num = Hash_Int2ManInsert( p->vHash, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), 0 );
608  assert( Num == Hash_IntManEntryNum(p->vHash) );
609  assert( Num == Vec_FltSize(p->vCounts) );
610  Vec_FltPush( p->vCounts, nRefs + 0.005*Dam_ManDivSlack(p, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), Vec_IntEntry(vLevRMax, i)) );
611  Vec_QuePush( p->vQue, Num );
612  // remember divisors
613  assert( Num == Vec_IntSize(p->vDiv2Nod) );
614  Vec_IntPush( p->vDiv2Nod, Vec_IntSize(p->vNodStore) );
615  Vec_IntPush( p->vNodStore, 0 );
616  Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 );
617  // remember entry
618  Vec_IntWriteEntry( vRemap, i, Num );
619  }
620  assert( Vec_FltSize(p->vCounts) == Hash_IntManEntryNum(p->vHash)+1 );
621  assert( Vec_IntSize(p->vDiv2Nod) == nDivsUsed+1 );
622  Hash_IntManStop( vHash );
623  Vec_IntFree( vLevRMax );
624  // fill in the divisors
625  iNode = -1;
626  Vec_IntForEachEntry( vDivs, iDiv, i )
627  {
628  if ( iDiv < 0 )
629  {
630  iNode = -iDiv;
631  continue;
632  }
633  Num = Vec_IntEntry( vRemap, iDiv );
634  if ( Num == -1 )
635  continue;
636  pSet = Dam_DivSet( p, Num );
637  pSet[++pSet[0]] = iNode;
638  }
639  Vec_IntFree( vRemap );
640  Vec_IntFree( vDivs );
641  // create storage for reverse level of divisor during update
642  p->vDivLevR = Vec_IntStart( 2 * nDivsUsed );
643  // make sure divisors are added correctly
644 // for ( i = 1; i <= nDivsUsed; i++ )
645 // assert( Dam_DivSet(p, i)[0] == Vec_FltEntry(p->vCounts, i)+1 );
646  if ( !fVerbose )
647  return;
648  // print stats
649  printf( "Pairs:" );
650  printf( " Total =%9d (%6.2f %%)", nPairsAll, 100.0 * nPairsAll / Abc_MaxInt(nPairsAll, 1) );
651  printf( " Tried =%9d (%6.2f %%)", nPairsTried, 100.0 * nPairsTried / Abc_MaxInt(nPairsAll, 1) );
652  printf( " Used =%9d (%6.2f %%)", nPairsUsed, 100.0 * nPairsUsed / Abc_MaxInt(nPairsAll, 1) );
653  printf( " Xor =%9d (%6.2f %%)", nPairsXor, 100.0 * nPairsXor / Abc_MaxInt(nPairsAll, 1) );
654  printf( "\n" );
655  printf( "Div: " );
656  printf( " Total =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
657  printf( " Tried =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
658  printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) );
659  printf( " Xor =%9d (%6.2f %%)", nDivsXor, 100.0 * nDivsXor / Abc_MaxInt(nDivsAll, 1) );
660  printf( "\n" );
661 }
662 
663 /**Function*************************************************************
664 
665  Synopsis [Derives new AIG.]
666 
667  Description []
668 
669  SideEffects []
670 
671  SeeAlso []
672 
673 ***********************************************************************/
674 void Dam_ManMultiAig_rec( Dam_Man_t * pMan, Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj )
675 {
676  int i, * pSet;
677  if ( ~pObj->Value )
678  return;
679  assert( Gia_ObjIsAnd(pObj) );
680  pSet = Dam_ObjSet(pMan, Gia_ObjId(p, pObj));
681  if ( pSet == NULL )
682  {
683  Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
684  Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin1(pObj) );
685  if ( Gia_ObjIsMux(p, pObj) )
686  {
687  Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin2(p, pObj) );
688  pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
689  }
690  else if ( Gia_ObjIsXor(pObj) )
691  pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
692  else
693  pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
694  Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
695  return;
696  }
697  assert( Gia_ObjIsXor(pObj) || Gia_ObjIsAndReal(p, pObj) );
698  // call recursively
699  for ( i = 1; i <= pSet[0]; i++ )
700  {
701  Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(pSet[i]) );
702  Dam_ManMultiAig_rec( pMan, pNew, p, pTemp );
703  pSet[i] = Abc_LitNotCond( pTemp->Value, Abc_LitIsCompl(pSet[i]) );
704  }
705  // create balanced gate
706  pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, pSet + 1, pSet[0] );
707 }
709 {
710  Gia_Man_t * p = pMan->pGia;
711  Gia_Man_t * pNew, * pTemp;
712  Gia_Obj_t * pObj;
713  int i;
714  // start the new manager
715  pNew = Gia_ManStart( 2*Gia_ManObjNum(p) );
716  pNew->pName = Abc_UtilStrsav( p->pName );
717  pNew->pSpec = Abc_UtilStrsav( p->pSpec );
718  pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
719  pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
720  // create constant and inputs
721  Gia_ManFillValue( p );
722  Gia_ManConst0(p)->Value = 0;
723  Gia_ManForEachCi( p, pObj, i )
724  {
725  pObj->Value = Gia_ManAppendCi( pNew );
726  Vec_IntWriteEntry( pNew->vLevels, Abc_Lit2Var(pObj->Value), Gia_ObjLevel(p, pObj) );
727  }
728  // create internal nodes
729  Gia_ManHashStart( pNew );
730  Gia_ManForEachBuf( p, pObj, i )
731  {
732  Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
733  pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
734  Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
735  }
736  Gia_ManForEachCo( p, pObj, i )
737  {
738  Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
739  pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
740  }
741 // assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
742  Gia_ManHashStop( pNew );
743  Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
744  // perform cleanup
745  pNew = Gia_ManCleanup( pTemp = pNew );
746  Gia_ManStop( pTemp );
747  return pNew;
748 }
749 
750 /**Function*************************************************************
751 
752  Synopsis [Updates the data-structure after extracting one divisor.]
753 
754  Description []
755 
756  SideEffects []
757 
758  SeeAlso []
759 
760 ***********************************************************************/
761 void Dam_PrintDiv( Dam_Man_t * p, int iDiv )
762 {
763  if ( iDiv == 0 )
764  printf( "Final statistics after extracting %6d divisors: ", p->nDivs );
765  else
766  {
767  char Buffer[100];
768  int iData0 = Hash_IntObjData0(p->vHash, iDiv);
769  int iData1 = Hash_IntObjData1(p->vHash, iDiv);
770  printf( "Div%5d : ", p->nDivs+1 );
771  printf( "D%-8d = ", iDiv );
772  sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData0)? '!':' ', Abc_Lit2Var(iData0) );
773  printf( "%8s ", Buffer );
774  printf( "%c ", (iData0 < iData1) ? '*' : '+' );
775  sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData1)? '!':' ', Abc_Lit2Var(iData1) );
776  printf( "%8s ", Buffer );
777  printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, iDiv) );
778  }
779  printf( "Divs =%8d ", Hash_IntManEntryNum(p->vHash) );
780  printf( "Ands =%8d ", p->nAnds - p->nGain );
781  Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
782 }
784 {
785  int i;
786  printf( "Divisor queue: \n" );
787  for ( i = 1; i <= Hash_IntManEntryNum(p->vHash); i++ )
788  {
789  int iLit0 = Hash_IntObjData0(p->vHash, i);
790  int iLit1 = Hash_IntObjData1(p->vHash, i);
791  printf( "Div %7d : ", i );
792  printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, i) );
793  printf( "F = %c%c ", Abc_LitIsCompl(iLit0) ? '!': ' ', 'a' + Abc_Lit2Var(iLit0)-1 );
794  printf( "%c ", (Hash_IntObjData0(p->vHash, i) < Hash_IntObjData1(p->vHash, i)) ? '*':'+' );
795  printf( "%c%c ", Abc_LitIsCompl(iLit1) ? '!': ' ', 'a' + Abc_Lit2Var(iLit1)-1 );
796  printf( "\n" );
797  }
798 }
799 int Dam_ManUpdateNode( Dam_Man_t * p, int iObj, int iLit0, int iLit1, int iLitNew, Vec_Int_t * vDivs )
800 {
801  int * pSet = Dam_ObjSet( p, iObj );
802  int i, k, c, Num, iLit, iLit2, fPres;
803  // check if literal can be found
804  for ( i = 1; i <= pSet[0]; i++ )
805  if ( pSet[i] == iLit0 )
806  break;
807  if ( i > pSet[0] )
808  return 0;
809  // check if literal can be found
810  for ( i = 1; i <= pSet[0]; i++ )
811  if ( pSet[i] == iLit1 )
812  break;
813  if ( i > pSet[0] )
814  return 0;
815  // compact literals
816  Vec_IntPush( vDivs, -iObj );
817  for ( k = i = 1; i <= pSet[0]; i++ )
818  {
819  if ( iLit0 == pSet[i] || iLit1 == pSet[i] )
820  continue;
821  pSet[k++] = iLit = pSet[i];
822  // reduce weights of the divisors
823  fPres = 0;
824  for ( c = 0; c < 2; c++ )
825  {
826  iLit2 = c ? iLit1 : iLit0;
827  if ( (iLit > iLit2) ^ (iLit0 > iLit1) )
828  Num = *Hash_Int2ManLookup( p->vHash, iLit2, iLit );
829  else
830  Num = *Hash_Int2ManLookup( p->vHash, iLit, iLit2 );
831  if ( Num > 0 )
832  {
833  Vec_FltAddToEntry( p->vCounts, Num, -1 );
834  if ( Vec_QueIsMember(p->vQue, Num) )
835  {
836  Vec_QueUpdate( p->vQue, Num );
837  fPres |= (1 << c);
838  }
839  }
840  }
841  if ( fPres != 3 )
842  continue;
843  if ( (iLit > iLitNew) ^ (iLit0 > iLit1) )
844  Num = Hash_Int2ManInsert( p->vHash, iLitNew, iLit, 0 );
845  else
846  Num = Hash_Int2ManInsert( p->vHash, iLit, iLitNew, 0 );
847  Hash_Int2ObjInc( p->vHash, Num );
848  Vec_IntPush( vDivs, Num );
849  // update reverse level
850  if ( Num >= Vec_IntSize(p->vDivLevR) )
851  Vec_IntFillExtra( p->vDivLevR, 3 * Vec_IntSize(p->vDivLevR) / 2, 0 );
852  Vec_IntUpdateEntry( p->vDivLevR, Num, Vec_IntEntry(p->vNodLevR, iObj) );
853  }
854  pSet[k] = iLitNew;
855  pSet[0] = k;
856  return 1;
857 }
858 void Dam_ManUpdate( Dam_Man_t * p, int iDiv )
859 {
860  Vec_Int_t * vDivs = p->pGia->vSuper;
861  int iLit0 = Hash_IntObjData0(p->vHash, iDiv);
862  int iLit1 = Hash_IntObjData1(p->vHash, iDiv);
863  int i, iLitNew, * pSet, * pNods = Dam_DivSet( p, iDiv );
864  int nPresent = 0, nPairsStart, nPairsStop, pPairsNew, nRefs;
865  int fThisIsXor = (iLit0 > iLit1), iDivTemp, iNode;
866 // Dam_PrintQue( p );
867  if ( fThisIsXor )
868  iLitNew = Gia_ManAppendXorReal( p->pGia, iLit0, iLit1 );
869  else
870  iLitNew = Gia_ManAppendAnd( p->pGia, iLit0, iLit1 );
871  Gia_ObjSetGateLevel( p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew)) );
872 // printf( "%d ", Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew))) );
873  // replace entries
874  assert( pNods[0] >= 2 );
875  nPairsStart = Hash_IntManEntryNum(p->vHash) + 1;
876  Vec_IntClear( vDivs );
877  for ( i = 1; i <= pNods[0]; i++ )
878  nPresent += Dam_ManUpdateNode( p, pNods[i], iLit0, iLit1, iLitNew, vDivs );
879  nPairsStop = Hash_IntManEntryNum(p->vHash) + 1;
880  // extend arrayvs
881  pPairsNew = 0;
882  Vec_FltFillExtra( p->vCounts, nPairsStop, 0 );
883  Vec_IntFillExtra( p->vDiv2Nod, nPairsStop, -1 );
884  for ( i = nPairsStart; i < nPairsStop; i++ )
885  {
886  nRefs = Hash_IntObjData2(p->vHash, i);
887  if ( nRefs < 2 )
888  continue;
889  Vec_FltWriteEntry( p->vCounts, i, nRefs + 0.001*Dam_ManDivSlack(p, Hash_IntObjData0(p->vHash, i), Hash_IntObjData1(p->vHash, i), Vec_IntEntry(p->vDivLevR, i)) );
890  Vec_QuePush( p->vQue, i );
891  // remember divisors
892  Vec_IntWriteEntry( p->vDiv2Nod, i, Vec_IntSize(p->vNodStore) );
893  Vec_IntPush( p->vNodStore, 0 );
894  Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 );
895  pPairsNew++;
896  }
897 // printf( "Added %d new pairs\n", pPairsNew );
898  // fill in the divisors
899  iNode = -1;
900  Vec_IntForEachEntry( vDivs, iDivTemp, i )
901  {
902  if ( iDivTemp < 0 )
903  {
904  iNode = -iDivTemp;
905  continue;
906  }
907  if ( Vec_IntEntry(p->vDiv2Nod, iDivTemp) == -1 )
908  continue;
909  pSet = Dam_DivSet( p, iDivTemp );
910  pSet[++pSet[0]] = iNode;
911  }
912  // make sure divisors are added correctly
913  for ( i = nPairsStart; i < nPairsStop; i++ )
914  if ( Vec_IntEntry(p->vDiv2Nod, i) > 0 )
915  assert( Dam_DivSet(p, i)[0] == Hash_IntObjData2(p->vHash, i) );
916  // update costs
917  Vec_FltWriteEntry( p->vCounts, iDiv, 0 );
918  p->nGain += (1 + 2 * fThisIsXor) * (nPresent - 1);
919  p->nGainX += 3 * fThisIsXor * (nPresent - 1);
920  p->nDivs++;
921 }
922 
923 /**Function*************************************************************
924 
925  Synopsis [Perform extraction for multi-input AND/XOR.]
926 
927  Description []
928 
929  SideEffects []
930 
931  SeeAlso []
932 
933 ***********************************************************************/
934 Gia_Man_t * Dam_ManAreaBalanceInt( Gia_Man_t * pGia, Vec_Int_t * vCiLevels, int nNewNodesMax, int fVerbose, int fVeryVerbose )
935 {
936  Gia_Man_t * pNew;
937  Dam_Man_t * p;
938  int i, iDiv;
939  p = Dam_ManAlloc( pGia );
940  p->nLevelMax = Gia_ManSetLevels( p->pGia, vCiLevels );
941  p->vNodLevR = Gia_ManReverseLevel( p->pGia );
942  Vec_IntFillExtra( p->pGia->vLevels, 3*Gia_ManObjNum(p->pGia)/2, 0 );
943  Dam_ManCreatePairs( p, fVerbose );
944  for ( i = 0; i < nNewNodesMax && Vec_QueTopPriority(p->vQue) >= 2; i++ )
945  {
946  iDiv = Vec_QuePop(p->vQue);
947  if ( fVeryVerbose )
948  Dam_PrintDiv( p, iDiv );
949  Dam_ManUpdate( p, iDiv );
950  }
951  if ( fVeryVerbose )
952  Dam_PrintDiv( p, 0 );
953  pNew = Dam_ManMultiAig( p );
954  if ( fVerbose )
955  {
956  int nDivsAll = Hash_IntManEntryNum(p->vHash);
957  int nDivsUsed = p->nDivs;
958  printf( "Div: " );
959  printf( " Total =%9d (%6.2f %%) ", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
960  printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) );
961  printf( " Gain =%6d (%6.2f %%)", p->nGain, 100.0 * p->nGain / Abc_MaxInt(p->nAnds, 1) );
962  printf( " GainX = %d ", p->nGainX );
963  Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
964  }
965  Dam_ManFree( p );
966  return pNew;
967 }
968 Gia_Man_t * Gia_ManAreaBalance( Gia_Man_t * p, int fSimpleAnd, int nNewNodesMax, int fVerbose, int fVeryVerbose )
969 {
970  Gia_Man_t * pNew0, * pNew, * pNew1, * pNew2;
971  Vec_Int_t * vCiLevels;
972  // determine CI levels
973  if ( p->pManTime && p->vLevels == NULL )
975  vCiLevels = Gia_ManGetCiLevels( p );
976  // get the starting manager
977  pNew0 = Gia_ManHasMapping(p) ? (Gia_Man_t *)Dsm_ManDeriveGia(p, 0) : p;
978  if ( fVerbose ) Gia_ManPrintStats( pNew0, NULL );
979  // derive internal manager
980  pNew = fSimpleAnd ? Gia_ManDup( pNew0 ) : Gia_ManDupMuxes( pNew0, 2 );
981  if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
982  if ( pNew0 != p ) Gia_ManStop( pNew0 );
983  // perform the operation
984  pNew1 = Dam_ManAreaBalanceInt( pNew, vCiLevels, nNewNodesMax, fVerbose, fVeryVerbose );
985  if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
986  Gia_ManStop( pNew );
987  Vec_IntFreeP( &vCiLevels );
988  // derive the final result
989  pNew2 = Gia_ManDupNoMuxes( pNew1 );
990  if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
991  Gia_ManStop( pNew1 );
992  // normalize if needed
993  if ( !Gia_ManIsNormalized(pNew2) )
994  {
995  pNew2 = Gia_ManDupNormalize( pNew1 = pNew2 );
996  Gia_ManStop( pNew1 );
997  }
998  Gia_ManTransferTiming( pNew2, p );
999  return pNew2;
1000 }
1001 
1002 ////////////////////////////////////////////////////////////////////////
1003 /// END OF FILE ///
1004 ////////////////////////////////////////////////////////////////////////
1005 
1006 
1008 
int nObjsAlloc
Definition: gia.h:102
static int Gia_ObjFanin2Copy(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:483
static Hash_IntMan_t * Hash_IntManStart(int nSize)
FUNCTION DEFINITIONS ///.
Definition: vecHash.h:86
static int Gia_ObjToLit(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:497
static int Gia_ObjLevelId(Gia_Man_t *p, int Id)
Definition: gia.h:500
static int Dam_DivHand(Dam_Man_t *p, int d)
Definition: giaBalAig.c:59
Vec_Int_t * vNodLevR
Definition: giaBalAig.c:43
static int * Vec_IntArray(Vec_Int_t *p)
Definition: vecInt.h:328
static int Gia_ManAppendAnd(Gia_Man_t *p, int iLit0, int iLit1)
Definition: gia.h:592
Gia_Man_t * pGia
Definition: giaBalAig.c:37
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition: giaUtil.c:715
static Gia_Obj_t * Gia_ObjChild0(Gia_Obj_t *pObj)
Definition: gia.h:457
Vec_Flt_t * vCounts
Definition: giaBalAig.c:42
static int * Dam_DivSet(Dam_Man_t *p, int d)
Definition: giaBalAig.c:60
static int Hash_IntManEntryNum(Hash_IntMan_t *p)
Definition: vecHash.h:101
Gia_Man_t * Dam_ManMultiAig(Dam_Man_t *pMan)
Definition: giaBalAig.c:708
Vec_Int_t * Gia_ManGetCiLevels(Gia_Man_t *p)
Definition: giaUtil.c:546
Vec_Que_t * vQue
Definition: giaBalAig.c:46
static void Vec_FltFillExtra(Vec_Flt_t *p, int nSize, float Fill)
Definition: vecFlt.h:470
static int Hash_Int2ObjInc(Hash_IntMan_t *p, int i)
Definition: vecHash.h:67
void Dam_ManMultiAig_rec(Dam_Man_t *pMan, Gia_Man_t *pNew, Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalAig.c:674
static int Gia_ObjIsAndReal(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:426
Gia_Man_t * Gia_ManDup(Gia_Man_t *p)
Definition: giaDup.c:552
void Gia_ManStop(Gia_Man_t *p)
Definition: giaMan.c:77
static void Vec_FltWriteEntry(Vec_Flt_t *p, int i, float Entry)
Definition: vecFlt.h:364
int nGain
Definition: giaBalAig.c:52
#define Gia_ManForEachCo(p, pObj, i)
Definition: gia.h:1022
void Gia_ManSuperCollect(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalAig.c:159
void Gia_ManPrintStats(Gia_Man_t *p, Gps_Par_t *pPars)
Definition: giaMan.c:389
void Gia_ManSimplifyXor(Vec_Int_t *vSuper)
FUNCTION DEFINITIONS ///.
Definition: giaBalAig.c:78
static int Gia_ObjFaninC1(Gia_Obj_t *pObj)
Definition: gia.h:452
static int Gia_ManAppendCo(Gia_Man_t *p, int iLit0)
Definition: gia.h:703
static Llb_Mgr_t * p
Definition: llb3Image.c:950
int Gia_ManHashXor(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:658
static void Vec_IntFillExtra(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:376
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
int nLevelMax
Definition: giaBalAig.c:49
static int Vec_FltCap(Vec_Flt_t *p)
Definition: vecFlt.h:310
void Gia_ManSuperCollectAnd_rec(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalAig.c:144
void Gia_ManCreateGate(Gia_Man_t *pNew, Gia_Obj_t *pObj, Vec_Int_t *vSuper)
Definition: giaBalAig.c:204
Vec_Int_t * vVisit
Definition: giaBalAig.c:45
static void Gia_ObjSetGateLevel(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:509
static float Vec_QueTopPriority(Vec_Que_t *p)
Definition: vecQue.h:143
static int Gia_ManAppendCi(Gia_Man_t *p)
Definition: gia.h:583
int Gia_ManLevelWithBoxes(Gia_Man_t *p)
Definition: giaTim.c:469
static int Hash_IntObjData2(Hash_IntMan_t *p, int i)
Definition: vecHash.h:65
int nDivs
Definition: giaBalAig.c:50
unsigned * pMuxes
Definition: gia.h:104
Gia_Man_t * Dam_ManAreaBalanceInt(Gia_Man_t *pGia, Vec_Int_t *vCiLevels, int nNewNodesMax, int fVerbose, int fVeryVerbose)
Definition: giaBalAig.c:934
typedefABC_NAMESPACE_HEADER_START struct Vec_Que_t_ Vec_Que_t
INCLUDES ///.
Definition: vecQue.h:40
int Gia_ManSetLevels(Gia_Man_t *p, Vec_Int_t *vCiLevels)
Definition: giaUtil.c:558
static int Gia_ObjRefNum(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:521
void Abc_QuickSortCostData(int *pCosts, int nSize, int fDecrease, word *pData, int *pResult)
Definition: utilSort.c:710
static Vec_Flt_t * Vec_FltAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecFlt.h:78
static int Gia_ObjIsBuf(Gia_Obj_t *pObj)
Definition: gia.h:427
Gia_Man_t * Gia_ManBalance(Gia_Man_t *p, int fSimpleAnd, int fVerbose)
Definition: giaBalAig.c:365
void Dam_ManCollectSets_rec(Dam_Man_t *p, int Id)
Definition: giaBalAig.c:430
void Gia_ManSetRegNum(Gia_Man_t *p, int nRegs)
Definition: giaMan.c:628
static int Vec_QuePop(Vec_Que_t *p)
Definition: vecQue.h:234
static abctime Abc_Clock()
Definition: abc_global.h:279
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
static int Dam_ObjHand(Dam_Man_t *p, int i)
Definition: giaBalAig.c:56
static void Vec_IntSort(Vec_Int_t *p, int fReverse)
Definition: vecInt.h:1293
static Vec_Int_t * Vec_IntStartFull(int nSize)
Definition: vecInt.h:119
static void Vec_FltFreeP(Vec_Flt_t **p)
Definition: vecFlt.h:235
static Gia_Obj_t * Gia_ManObj(Gia_Man_t *p, int v)
Definition: gia.h:402
static int Abc_LitNotCond(int Lit, int c)
Definition: abc_global.h:267
Vec_Int_t * vStore
Definition: gia.h:190
static void Vec_FltPush(Vec_Flt_t *p, float Entry)
Definition: vecFlt.h:528
Definition: gia.h:75
void Gia_ManSimplifyAnd(Vec_Int_t *vSuper)
Definition: giaBalAig.c:98
Gia_Man_t * Gia_ManDupNoMuxes(Gia_Man_t *p)
Definition: giaMuxes.c:159
Vec_Int_t * vNodStore
Definition: giaBalAig.c:41
int nGainX
Definition: giaBalAig.c:53
Gia_Man_t * Gia_ManBalanceInt(Gia_Man_t *p)
Definition: giaBalAig.c:315
int Gia_ManBalanceGate(Gia_Man_t *pNew, Gia_Obj_t *pObj, Vec_Int_t *vSuper, int *pLits, int nLits)
Definition: giaBalAig.c:228
Vec_Int_t * vNod2Set
Definition: giaBalAig.c:38
static Gia_Obj_t * Gia_ObjChild1(Gia_Obj_t *pObj)
Definition: gia.h:458
static void Vec_IntGrow(Vec_Int_t *p, int nCapMin)
Definition: bblif.c:336
#define Gia_ManForEachCi(p, pObj, i)
Definition: gia.h:1016
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
void Dam_ManUpdate(Dam_Man_t *p, int iDiv)
Definition: giaBalAig.c:858
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
static void Vec_QueFreeP(Vec_Que_t **p)
Definition: vecQue.h:89
void Dam_ManCreateMultiRefs(Dam_Man_t *p, Vec_Int_t **pvRefsAnd, Vec_Int_t **pvRefsXor)
Definition: giaBalAig.c:502
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
static int Gia_ObjLevel(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:501
static Vec_Int_t * Vec_IntStart(int nSize)
Definition: bblif.c:172
static int Abc_LitIsCompl(int Lit)
Definition: abc_global.h:265
static Gia_Obj_t * Gia_ObjFanin0(Gia_Obj_t *pObj)
Definition: gia.h:454
char * pName
Definition: gia.h:97
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
void Dam_PrintDiv(Dam_Man_t *p, int iDiv)
Definition: giaBalAig.c:761
void Dam_ManFree(Dam_Man_t *p)
Definition: giaBalAig.c:404
static int Gia_ObjFanin1Copy(Gia_Obj_t *pObj)
Definition: gia.h:482
static void Vec_IntAddToEntry(Vec_Int_t *p, int i, int Addition)
Definition: bblif.c:302
Dam_Man_t * Dam_ManAlloc(Gia_Man_t *pGia)
Definition: giaBalAig.c:395
Gia_Man_t * Gia_ManDupNormalize(Gia_Man_t *p)
Definition: giaTim.c:134
static int Gia_ManAppendBuf(Gia_Man_t *p, int iLit)
Definition: gia.h:694
int Dam_ManDivSlack(Dam_Man_t *p, int iLit0, int iLit1, int LevR)
Definition: giaBalAig.c:495
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
static void Hash_IntManStop(Hash_IntMan_t *p)
Definition: vecHash.h:95
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
static void Vec_IntFill(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:356
void Gia_ManHashStart(Gia_Man_t *p)
Definition: giaHash.c:117
char * pSpec
Definition: gia.h:98
static int Vec_IntPop(Vec_Int_t *p)
Gia_Man_t * Gia_ManStart(int nObjsMax)
DECLARATIONS ///.
Definition: giaMan.c:52
Gia_Man_t * Gia_ManDupMuxes(Gia_Man_t *p, int Limit)
Definition: giaMuxes.c:96
static void Vec_IntUpdateEntry(Vec_Int_t *p, int i, int Value)
Definition: vecInt.h:468
static int Gia_ObjIsXor(Gia_Obj_t *pObj)
Definition: gia.h:423
#define Gia_ManForEachAnd(p, pObj, i)
Definition: gia.h:1002
void Dam_ManCreatePairs(Dam_Man_t *p, int fVerbose)
Definition: giaBalAig.c:528
int Gia_ManHashXorReal(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:465
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
static void Vec_IntAppend(Vec_Int_t *vVec1, Vec_Int_t *vVec2)
void * pManTime
Definition: gia.h:165
char * sprintf()
static int Gia_ObjId(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:410
typedefABC_NAMESPACE_IMPL_START struct Dam_Man_t_ Dam_Man_t
DECLARATIONS ///.
Definition: giaBalAig.c:34
void Gia_ManFillValue(Gia_Man_t *p)
Definition: giaUtil.c:328
static int * Dam_ObjSet(Dam_Man_t *p, int i)
Definition: giaBalAig.c:57
void Gia_ManTransferTiming(Gia_Man_t *p, Gia_Man_t *pGia)
Definition: giaIf.c:1912
Gia_Man_t * Gia_ManAreaBalance(Gia_Man_t *p, int fSimpleAnd, int nNewNodesMax, int fVerbose, int fVeryVerbose)
Definition: giaBalAig.c:968
static int * Hash_Int2ManLookup(Hash_IntMan_t *p, int iData0, int iData1)
Definition: vecHash.h:134
#define Vec_IntForEachEntryStart(vVec, Entry, i, Start)
Definition: vecInt.h:56
static void Vec_IntFreeP(Vec_Int_t **p)
Definition: vecInt.h:289
static int pPerm[13719]
Definition: rwrTemp.c:32
static int Hash_Int2ManInsert(Hash_IntMan_t *p, int iData0, int iData1, int iData2)
Definition: vecHash.h:144
static int Gia_ObjFanin0Copy(Gia_Obj_t *pObj)
Definition: gia.h:481
int nAnds
Definition: giaBalAig.c:51
static Gia_Obj_t * Gia_ObjFanin2(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:456
#define Gia_ManForEachObjVec(vVec, p, pObj, i)
Definition: gia.h:988
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
static int Abc_LitNot(int Lit)
Definition: abc_global.h:266
static void Vec_FltAddToEntry(Vec_Flt_t *p, int i, float Addition)
Definition: vecFlt.h:381
int Dam_ManUpdateNode(Dam_Man_t *p, int iObj, int iLit0, int iLit1, int iLitNew, Vec_Int_t *vDivs)
Definition: giaBalAig.c:799
void Gia_ManSuperCollectXor_rec(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalAig.c:128
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Hash_IntMan_t * vHash
Definition: giaBalAig.c:47
static int Gia_ManHasMapping(Gia_Man_t *p)
Definition: gia.h:951
static int Gia_IsComplement(Gia_Obj_t *p)
Definition: gia.h:380
void Dam_PrintQue(Dam_Man_t *p)
Definition: giaBalAig.c:783
void Dam_ManCollectSets(Dam_Man_t *p)
Definition: giaBalAig.c:468
void * Dsm_ManDeriveGia(void *p, int fUseMuxes)
Definition: dauGia.c:471
static float ** Vec_FltArrayP(Vec_Flt_t *p)
Definition: vecFlt.h:278
static void Vec_IntShrink(Vec_Int_t *p, int nSizeNew)
Definition: bblif.c:435
unsigned fMark0
Definition: gia.h:79
#define ABC_FREE(obj)
Definition: abc_global.h:232
Definition: gia.h:95
int Gia_ManIsNormalized(Gia_Man_t *p)
Definition: giaTim.c:109
static int Gia_ObjIsAnd(Gia_Obj_t *pObj)
Definition: gia.h:422
Vec_Int_t * vSetStore
Definition: giaBalAig.c:40
void Gia_ManBalance_rec(Gia_Man_t *pNew, Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalAig.c:278
static Gia_Obj_t * Gia_ManConst0(Gia_Man_t *p)
Definition: gia.h:400
static void Vec_QueUpdate(Vec_Que_t *p, int v)
Definition: vecQue.h:199
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
static int Abc_Lit2Var(int Lit)
Definition: abc_global.h:264
static int Gia_ObjFaninId0p(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:463
typedefABC_NAMESPACE_HEADER_START struct Vec_Flt_t_ Vec_Flt_t
INCLUDES ///.
Definition: vecFlt.h:42
static Gia_Obj_t * Gia_ObjFanin1(Gia_Obj_t *pObj)
Definition: gia.h:455
static int Vec_QueIsMember(Vec_Que_t *p, int v)
Definition: vecQue.h:216
#define Gia_ManForEachBuf(p, pObj, i)
Definition: gia.h:998
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
#define assert(ex)
Definition: util_old.h:213
static int * Vec_IntEntryP(Vec_Int_t *p, int i)
Definition: vecInt.h:417
#define Vec_IntForEachEntryStartStop(vVec, Entry, i, Start, Stop)
Definition: vecInt.h:60
static int Gia_ObjFaninId2(Gia_Man_t *p, int ObjId)
Definition: gia.h:462
unsigned Value
Definition: gia.h:87
int Gia_ManHashMuxReal(Gia_Man_t *p, int iLitC, int iLit1, int iLit0)
Definition: giaHash.c:517
static float Vec_FltEntry(Vec_Flt_t *p, int i)
Definition: vecFlt.h:342
Vec_Int_t * vLevels
Definition: gia.h:115
static int Hash_IntObjData1(Hash_IntMan_t *p, int i)
Definition: vecHash.h:64
static int Hash_IntObjData0(Hash_IntMan_t *p, int i)
Definition: vecHash.h:63
static int Gia_ObjFaninC0(Gia_Obj_t *pObj)
Definition: gia.h:451
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Vec_Int_t * vDivLevR
Definition: giaBalAig.c:44
Vec_Int_t * vSuper
Definition: gia.h:189
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
ABC_INT64_T abctime
Definition: abc_global.h:278
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
static int Vec_FltSize(Vec_Flt_t *p)
Definition: vecFlt.h:294
Gia_Man_t * Gia_ManCleanup(Gia_Man_t *p)
Definition: giaScl.c:84
char * Abc_UtilStrsav(char *s)
Definition: starter.c:47
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
static int Gia_ObjFaninId1(Gia_Obj_t *pObj, int ObjId)
Definition: gia.h:461
static Vec_Que_t * Vec_QueAlloc(int nCap)
MACRO DEFINITIONS ///.
Definition: vecQue.h:71
static int Gia_ObjIsMux(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:425
static int Gia_ManAppendXorReal(Gia_Man_t *p, int iLit0, int iLit1)
Definition: gia.h:639
Vec_Int_t * vDiv2Nod
Definition: giaBalAig.c:39
int Gia_ManHashAnd(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:572
static void Vec_QuePush(Vec_Que_t *p, int v)
Definition: vecQue.h:221
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
static void Vec_QueSetPriority(Vec_Que_t *p, float **pCosts)
Definition: vecQue.h:95
abctime clkStart
Definition: giaBalAig.c:48
Vec_Int_t * Gia_ManReverseLevel(Gia_Man_t *p)
Definition: giaUtil.c:595
static int Gia_ObjFaninId0(Gia_Obj_t *pObj, int ObjId)
Definition: gia.h:460
void Gia_ManHashStop(Gia_Man_t *p)
Definition: giaHash.c:142
static int Gia_ManRegNum(Gia_Man_t *p)
Definition: gia.h:387