abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaBalLut.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 
26 ABC_NAMESPACE_IMPL_START
27 
28 
29 ////////////////////////////////////////////////////////////////////////
30 /// DECLARATIONS ///
31 ////////////////////////////////////////////////////////////////////////
32 
33 #define BAL_LEAF_MAX 6
34 #define BAL_CUT_MAX 8
35 #define BAL_SUPER 50
36 #define BAL_NO_LEAF 31
37 #define BAL_NO_FUNC 134217727 // (1<<27)-1
38 
39 typedef struct Bal_Cut_t_ Bal_Cut_t;
40 struct Bal_Cut_t_
41 {
42  word Sign; // signature
43  int Delay; // delay
44  unsigned iFunc : 27; // function (BAL_NO_FUNC)
45  unsigned nLeaves : 5; // leaf number (Bal_NO_LEAF)
46  int pLeaves[BAL_LEAF_MAX]; // leaves
47 };
48 
49 // operation manager
50 typedef struct Bal_Man_t_ Bal_Man_t;
51 struct Bal_Man_t_
52 {
53  Gia_Man_t * pGia; // user AIG
54  int nLutSize; // LUT size
55  int nCutNum; // cut number
56  int fCutMin; // cut minimization
57  int fVerbose; // verbose
58  Gia_Man_t * pNew; // derived AIG
59  Vec_Int_t * vCosts; // cost of supergate nodes
60  Vec_Ptr_t * vCutSets; // object cutsets
61  abctime clkStart; // starting the clock
62 };
63 
64 static inline Bal_Man_t * Bal_GiaMan( Gia_Man_t * p ) { return (Bal_Man_t *)p->pData; }
65 
66 static inline int Bal_ObjCost( Bal_Man_t * p, int i ) { return Vec_IntEntry(p->vCosts, i); }
67 static inline int Bal_LitCost( Bal_Man_t * p, int i ) { return Bal_ObjCost(p, Abc_Lit2Var(i)); }
68 static inline int Bal_ObjDelay( Bal_Man_t * p, int i ) { return Bal_ObjCost(p, i) >> 4; }
69 static inline int Bal_LitDelay( Bal_Man_t * p, int i ) { return Bal_ObjDelay(p, Abc_Lit2Var(i)); }
70 
71 ////////////////////////////////////////////////////////////////////////
72 /// FUNCTION DEFINITIONS ///
73 ////////////////////////////////////////////////////////////////////////
74 
75 /**Function*************************************************************
76 
77  Synopsis []
78 
79  Description []
80 
81  SideEffects []
82 
83  SeeAlso []
84 
85 ***********************************************************************/
86 Bal_Man_t * Bal_ManAlloc( Gia_Man_t * pGia, Gia_Man_t * pNew, int nLutSize, int nCutNum, int fVerbose )
87 {
88  Bal_Man_t * p;
89  p = ABC_CALLOC( Bal_Man_t, 1 );
90  p->clkStart = Abc_Clock();
91  p->pGia = pGia;
92  p->pNew = pNew;
93  p->nLutSize = nLutSize;
94  p->nCutNum = nCutNum;
95  p->fVerbose = fVerbose;
96  p->vCosts = Vec_IntAlloc( 3 * Gia_ManObjNum(pGia) / 2 );
97  p->vCutSets = Vec_PtrAlloc( 3 * Gia_ManObjNum(pGia) / 2 );
98  Vec_IntFill( p->vCosts, Gia_ManObjNum(pNew), 0 );
99  Vec_PtrFill( p->vCutSets, Gia_ManObjNum(pNew), NULL );
100  pNew->pData = p;
101  return p;
102 }
103 void Bal_ManFree( Bal_Man_t * p )
104 {
105  Vec_PtrFreeFree( p->vCutSets );
106  Vec_IntFree( p->vCosts );
107  ABC_FREE( p );
108 }
109 
110 /**Function*************************************************************
111 
112  Synopsis []
113 
114  Description []
115 
116  SideEffects []
117 
118  SeeAlso []
119 
120 ***********************************************************************/
121 static inline int Bal_CutCountBits( word i )
122 {
123  i = i - ((i >> 1) & 0x5555555555555555);
124  i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
125  i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);
126  return (i*(0x0101010101010101))>>56;
127 }
128 static inline word Bal_CutGetSign( int * pLeaves, int nLeaves )
129 {
130  word Sign = 0; int i;
131  for ( i = 0; i < nLeaves; i++ )
132  Sign |= ((word)1) << (pLeaves[i] & 0x3F);
133  return Sign;
134 }
135 static inline int Bal_CutCreateUnit( Bal_Cut_t * p, int i, int Delay )
136 {
137  p->iFunc = 2;
138  p->Delay = Delay;
139  p->nLeaves = 1;
140  p->pLeaves[0] = i;
141  p->Sign = ((word)1) << (i & 0x3F);
142  return 1;
143 }
144 static inline int Bal_ManPrepareSet( Bal_Man_t * p, int iObj, int Index, int fUnit, Bal_Cut_t ** ppCutSet )
145 {
146  static Bal_Cut_t CutTemp[3]; int i;
147  if ( Vec_PtrEntry(p->vCutSets, iObj) == NULL || fUnit )
148  return Bal_CutCreateUnit( (*ppCutSet = CutTemp + Index), iObj, Bal_ObjDelay(p, iObj)+1 );
149  *ppCutSet = (Bal_Cut_t *)Vec_PtrEntry(p->vCutSets, iObj);
150  for ( i = 0; i < p->nCutNum; i++ )
151  if ( (*ppCutSet)[i].nLeaves == BAL_NO_LEAF )
152  return i;
153  return i;
154 }
155 
156 
157 /**Function*************************************************************
158 
159  Synopsis [Check correctness of cuts.]
160 
161  Description []
162 
163  SideEffects []
164 
165  SeeAlso []
166 
167 ***********************************************************************/
168 static inline int Bal_CutCheck( Bal_Cut_t * pBase, Bal_Cut_t * pCut ) // check if pCut is contained in pBase
169 {
170  int nSizeB = pBase->nLeaves;
171  int nSizeC = pCut->nLeaves;
172  int i, * pB = pBase->pLeaves;
173  int k, * pC = pCut->pLeaves;
174  for ( i = 0; i < nSizeC; i++ )
175  {
176  for ( k = 0; k < nSizeB; k++ )
177  if ( pC[i] == pB[k] )
178  break;
179  if ( k == nSizeB )
180  return 0;
181  }
182  return 1;
183 }
184 static inline int Bal_SetCheckArray( Bal_Cut_t ** ppCuts, int nCuts )
185 {
186  Bal_Cut_t * pCut0, * pCut1;
187  int i, k, m, n, Value;
188  assert( nCuts > 0 );
189  for ( i = 0; i < nCuts; i++ )
190  {
191  pCut0 = ppCuts[i];
192  assert( pCut0->nLeaves <= BAL_LEAF_MAX );
193  assert( pCut0->Sign == Bal_CutGetSign(pCut0->pLeaves, pCut0->nLeaves) );
194  // check duplicates
195  for ( m = 0; m < (int)pCut0->nLeaves; m++ )
196  for ( n = m + 1; n < (int)pCut0->nLeaves; n++ )
197  assert( pCut0->pLeaves[m] < pCut0->pLeaves[n] );
198  // check pairs
199  for ( k = 0; k < nCuts; k++ )
200  {
201  pCut1 = ppCuts[k];
202  if ( pCut0 == pCut1 )
203  continue;
204  // check containments
205  Value = Bal_CutCheck( pCut0, pCut1 );
206  assert( Value == 0 );
207  }
208  }
209  return 1;
210 }
211 
212 /**Function*************************************************************
213 
214  Synopsis []
215 
216  Description []
217 
218  SideEffects []
219 
220  SeeAlso []
221 
222 ***********************************************************************/
223 static inline int Bal_CutMergeOrder( Bal_Cut_t * pCut0, Bal_Cut_t * pCut1, Bal_Cut_t * pCut, int nLutSize )
224 {
225  int nSize0 = pCut0->nLeaves;
226  int nSize1 = pCut1->nLeaves;
227  int i, * pC0 = pCut0->pLeaves;
228  int k, * pC1 = pCut1->pLeaves;
229  int c, * pC = pCut->pLeaves;
230  // the case of the largest cut sizes
231  if ( nSize0 == nLutSize && nSize1 == nLutSize )
232  {
233  for ( i = 0; i < nSize0; i++ )
234  {
235  if ( pC0[i] != pC1[i] ) return 0;
236  pC[i] = pC0[i];
237  }
238  pCut->nLeaves = nLutSize;
239  pCut->iFunc = BAL_NO_FUNC;
240  pCut->Sign = pCut0->Sign | pCut1->Sign;
241  pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay );
242  return 1;
243  }
244  // compare two cuts with different numbers
245  i = k = c = 0;
246  while ( 1 )
247  {
248  if ( c == nLutSize ) return 0;
249  if ( pC0[i] < pC1[k] )
250  {
251  pC[c++] = pC0[i++];
252  if ( i >= nSize0 ) goto FlushCut1;
253  }
254  else if ( pC0[i] > pC1[k] )
255  {
256  pC[c++] = pC1[k++];
257  if ( k >= nSize1 ) goto FlushCut0;
258  }
259  else
260  {
261  pC[c++] = pC0[i++]; k++;
262  if ( i >= nSize0 ) goto FlushCut1;
263  if ( k >= nSize1 ) goto FlushCut0;
264  }
265  }
266 
267 FlushCut0:
268  if ( c + nSize0 > nLutSize + i ) return 0;
269  while ( i < nSize0 )
270  pC[c++] = pC0[i++];
271  pCut->nLeaves = c;
272  pCut->iFunc = BAL_NO_FUNC;
273  pCut->Sign = pCut0->Sign | pCut1->Sign;
274  pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay );
275  return 1;
276 
277 FlushCut1:
278  if ( c + nSize1 > nLutSize + k ) return 0;
279  while ( k < nSize1 )
280  pC[c++] = pC1[k++];
281  pCut->nLeaves = c;
282  pCut->iFunc = BAL_NO_FUNC;
283  pCut->Sign = pCut0->Sign | pCut1->Sign;
284  pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay );
285  return 1;
286 }
287 static inline int Bal_CutMergeOrderMux( Bal_Cut_t * pCut0, Bal_Cut_t * pCut1, Bal_Cut_t * pCut2, Bal_Cut_t * pCut, int nLutSize )
288 {
289  int x0, i0 = 0, nSize0 = pCut0->nLeaves, * pC0 = pCut0->pLeaves;
290  int x1, i1 = 0, nSize1 = pCut1->nLeaves, * pC1 = pCut1->pLeaves;
291  int x2, i2 = 0, nSize2 = pCut2->nLeaves, * pC2 = pCut2->pLeaves;
292  int xMin, c = 0, * pC = pCut->pLeaves;
293  while ( 1 )
294  {
295  x0 = (i0 == nSize0) ? ABC_INFINITY : pC0[i0];
296  x1 = (i1 == nSize1) ? ABC_INFINITY : pC1[i1];
297  x2 = (i2 == nSize2) ? ABC_INFINITY : pC2[i2];
298  xMin = Abc_MinInt( Abc_MinInt(x0, x1), x2 );
299  if ( xMin == ABC_INFINITY ) break;
300  if ( c == nLutSize ) return 0;
301  pC[c++] = xMin;
302  if (x0 == xMin) i0++;
303  if (x1 == xMin) i1++;
304  if (x2 == xMin) i2++;
305  }
306  pCut->nLeaves = c;
307  pCut->iFunc = BAL_NO_FUNC;
308  pCut->Sign = pCut0->Sign | pCut1->Sign | pCut2->Sign;
309  pCut->Delay = Abc_MaxInt( pCut0->Delay, Abc_MaxInt(pCut1->Delay, pCut2->Delay) );
310  return 1;
311 }
312 static inline int Bal_SetCutIsContainedOrder( Bal_Cut_t * pBase, Bal_Cut_t * pCut ) // check if pCut is contained in pBase
313 {
314  int i, nSizeB = pBase->nLeaves;
315  int k, nSizeC = pCut->nLeaves;
316  if ( nSizeB == nSizeC )
317  {
318  for ( i = 0; i < nSizeB; i++ )
319  if ( pBase->pLeaves[i] != pCut->pLeaves[i] )
320  return 0;
321  return 1;
322  }
323  assert( nSizeB > nSizeC );
324  if ( nSizeC == 0 )
325  return 1;
326  for ( i = k = 0; i < nSizeB; i++ )
327  {
328  if ( pBase->pLeaves[i] > pCut->pLeaves[k] )
329  return 0;
330  if ( pBase->pLeaves[i] == pCut->pLeaves[k] )
331  {
332  if ( ++k == nSizeC )
333  return 1;
334  }
335  }
336  return 0;
337 }
338 static inline int Bal_SetLastCutIsContained( Bal_Cut_t ** pCuts, int nCuts )
339 {
340  int i;
341  for ( i = 0; i < nCuts; i++ )
342  if ( pCuts[i]->nLeaves <= pCuts[nCuts]->nLeaves && (pCuts[i]->Sign & pCuts[nCuts]->Sign) == pCuts[i]->Sign && Bal_SetCutIsContainedOrder(pCuts[nCuts], pCuts[i]) )
343  return 1;
344  return 0;
345 }
346 static inline int Bal_SetLastCutContains( Bal_Cut_t ** pCuts, int nCuts )
347 {
348  int i, k, fChanges = 0;
349  for ( i = 0; i < nCuts; i++ )
350  if ( pCuts[nCuts]->nLeaves < pCuts[i]->nLeaves && (pCuts[nCuts]->Sign & pCuts[i]->Sign) == pCuts[nCuts]->Sign && Bal_SetCutIsContainedOrder(pCuts[i], pCuts[nCuts]) )
351  pCuts[i]->nLeaves = BAL_NO_LEAF, fChanges = 1;
352  if ( !fChanges )
353  return nCuts;
354  for ( i = k = 0; i <= nCuts; i++ )
355  {
356  if ( pCuts[i]->nLeaves == BAL_NO_LEAF )
357  continue;
358  if ( k < i )
359  ABC_SWAP( Bal_Cut_t *, pCuts[k], pCuts[i] );
360  k++;
361  }
362  return k - 1;
363 }
364 static inline int Bal_CutCompareArea( Bal_Cut_t * pCut0, Bal_Cut_t * pCut1 )
365 {
366  if ( pCut0->Delay < pCut1->Delay ) return -1;
367  if ( pCut0->Delay > pCut1->Delay ) return 1;
368  if ( pCut0->nLeaves < pCut1->nLeaves ) return -1;
369  if ( pCut0->nLeaves > pCut1->nLeaves ) return 1;
370  return 0;
371 }
372 static inline void Bal_SetSortByDelay( Bal_Cut_t ** pCuts, int nCuts )
373 {
374  int i;
375  for ( i = nCuts; i > 0; i-- )
376  {
377  if ( Bal_CutCompareArea(pCuts[i - 1], pCuts[i]) < 0 )//!= 1 )
378  return;
379  ABC_SWAP( Bal_Cut_t *, pCuts[i - 1], pCuts[i] );
380  }
381 }
382 static inline int Bal_SetAddCut( Bal_Cut_t ** pCuts, int nCuts, int nCutNum )
383 {
384  if ( nCuts == 0 )
385  return 1;
386  nCuts = Bal_SetLastCutContains(pCuts, nCuts);
387  Bal_SetSortByDelay( pCuts, nCuts );
388  return Abc_MinInt( nCuts + 1, nCutNum - 1 );
389 }
390 
391 /**Function*************************************************************
392 
393  Synopsis []
394 
395  Description []
396 
397  SideEffects []
398 
399  SeeAlso []
400 
401 ***********************************************************************/
402 int Bal_ManDeriveCuts( Bal_Man_t * p, int iFan0, int iFan1, int iFan2, int fCompl0, int fCompl1, int fCompl2, int fUnit0, int fUnit1, int fUnit2, int fIsXor, int Target, int fSave )
403 {
404  Bal_Cut_t pCutSet[BAL_CUT_MAX], * pCutsR[BAL_CUT_MAX];
405  Bal_Cut_t * pCutSet0, * pCutSet1, * pCutSet2;
406  int nCuts0 = Bal_ManPrepareSet( p, iFan0, 0, fUnit0, &pCutSet0 );
407  int nCuts1 = Bal_ManPrepareSet( p, iFan1, 1, fUnit1, &pCutSet1 );
408  Bal_Cut_t * pCut0, * pCut0Lim = pCutSet0 + nCuts0;
409  Bal_Cut_t * pCut1, * pCut1Lim = pCutSet1 + nCuts1;
410  int i, Cost, nCutsR = 0;
411  memset( pCutSet, 0, sizeof(Bal_Cut_t) * p->nCutNum );
412  for ( i = 0; i < p->nCutNum; i++ )
413  pCutsR[i] = pCutSet + i;
414  // enumerate cuts
415  if ( iFan2 > 0 )
416  {
417  int nCuts2 = Bal_ManPrepareSet( p, iFan2, 2, fUnit2, &pCutSet2 );
418  Bal_Cut_t * pCut2, * pCut2Lim = pCutSet2 + nCuts2;
419  for ( pCut0 = pCutSet0; pCut0 < pCut0Lim; pCut0++ )
420  for ( pCut1 = pCutSet1; pCut1 < pCut1Lim; pCut1++ )
421  for ( pCut2 = pCutSet2; pCut2 < pCut2Lim; pCut2++ )
422  {
423  if ( Bal_CutCountBits(pCut0->Sign | pCut1->Sign | pCut2->Sign) > p->nLutSize )
424  continue;
425  if ( !Bal_CutMergeOrderMux(pCut0, pCut1, pCut2, pCutsR[nCutsR], p->nLutSize) )
426  continue;
427  assert( pCutsR[nCutsR]->Delay == Target );
428  if ( Bal_SetLastCutIsContained(pCutsR, nCutsR) )
429  continue;
430 // if ( p->fCutMin && Bal_CutComputeTruthMux(p, pCut0, pCut1, pCut2, fCompl0, fCompl1, fCompl2, pCutsR[nCutsR]) )
431 // pCutsR[nCutsR]->Sign = Bal_CutGetSign(pCutsR[nCutsR]->pLeaves, pCutsR[nCutsR]->nLeaves);
432  nCutsR = Bal_SetAddCut( pCutsR, nCutsR, p->nCutNum );
433  }
434  }
435  else
436  {
437  for ( pCut0 = pCutSet0; pCut0 < pCut0Lim; pCut0++ )
438  for ( pCut1 = pCutSet1; pCut1 < pCut1Lim; pCut1++ )
439  {
440  if ( Bal_CutCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
441  continue;
442  if ( !Bal_CutMergeOrder(pCut0, pCut1, pCutsR[nCutsR], p->nLutSize) )
443  continue;
444  assert( pCutsR[nCutsR]->Delay == Target );
445  if ( Bal_SetLastCutIsContained(pCutsR, nCutsR) )
446  continue;
447 // if ( p->fCutMin && Bal_CutComputeTruth(p, pCut0, pCut1, fCompl0, fCompl1, pCutsR[nCutsR], fIsXor) )
448 // pCutsR[nCutsR]->Sign = Bal_CutGetSign(pCutsR[nCutsR]->pLeaves, pCutsR[nCutsR]->nLeaves);
449  nCutsR = Bal_SetAddCut( pCutsR, nCutsR, p->nCutNum );
450  }
451  }
452  if ( nCutsR == 0 )
453  return -1;
454 //printf( "%d ", nCutsR );
455  Cost = ((pCutsR[0]->Delay << 4) | pCutsR[0]->nLeaves);
456  // verify
457  assert( nCutsR > 0 && nCutsR < p->nCutNum );
458  assert( Bal_SetCheckArray(pCutsR, nCutsR) );
459  // save cuts
460  if ( fSave && Cost >= 0 )
461  {
462  pCutSet0 = ABC_CALLOC( Bal_Cut_t, p->nCutNum );
463  Vec_PtrPush( p->vCutSets, pCutSet0 );
464  assert( Vec_PtrSize(p->vCutSets) == Gia_ManObjNum(p->pNew) );
465  for ( i = 0; i < nCutsR; i++ )
466  pCutSet0[i] = *pCutsR[i];
467  for ( ; i < p->nCutNum; i++ )
468  pCutSet0[i].nLeaves = BAL_NO_LEAF;
469  Vec_IntPush( p->vCosts, Cost );
470  assert( Vec_IntSize(p->vCosts) == Gia_ManObjNum(p->pNew) );
471  }
472  return Cost;
473 }
474 
475 /**Function*************************************************************
476 
477  Synopsis []
478 
479  Description []
480 
481  SideEffects []
482 
483  SeeAlso []
484 
485 ***********************************************************************/
486 int Bal_ManSetGateLevel( Bal_Man_t * p, Gia_Obj_t * pObjOld, int iLitNew )
487 {
488  int iFan0, iFan1, iFan2, Cost;
489  int fCompl0, fCompl1, fCompl2;
490  int fUnit0, fUnit1, fUnit2;
491  int Delay0, Delay1, Delay2, DelayMax;
492  int iObjNew = Abc_Lit2Var(iLitNew);
493  Gia_Obj_t * pObjNew = Gia_ManObj( p->pNew, iObjNew );
494  int fMux = Gia_ObjIsMux(p->pNew, pObjNew);
495  if ( iObjNew < Vec_PtrSize(p->vCutSets) )
496  return -1;
497  iFan0 = Gia_ObjFaninId0( pObjNew, iObjNew );
498  iFan1 = Gia_ObjFaninId1( pObjNew, iObjNew );
499  iFan2 = fMux ? Gia_ObjFaninId2(p->pNew, iObjNew) : 0;
500  fCompl0 = Gia_ObjFaninC0( pObjNew );
501  fCompl1 = Gia_ObjFaninC1( pObjNew );
502  fCompl2 = fMux ? Gia_ObjFaninC2(p->pNew, pObjNew) : 0;
503  Delay0 = Bal_ObjDelay( p, iFan0 );
504  Delay1 = Bal_ObjDelay( p, iFan1 );
505  Delay2 = Bal_ObjDelay( p, iFan2 );
506  DelayMax = Abc_MaxInt( Delay0, Abc_MaxInt(Delay1, Delay2) );
507  fUnit0 = (int)(Delay0 != DelayMax);
508  fUnit1 = (int)(Delay1 != DelayMax);
509  fUnit2 = (int)(Delay2 != DelayMax);
510  if ( DelayMax > 0 )
511  {
512 //printf( "A" );
513  Cost = Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, Gia_ObjIsXor(pObjNew), DelayMax, 1 );
514 //printf( "B" );
515  if ( Cost >= 0 )
516  return Cost;
517  }
518  DelayMax++;
519  fUnit0 = fUnit1 = fUnit2 = 1;
520 //printf( "A" );
521  Cost = Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, Gia_ObjIsXor(pObjNew), DelayMax, 1 );
522 //printf( "B" );
523  assert( Cost >= 0 );
524  return Cost;
525 }
526 int Bal_ManEvalTwo( Bal_Man_t * p, int iLitNew0, int iLitNew1, int iLitNew2, int fIsXor )
527 {
528  int iFan0 = Abc_Lit2Var( iLitNew0 );
529  int iFan1 = Abc_Lit2Var( iLitNew1 );
530  int iFan2 = Abc_Lit2Var( iLitNew2 );
531  int fCompl0 = Abc_LitIsCompl( iLitNew0 );
532  int fCompl1 = Abc_LitIsCompl( iLitNew1 );
533  int fCompl2 = Abc_LitIsCompl( iLitNew2 );
534  int Delay0 = Bal_ObjDelay( p, iFan0 );
535  int Delay1 = Bal_ObjDelay( p, iFan1 );
536  int Delay2 = Bal_ObjDelay( p, iFan2 );
537  int DelayMax = Abc_MaxInt( Delay0, Abc_MaxInt(Delay1, Delay2) );
538  int fUnit0 = (int)(Delay0 != DelayMax);
539  int fUnit1 = (int)(Delay1 != DelayMax);
540  int fUnit2 = (int)(Delay2 != DelayMax);
541  if ( DelayMax == 0 )
542  return -1;
543  return Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, fIsXor, DelayMax, 0 );
544 }
545 
546 /**Function*************************************************************
547 
548  Synopsis [Sort literals by their cost.]
549 
550  Description []
551 
552  SideEffects []
553 
554  SeeAlso []
555 
556 ***********************************************************************/
557 static inline void Vec_IntSelectSortCostLit( Vec_Int_t * vSuper, Vec_Int_t * vCosts )
558 {
559  int * pArray = Vec_IntArray(vSuper);
560  int nSize = Vec_IntSize(vSuper);
561  int i, j, best_i;
562  for ( i = 0; i < nSize-1; i++ )
563  {
564  best_i = i;
565  for ( j = i+1; j < nSize; j++ )
566  if ( Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[j])) > Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[best_i])) )
567  best_i = j;
568  ABC_SWAP( int, pArray[i], pArray[best_i] );
569  }
570 }
571 static inline void Vec_IntPushOrderCost( Vec_Int_t * vSuper, Vec_Int_t * vCosts, int iLit )
572 {
573  int i, nSize, * pArray;
574  Vec_IntPush( vSuper, iLit );
575  pArray = Vec_IntArray(vSuper);
576  nSize = Vec_IntSize(vSuper);
577  for ( i = nSize-1; i > 0; i-- )
578  {
579  if ( Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[i])) <= Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[i - 1])) )
580  return;
581  ABC_SWAP( int, pArray[i], pArray[i - 1] );
582  }
583 }
584 static inline int Vec_IntFindFirstSameDelayAsLast( Bal_Man_t * p, Vec_Int_t * vSuper )
585 {
586  int i, DelayCur, Delay = Bal_LitDelay( p, Vec_IntEntryLast(vSuper) );
587  assert( Vec_IntSize(vSuper) > 1 );
588  for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
589  {
590  DelayCur = Bal_LitDelay( p, Vec_IntEntry(vSuper, i-1) );
591  assert( DelayCur >= Delay );
592  if ( DelayCur > Delay )
593  return i;
594  }
595  return i;
596 }
597 
598 
599 /**Function*************************************************************
600 
601  Synopsis [Select the best pair to merge.]
602 
603  Description []
604 
605  SideEffects []
606 
607  SeeAlso []
608 
609 ***********************************************************************/
610 static inline int Bal_ManFindBestPair( Bal_Man_t * p, Vec_Int_t * vSuper, Gia_Obj_t * pObj )
611 {
612  int * pSuper = Vec_IntArray(vSuper);
613  int iBeg = Vec_IntFindFirstSameDelayAsLast( p, vSuper );
614  int iEnd = Vec_IntSize(vSuper)-1;
615  int i, k, iBest = -1, kBest = -1, BestCost = ABC_INFINITY, Cost;
616  assert( iBeg <= iEnd );
617  // check if we can add to the higher levels without increasing cost
618  for ( k = iBeg-1; k >= 0; k-- )
619  for ( i = iEnd; i >= iBeg; i-- )
620  {
621  Cost = Bal_ManEvalTwo( p, pSuper[i], pSuper[k], 0, Gia_ObjIsXor(pObj) );
622  if ( Cost == -1 )
623  continue;
624  if ( Cost == Bal_LitCost(p, pSuper[k]) )
625  {
626 // printf( "A" );
627  return (k << 16)|i;
628  }
629  if ( BestCost > Cost )
630  BestCost = Cost, iBest = i, kBest = k;
631  }
632  if ( BestCost != ABC_INFINITY && (BestCost >> 4) == Bal_LitDelay(p, pSuper[kBest]) )
633  {
634 // printf( "B" );
635  return (kBest << 16)|iBest;
636  }
637  // check if some can be added to lowest level without increasing cost
638  BestCost = ABC_INFINITY;
639  for ( i = iBeg; i <= iEnd; i++ )
640  for ( k = i+1; k <= iEnd; k++ )
641  {
642  Cost = Bal_ManEvalTwo( p, pSuper[i], pSuper[k], 0, Gia_ObjIsXor(pObj) );
643  if ( Cost == -1 )
644  continue;
645  if ( Cost == Abc_MaxInt(Bal_LitCost(p, pSuper[i]), Bal_LitCost(p, pSuper[k])) )
646  {
647 // printf( "C" );
648  return (k << 16)|i;
649  }
650  if ( BestCost > Cost )
651  BestCost = Cost, iBest = i, kBest = k;
652  }
653  if ( BestCost != ABC_INFINITY )
654  {
655 // printf( "D" );
656  return (kBest << 16)|iBest;
657  }
658 // printf( "E" );
659  // group pairs from lowest level based on proximity
660  return (iEnd << 16)|(iEnd-1);
661 }
662 
663 /**Function*************************************************************
664 
665  Synopsis [Simplify multi-input AND/XOR.]
666 
667  Description []
668 
669  SideEffects []
670 
671  SeeAlso []
672 
673 ***********************************************************************/
674 static inline void Gia_ManSimplifyXor( Vec_Int_t * vSuper )
675 {
676  int i, k = 0, Prev = -1, This, fCompl = 0;
677  Vec_IntForEachEntry( vSuper, This, i )
678  {
679  if ( This == 0 )
680  continue;
681  if ( This == 1 )
682  fCompl ^= 1;
683  else if ( Prev != This )
684  Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
685  else
686  Prev = -1, k--;
687  }
688  Vec_IntShrink( vSuper, k );
689  if ( Vec_IntSize( vSuper ) == 0 )
690  Vec_IntPush( vSuper, fCompl );
691  else if ( fCompl )
692  Vec_IntWriteEntry( vSuper, 0, Abc_LitNot(Vec_IntEntry(vSuper, 0)) );
693 }
694 static inline void Gia_ManSimplifyAnd( Vec_Int_t * vSuper )
695 {
696  int i, k = 0, Prev = -1, This;
697  Vec_IntForEachEntry( vSuper, This, i )
698  {
699  if ( This == 0 )
700  { Vec_IntFill(vSuper, 1, 0); return; }
701  if ( This == 1 )
702  continue;
703  if ( Prev == -1 || Abc_Lit2Var(Prev) != Abc_Lit2Var(This) )
704  Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
705  else if ( Prev != This )
706  { Vec_IntFill(vSuper, 1, 0); return; }
707  }
708  Vec_IntShrink( vSuper, k );
709  if ( Vec_IntSize( vSuper ) == 0 )
710  Vec_IntPush( vSuper, 1 );
711 }
712 
713 /**Function*************************************************************
714 
715  Synopsis [Collect multi-input AND/XOR.]
716 
717  Description []
718 
719  SideEffects []
720 
721  SeeAlso []
722 
723 ***********************************************************************/
724 static inline void Gia_ManSuperCollectXor_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
725 {
726  assert( !Gia_IsComplement(pObj) );
727  if ( !Gia_ObjIsXor(pObj) ||
728 // Gia_ObjRefNum(p, pObj) > 1 ||
729  Gia_ObjRefNum(p, pObj) > 3 ||
730 // (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
731  Vec_IntSize(p->vSuper) > BAL_SUPER )
732  {
733  Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
734  return;
735  }
736  assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
737  Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj) );
738  Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj) );
739 }
740 static inline void Gia_ManSuperCollectAnd_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
741 {
742  if ( Gia_IsComplement(pObj) ||
743  !Gia_ObjIsAndReal(p, pObj) ||
744 // Gia_ObjRefNum(p, pObj) > 1 ||
745  Gia_ObjRefNum(p, pObj) > 3 ||
746 // (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
747  Vec_IntSize(p->vSuper) > BAL_SUPER )
748  {
749  Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
750  return;
751  }
752  Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) );
753  Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) );
754 }
755 static inline void Gia_ManSuperCollect( Gia_Man_t * p, Gia_Obj_t * pObj )
756 {
757 // int nSize;
758  if ( p->vSuper == NULL )
759  p->vSuper = Vec_IntAlloc( 1000 );
760  else
761  Vec_IntClear( p->vSuper );
762  if ( Gia_ObjIsXor(pObj) )
763  {
764  assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
765  Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj) );
766  Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj) );
767 // nSize = Vec_IntSize(vSuper);
768  Vec_IntSort( p->vSuper, 0 );
769  Gia_ManSimplifyXor( p->vSuper );
770 // if ( nSize != Vec_IntSize(vSuper) )
771 // printf( "X %d->%d ", nSize, Vec_IntSize(vSuper) );
772  }
773  else if ( Gia_ObjIsAndReal(p, pObj) )
774  {
775  Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) );
776  Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) );
777 // nSize = Vec_IntSize(vSuper);
778  Vec_IntSort( p->vSuper, 0 );
779  Gia_ManSimplifyAnd( p->vSuper );
780 // if ( nSize != Vec_IntSize(vSuper) )
781 // printf( "A %d->%d ", nSize, Vec_IntSize(vSuper) );
782  }
783  else assert( 0 );
784 // if ( nSize > 10 )
785 // printf( "%d ", nSize );
786  assert( Vec_IntSize(p->vSuper) > 0 );
787 }
788 
789 /**Function*************************************************************
790 
791  Synopsis []
792 
793  Description []
794 
795  SideEffects []
796 
797  SeeAlso []
798 
799 ***********************************************************************/
800 static inline void Gia_ManCreateGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper )
801 {
802  int iLit0 = Vec_IntPop(vSuper);
803  int iLit1 = Vec_IntPop(vSuper);
804  int iLit, i;
805  if ( !Gia_ObjIsXor(pObj) )
806  iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 );
807  else if ( pNew->pMuxes )
808  iLit = Gia_ManHashXorReal( pNew, iLit0, iLit1 );
809  else
810  iLit = Gia_ManHashXor( pNew, iLit0, iLit1 );
811  Vec_IntPush( vSuper, iLit );
812  Bal_ManSetGateLevel( Bal_GiaMan(pNew), pObj, iLit );
813 // Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(iLit)) );
814  // shift to the corrent location
815  for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
816  {
817  int iLit1 = Vec_IntEntry(vSuper, i);
818  int iLit2 = Vec_IntEntry(vSuper, i-1);
819  if ( Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1)) <= Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
820  break;
821  Vec_IntWriteEntry( vSuper, i, iLit2 );
822  Vec_IntWriteEntry( vSuper, i-1, iLit1 );
823  }
824 }
825 static inline int Gia_ManBalanceGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper, int * pLits, int nLits )
826 {
827  Vec_IntClear( vSuper );
828  if ( nLits == 1 )
829  Vec_IntPush( vSuper, pLits[0] );
830  else if ( nLits == 2 )
831  {
832  Vec_IntPush( vSuper, pLits[0] );
833  Vec_IntPush( vSuper, pLits[1] );
834  Gia_ManCreateGate( pNew, pObj, vSuper );
835  }
836  else if ( nLits > 2 )
837  {
838  Bal_Man_t * p = Bal_GiaMan(pNew); int i;
839  for ( i = 0; i < nLits; i++ )
840  Vec_IntPush( vSuper, pLits[i] );
841  // sort by level/cut-size
842  Vec_IntSelectSortCostLit( vSuper, p->vCosts );
843  // iterate till everything is grouped
844  while ( Vec_IntSize(vSuper) > 1 )
845  {
846  int iLit, Res = Bal_ManFindBestPair( p, vSuper, pObj );
847  int iBest = Vec_IntEntry( vSuper, Res >> 16 );
848  int kBest = Vec_IntEntry( vSuper, Res & 0xFFFF );
849  Vec_IntRemove( vSuper, iBest );
850  Vec_IntRemove( vSuper, kBest );
851  if ( Gia_ObjIsXor(pObj) )
852  iLit = Gia_ManHashXorReal( pNew, iBest, kBest );
853  else
854  iLit = Gia_ManHashAnd( pNew, iBest, kBest );
855  Bal_ManSetGateLevel( p, pObj, iLit );
856  Vec_IntPushOrderCost( vSuper, p->vCosts, iLit );
857  }
858  }
859  // consider trivial case
860  assert( Vec_IntSize(vSuper) == 1 );
861  return Vec_IntEntry(vSuper, 0);
862 }
863 
864 /**Function*************************************************************
865 
866  Synopsis []
867 
868  Description []
869 
870  SideEffects []
871 
872  SeeAlso []
873 
874 ***********************************************************************/
875 static inline void Gia_ManBalance_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj )
876 {
877  int i, iLit, iBeg, iEnd;
878  if ( ~pObj->Value )
879  return;
880  assert( Gia_ObjIsAnd(pObj) );
881  // handle MUX
882  if ( Gia_ObjIsMux(p, pObj) )
883  {
884  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
885  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin1(pObj) );
886  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin2(p, pObj) );
887  pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
888  Bal_ManSetGateLevel( Bal_GiaMan(pNew), pObj, pObj->Value );
889 // Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
890  return;
891  }
892  // find supergate
893  Gia_ManSuperCollect( p, pObj );
894  // save entries
895  if ( p->vStore == NULL )
896  p->vStore = Vec_IntAlloc( 1000 );
897  iBeg = Vec_IntSize( p->vStore );
898  Vec_IntAppend( p->vStore, p->vSuper );
899  iEnd = Vec_IntSize( p->vStore );
900  // call recursively
901  Vec_IntForEachEntryStartStop( p->vStore, iLit, i, iBeg, iEnd )
902  {
903  Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(iLit) );
904  Gia_ManBalance_rec( pNew, p, pTemp );
905  Vec_IntWriteEntry( p->vStore, i, Abc_LitNotCond(pTemp->Value, Abc_LitIsCompl(iLit)) );
906  }
907  assert( Vec_IntSize(p->vStore) == iEnd );
908  // consider general case
909  pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, Vec_IntEntryP(p->vStore, iBeg), iEnd-iBeg );
910  Vec_IntShrink( p->vStore, iBeg );
911 }
912 static inline Gia_Man_t * Gia_ManBalanceInt( Gia_Man_t * p, int nLutSize, int nCutNum, int fVerbose )
913 {
914  Bal_Man_t * pMan;
915  Gia_Man_t * pNew, * pTemp;
916  Gia_Obj_t * pObj;
917  int i;
918  Gia_ManFillValue( p );
919  Gia_ManCreateRefs( p );
920  // start the new manager
921  pNew = Gia_ManStart( 3*Gia_ManObjNum(p)/2 );
922  pNew->pName = Abc_UtilStrsav( p->pName );
923  pNew->pSpec = Abc_UtilStrsav( p->pSpec );
924  pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
925  pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
926  // create constant and inputs
927  Gia_ManConst0(p)->Value = 0;
928  Gia_ManForEachCi( p, pObj, i )
929  pObj->Value = Gia_ManAppendCi( pNew );
930  // create balancing manager
931  pMan = Bal_ManAlloc( p, pNew, nLutSize, nCutNum, fVerbose );
932  // create internal nodes
933  Gia_ManHashStart( pNew );
934  Gia_ManForEachCo( p, pObj, i )
935  Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
936  Gia_ManForEachCo( p, pObj, i )
937  pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
938 // if ( fVerbose )
939  {
940  int nLevelMax = 0;
941  Gia_ManForEachCo( pNew, pObj, i )
942  {
943  nLevelMax = Abc_MaxInt( nLevelMax, Bal_ObjDelay(pMan, Gia_ObjFaninId0p(pNew, pObj)) );
944 // printf( "%d=%d ", i, Bal_ObjDelay(pMan, Gia_ObjFaninId0p(pNew, pObj)) );
945  }
946  printf( "Best delay = %d\n", nLevelMax );
947  }
948 
949 // assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
950  Gia_ManHashStop( pNew );
951  Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
952  // delete manager
953  Bal_ManFree( pMan );
954  // perform cleanup
955  pNew = Gia_ManCleanup( pTemp = pNew );
956  Gia_ManStop( pTemp );
957  return pNew;
958 }
959 Gia_Man_t * Gia_ManBalanceLut( Gia_Man_t * p, int nLutSize, int nCutNum, int fVerbose )
960 {
961  Gia_Man_t * pNew, * pNew1, * pNew2;
962  if ( fVerbose ) Gia_ManPrintStats( p, NULL );
963  pNew = Gia_ManDupMuxes( p, 2 );
964  if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
965  pNew1 = Gia_ManBalanceInt( pNew, nLutSize, nCutNum, fVerbose );
966  if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
967  Gia_ManStop( pNew );
968  pNew2 = Gia_ManDupNoMuxes( pNew1 );
969  if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
970  Gia_ManStop( pNew1 );
971  return pNew2;
972 }
973 
974 
975 
976 ////////////////////////////////////////////////////////////////////////
977 /// END OF FILE ///
978 ////////////////////////////////////////////////////////////////////////
979 
980 
981 ABC_NAMESPACE_IMPL_END
982 
Gia_Man_t_::nObjsAlloc
int nObjsAlloc
Definition: gia.h:102
Gia_ObjFanin2Copy
static int Gia_ObjFanin2Copy(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:483
memset
char * memset()
Gia_ObjToLit
static int Gia_ObjToLit(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:497
Gia_ObjLevelId
static int Gia_ObjLevelId(Gia_Man_t *p, int Id)
Definition: gia.h:500
Vec_IntArray
static int * Vec_IntArray(Vec_Int_t *p)
Definition: vecInt.h:328
Gia_ManCreateRefs
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition: giaUtil.c:715
Gia_ObjChild0
static Gia_Obj_t * Gia_ObjChild0(Gia_Obj_t *pObj)
Definition: gia.h:457
Gia_ObjFaninC2
static int Gia_ObjFaninC2(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:453
Bal_SetCutIsContainedOrder
static int Bal_SetCutIsContainedOrder(Bal_Cut_t *pBase, Bal_Cut_t *pCut)
Definition: giaBalLut.c:312
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Bal_Cut_t_
Definition: giaBalLut.c:40
Gia_ObjIsAndReal
static int Gia_ObjIsAndReal(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:426
BAL_LEAF_MAX
#define BAL_LEAF_MAX
DECLARATIONS ///.
Definition: giaBalLut.c:33
Gia_ManStop
void Gia_ManStop(Gia_Man_t *p)
Definition: giaMan.c:77
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition: gia.h:1022
Gia_ManPrintStats
void Gia_ManPrintStats(Gia_Man_t *p, Gps_Par_t *pPars)
Definition: giaMan.c:389
Bal_LitCost
static int Bal_LitCost(Bal_Man_t *p, int i)
Definition: giaBalLut.c:67
Gia_ObjFaninC1
static int Gia_ObjFaninC1(Gia_Obj_t *pObj)
Definition: gia.h:452
Bal_Man_t_
Definition: giaBalLut.c:51
Bal_CutGetSign
static word Bal_CutGetSign(int *pLeaves, int nLeaves)
Definition: giaBalLut.c:128
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
BAL_CUT_MAX
#define BAL_CUT_MAX
Definition: giaBalLut.c:34
Gia_ManHashXor
int Gia_ManHashXor(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:658
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Bal_ManEvalTwo
int Bal_ManEvalTwo(Bal_Man_t *p, int iLitNew0, int iLitNew1, int iLitNew2, int fIsXor)
Definition: giaBalLut.c:526
Vec_PtrFill
static void Vec_PtrFill(Vec_Ptr_t *p, int nSize, void *Entry)
Definition: vecPtr.h:449
Gia_ManBalance_rec
static void Gia_ManBalance_rec(Gia_Man_t *pNew, Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalLut.c:875
Gia_ManSimplifyXor
static void Gia_ManSimplifyXor(Vec_Int_t *vSuper)
Definition: giaBalLut.c:674
Bal_ManFindBestPair
static int Bal_ManFindBestPair(Bal_Man_t *p, Vec_Int_t *vSuper, Gia_Obj_t *pObj)
Definition: giaBalLut.c:610
Bal_ObjDelay
static int Bal_ObjDelay(Bal_Man_t *p, int i)
Definition: giaBalLut.c:68
Bal_CutCountBits
static int Bal_CutCountBits(word i)
Definition: giaBalLut.c:121
Bal_Man_t_::pNew
Gia_Man_t * pNew
Definition: giaBalLut.c:58
Gia_ManAppendCi
static int Gia_ManAppendCi(Gia_Man_t *p)
Definition: gia.h:583
Gia_ManBalanceLut
Gia_Man_t * Gia_ManBalanceLut(Gia_Man_t *p, int nLutSize, int nCutNum, int fVerbose)
Definition: giaBalLut.c:959
Vec_PtrFreeFree
static void Vec_PtrFreeFree(Vec_Ptr_t *p)
Definition: vecPtr.h:569
Bal_ManPrepareSet
static int Bal_ManPrepareSet(Bal_Man_t *p, int iObj, int Index, int fUnit, Bal_Cut_t **ppCutSet)
Definition: giaBalLut.c:144
Gia_Man_t_::pMuxes
unsigned * pMuxes
Definition: gia.h:104
Bal_ManDeriveCuts
int Bal_ManDeriveCuts(Bal_Man_t *p, int iFan0, int iFan1, int iFan2, int fCompl0, int fCompl1, int fCompl2, int fUnit0, int fUnit1, int fUnit2, int fIsXor, int Target, int fSave)
Definition: giaBalLut.c:402
Bal_CutMergeOrder
static int Bal_CutMergeOrder(Bal_Cut_t *pCut0, Bal_Cut_t *pCut1, Bal_Cut_t *pCut, int nLutSize)
Definition: giaBalLut.c:223
Vec_IntPushOrderCost
static void Vec_IntPushOrderCost(Vec_Int_t *vSuper, Vec_Int_t *vCosts, int iLit)
Definition: giaBalLut.c:571
Gia_ObjRefNum
static int Gia_ObjRefNum(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:521
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Bal_Man_t_::nCutNum
int nCutNum
Definition: giaBalLut.c:55
Gia_ManSetRegNum
void Gia_ManSetRegNum(Gia_Man_t *p, int nRegs)
Definition: giaMan.c:628
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Bal_Man_t_::fVerbose
int fVerbose
Definition: giaBalLut.c:57
Gia_ManSuperCollectXor_rec
static void Gia_ManSuperCollectXor_rec(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalLut.c:724
Vec_IntSort
static void Vec_IntSort(Vec_Int_t *p, int fReverse)
Definition: vecInt.h:1293
Gia_ManObj
static Gia_Obj_t * Gia_ManObj(Gia_Man_t *p, int v)
Definition: gia.h:402
Abc_LitNotCond
static int Abc_LitNotCond(int Lit, int c)
Definition: abc_global.h:267
Gia_Man_t_::vStore
Vec_Int_t * vStore
Definition: gia.h:190
Gia_Obj_t_
Definition: gia.h:75
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
Gia_ManDupNoMuxes
Gia_Man_t * Gia_ManDupNoMuxes(Gia_Man_t *p)
Definition: giaMuxes.c:159
Bal_Man_t_::clkStart
abctime clkStart
Definition: giaBalLut.c:61
Gia_ObjChild1
static Gia_Obj_t * Gia_ObjChild1(Gia_Obj_t *pObj)
Definition: gia.h:458
Gia_ManForEachCi
#define Gia_ManForEachCi(p, pObj, i)
Definition: gia.h:1016
Gia_ManBalanceGate
static int Gia_ManBalanceGate(Gia_Man_t *pNew, Gia_Obj_t *pObj, Vec_Int_t *vSuper, int *pLits, int nLits)
Definition: giaBalLut.c:825
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
Gia_ManBalanceInt
static Gia_Man_t * Gia_ManBalanceInt(Gia_Man_t *p, int nLutSize, int nCutNum, int fVerbose)
Definition: giaBalLut.c:912
Gia_ManSuperCollect
static void Gia_ManSuperCollect(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalLut.c:755
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
Vec_IntStart
static Vec_Int_t * Vec_IntStart(int nSize)
Definition: bblif.c:172
Abc_LitIsCompl
static int Abc_LitIsCompl(int Lit)
Definition: abc_global.h:265
BAL_SUPER
#define BAL_SUPER
Definition: giaBalLut.c:35
Bal_SetCheckArray
static int Bal_SetCheckArray(Bal_Cut_t **ppCuts, int nCuts)
Definition: giaBalLut.c:184
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_ManSuperCollectAnd_rec
static void Gia_ManSuperCollectAnd_rec(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: giaBalLut.c:740
Bal_Cut_t_::Delay
int Delay
Definition: giaBalLut.c:43
Bal_SetLastCutIsContained
static int Bal_SetLastCutIsContained(Bal_Cut_t **pCuts, int nCuts)
Definition: giaBalLut.c:338
Gia_ObjFanin1Copy
static int Gia_ObjFanin1Copy(Gia_Obj_t *pObj)
Definition: gia.h:482
Bal_CutCheck
static int Bal_CutCheck(Bal_Cut_t *pBase, Bal_Cut_t *pCut)
Definition: giaBalLut.c:168
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
Bal_Man_t_::fCutMin
int fCutMin
Definition: giaBalLut.c:56
Gia_Man_t_::pData
void * pData
Definition: gia.h:169
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
BAL_NO_LEAF
#define BAL_NO_LEAF
Definition: giaBalLut.c:36
Vec_IntFill
static void Vec_IntFill(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:356
Gia_ManHashStart
void Gia_ManHashStart(Gia_Man_t *p)
Definition: giaHash.c:117
Gia_Man_t_::pSpec
char * pSpec
Definition: gia.h:98
Vec_IntSelectSortCostLit
static void Vec_IntSelectSortCostLit(Vec_Int_t *vSuper, Vec_Int_t *vCosts)
Definition: giaBalLut.c:557
Vec_IntPop
static int Vec_IntPop(Vec_Int_t *p)
Definition: extraZddTrunc.c:110
Gia_ManStart
Gia_Man_t * Gia_ManStart(int nObjsMax)
DECLARATIONS ///.
Definition: giaMan.c:52
Gia_ManDupMuxes
Gia_Man_t * Gia_ManDupMuxes(Gia_Man_t *p, int Limit)
Definition: giaMuxes.c:96
Gia_ObjIsXor
static int Gia_ObjIsXor(Gia_Obj_t *pObj)
Definition: gia.h:423
Bal_CutMergeOrderMux
static int Bal_CutMergeOrderMux(Bal_Cut_t *pCut0, Bal_Cut_t *pCut1, Bal_Cut_t *pCut2, Bal_Cut_t *pCut, int nLutSize)
Definition: giaBalLut.c:287
Gia_ManHashXorReal
int Gia_ManHashXorReal(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:465
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Vec_IntAppend
static void Vec_IntAppend(Vec_Int_t *vVec1, Vec_Int_t *vVec2)
Definition: extraZddTrunc.c:126
Gia_ManFillValue
void Gia_ManFillValue(Gia_Man_t *p)
Definition: giaUtil.c:328
Bal_LitDelay
static int Bal_LitDelay(Bal_Man_t *p, int i)
Definition: giaBalLut.c:69
Bal_Man_t_::vCutSets
Vec_Ptr_t * vCutSets
Definition: giaBalLut.c:60
Bal_Cut_t_::iFunc
unsigned iFunc
Definition: giaBalLut.c:44
Bal_CutCreateUnit
static int Bal_CutCreateUnit(Bal_Cut_t *p, int i, int Delay)
Definition: giaBalLut.c:135
Bal_SetSortByDelay
static void Bal_SetSortByDelay(Bal_Cut_t **pCuts, int nCuts)
Definition: giaBalLut.c:372
Bal_GiaMan
static Bal_Man_t * Bal_GiaMan(Gia_Man_t *p)
Definition: giaBalLut.c:64
Bal_Cut_t_::Sign
word Sign
Definition: giaBalLut.c:42
Vec_IntRemove
static int Vec_IntRemove(Vec_Int_t *p, int Entry)
Definition: vecInt.h:915
Gia_ManSimplifyAnd
static void Gia_ManSimplifyAnd(Vec_Int_t *vSuper)
Definition: giaBalLut.c:694
Gia_ObjFanin0Copy
static int Gia_ObjFanin0Copy(Gia_Obj_t *pObj)
Definition: gia.h:481
Bal_Cut_t_::pLeaves
int pLeaves[BAL_LEAF_MAX]
Definition: giaBalLut.c:46
Gia_ObjFanin2
static Gia_Obj_t * Gia_ObjFanin2(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:456
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Bal_SetLastCutContains
static int Bal_SetLastCutContains(Bal_Cut_t **pCuts, int nCuts)
Definition: giaBalLut.c:346
Vec_IntEntryLast
static int Vec_IntEntryLast(Vec_Int_t *p)
Definition: bblif.c:319
Abc_LitNot
static int Abc_LitNot(int Lit)
Definition: abc_global.h:266
Bal_Man_t_::pGia
Gia_Man_t * pGia
Definition: giaBalLut.c:53
Bal_ManAlloc
Bal_Man_t * Bal_ManAlloc(Gia_Man_t *pGia, Gia_Man_t *pNew, int nLutSize, int nCutNum, int fVerbose)
FUNCTION DEFINITIONS ///.
Definition: giaBalLut.c:86
Vec_IntFindFirstSameDelayAsLast
static int Vec_IntFindFirstSameDelayAsLast(Bal_Man_t *p, Vec_Int_t *vSuper)
Definition: giaBalLut.c:584
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Bal_CutCompareArea
static int Bal_CutCompareArea(Bal_Cut_t *pCut0, Bal_Cut_t *pCut1)
Definition: giaBalLut.c:364
Gia_IsComplement
static int Gia_IsComplement(Gia_Obj_t *p)
Definition: gia.h:380
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Bal_Man_t_::vCosts
Vec_Int_t * vCosts
Definition: giaBalLut.c:59
Bal_Cut_t_::nLeaves
unsigned nLeaves
Definition: giaBalLut.c:45
Vec_IntShrink
static void Vec_IntShrink(Vec_Int_t *p, int nSizeNew)
Definition: bblif.c:435
Bal_SetAddCut
static int Bal_SetAddCut(Bal_Cut_t **pCuts, int nCuts, int nCutNum)
Definition: giaBalLut.c:382
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_ManConst0
static Gia_Obj_t * Gia_ManConst0(Gia_Man_t *p)
Definition: gia.h:400
Bal_ManFree
void Bal_ManFree(Bal_Man_t *p)
Definition: giaBalLut.c:103
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
Abc_Lit2Var
static int Abc_Lit2Var(int Lit)
Definition: abc_global.h:264
Gia_ObjFaninId0p
static int Gia_ObjFaninId0p(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:463
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_ManCreateGate
static void Gia_ManCreateGate(Gia_Man_t *pNew, Gia_Obj_t *pObj, Vec_Int_t *vSuper)
Definition: giaBalLut.c:800
Bal_ObjCost
static int Bal_ObjCost(Bal_Man_t *p, int i)
Definition: giaBalLut.c:66
assert
#define assert(ex)
Definition: util_old.h:213
Vec_IntEntryP
static int * Vec_IntEntryP(Vec_Int_t *p, int i)
Definition: vecInt.h:417
Vec_IntForEachEntryStartStop
#define Vec_IntForEachEntryStartStop(vVec, Entry, i, Start, Stop)
Definition: vecInt.h:60
Gia_ObjFaninId2
static int Gia_ObjFaninId2(Gia_Man_t *p, int ObjId)
Definition: gia.h:462
Gia_Obj_t_::Value
unsigned Value
Definition: gia.h:87
Gia_ManHashMuxReal
int Gia_ManHashMuxReal(Gia_Man_t *p, int iLitC, int iLit1, int iLit0)
Definition: giaHash.c:517
Bal_ManSetGateLevel
int Bal_ManSetGateLevel(Bal_Man_t *p, Gia_Obj_t *pObjOld, int iLitNew)
Definition: giaBalLut.c:486
Gia_Man_t_::vLevels
Vec_Int_t * vLevels
Definition: gia.h:115
BAL_NO_FUNC
#define BAL_NO_FUNC
Definition: giaBalLut.c:37
Gia_ObjFaninC0
static int Gia_ObjFaninC0(Gia_Obj_t *pObj)
Definition: gia.h:451
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Gia_Man_t_::vSuper
Vec_Int_t * vSuper
Definition: gia.h:189
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_ManCleanup
Gia_Man_t * Gia_ManCleanup(Gia_Man_t *p)
Definition: giaScl.c:84
Abc_UtilStrsav
char * Abc_UtilStrsav(char *s)
Definition: starter.c:47
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Gia_ObjFaninId1
static int Gia_ObjFaninId1(Gia_Obj_t *pObj, int ObjId)
Definition: gia.h:461
Gia_ObjIsMux
static int Gia_ObjIsMux(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:425
Gia_ManHashAnd
int Gia_ManHashAnd(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:572
Gia_ManObjNum
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
Bal_Man_t_::nLutSize
int nLutSize
Definition: giaBalLut.c:54
Gia_ManHashStop
void Gia_ManHashStop(Gia_Man_t *p)
Definition: giaHash.c:142
Gia_ObjFaninId0
static int Gia_ObjFaninId0(Gia_Obj_t *pObj, int ObjId)
Definition: gia.h:460
Gia_ManRegNum
static int Gia_ManRegNum(Gia_Man_t *p)
Definition: gia.h:387