abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaTsim.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [giaTsim.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Scalable AIG package.]
8 
9  Synopsis [Ternary simulation.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: giaTsim.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "gia.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 static inline int Gia_ManTerSimInfoGet( unsigned * pInfo, int i )
31 {
32  return 3 & (pInfo[i >> 4] >> ((i & 15) << 1));
33 }
34 static inline void Gia_ManTerSimInfoSet( unsigned * pInfo, int i, int Value )
35 {
36  assert( Value >= GIA_ZER && Value <= GIA_UND );
37  Value ^= Gia_ManTerSimInfoGet( pInfo, i );
38  pInfo[i >> 4] ^= (Value << ((i & 15) << 1));
39 }
40 
41 static inline unsigned * Gia_ManTerStateNext( unsigned * pState, int nWords ) { return *((unsigned **)(pState + nWords)); }
42 static inline void Gia_ManTerStateSetNext( unsigned * pState, int nWords, unsigned * pNext ) { *((unsigned **)(pState + nWords)) = pNext; }
43 
44 // ternary simulation manager
45 typedef struct Gia_ManTer_t_ Gia_ManTer_t;
46 struct Gia_ManTer_t_
47 {
48  Gia_Man_t * pAig;
49  int nIters;
50  int nStateWords;
51  Vec_Ptr_t * vStates;
52  Vec_Ptr_t * vFlops;
53  Vec_Int_t * vRetired; // retired registers
54  char * pRetired; // retired registers
55  int * pCount0;
56  int * pCountX;
57  // hash table for states
58  int nBins;
59  unsigned ** pBins;
60  // simulation information
61  unsigned * pDataSim; // simulation data
62  unsigned * pDataSimCis; // simulation data for CIs
63  unsigned * pDataSimCos; // simulation data for COs
64 };
65 
66 ////////////////////////////////////////////////////////////////////////
67 /// FUNCTION DEFINITIONS ///
68 ////////////////////////////////////////////////////////////////////////
69 
70 /**Function*************************************************************
71 
72  Synopsis [Creates fast simulation manager.]
73 
74  Description []
75 
76  SideEffects []
77 
78  SeeAlso []
79 
80 ***********************************************************************/
81 Gia_ManTer_t * Gia_ManTerCreate( Gia_Man_t * pAig )
82 {
83  Gia_ManTer_t * p;
84  p = ABC_CALLOC( Gia_ManTer_t, 1 );
85  p->pAig = Gia_ManFront( pAig );
86  p->nIters = 300;
87  p->pDataSim = ABC_ALLOC( unsigned, Abc_BitWordNum(2*p->pAig->nFront) );
88  p->pDataSimCis = ABC_ALLOC( unsigned, Abc_BitWordNum(2*Gia_ManCiNum(p->pAig)) );
89  p->pDataSimCos = ABC_ALLOC( unsigned, Abc_BitWordNum(2*Gia_ManCoNum(p->pAig)) );
90  // allocate storage for terminary states
91  p->nStateWords = Abc_BitWordNum( 2*Gia_ManRegNum(pAig) );
92  p->vStates = Vec_PtrAlloc( 1000 );
93  p->pCount0 = ABC_CALLOC( int, Gia_ManRegNum(pAig) );
94  p->pCountX = ABC_CALLOC( int, Gia_ManRegNum(pAig) );
95  p->nBins = Abc_PrimeCudd( 500 );
96  p->pBins = ABC_CALLOC( unsigned *, p->nBins );
97  p->vRetired = Vec_IntAlloc( 100 );
98  p->pRetired = ABC_CALLOC( char, Gia_ManRegNum(pAig) );
99  return p;
100 }
101 
102 /**Function*************************************************************
103 
104  Synopsis []
105 
106  Description []
107 
108  SideEffects []
109 
110  SeeAlso []
111 
112 ***********************************************************************/
113 void Gia_ManTerStatesFree( Vec_Ptr_t * vStates )
114 {
115  unsigned * pTemp;
116  int i;
117  Vec_PtrForEachEntry( unsigned *, vStates, pTemp, i )
118  ABC_FREE( pTemp );
119  Vec_PtrFree( vStates );
120 }
121 
122 /**Function*************************************************************
123 
124  Synopsis []
125 
126  Description []
127 
128  SideEffects []
129 
130  SeeAlso []
131 
132 ***********************************************************************/
133 void Gia_ManTerDelete( Gia_ManTer_t * p )
134 {
135  if ( p->vStates )
136  Gia_ManTerStatesFree( p->vStates );
137  if ( p->vFlops )
138  Gia_ManTerStatesFree( p->vFlops );
139  Gia_ManStop( p->pAig );
140  Vec_IntFree( p->vRetired );
141  ABC_FREE( p->pRetired );
142  ABC_FREE( p->pCount0 );
143  ABC_FREE( p->pCountX );
144  ABC_FREE( p->pBins );
145  ABC_FREE( p->pDataSim );
146  ABC_FREE( p->pDataSimCis );
147  ABC_FREE( p->pDataSimCos );
148  ABC_FREE( p );
149 }
150 
151 /**Function*************************************************************
152 
153  Synopsis []
154 
155  Description []
156 
157  SideEffects []
158 
159  SeeAlso []
160 
161 ***********************************************************************/
162 static inline void Gia_ManTerSimulateCi( Gia_ManTer_t * p, Gia_Obj_t * pObj, int iCi )
163 {
164  Gia_ManTerSimInfoSet( p->pDataSim, Gia_ObjValue(pObj), Gia_ManTerSimInfoGet(p->pDataSimCis, iCi) );
165 }
166 
167 /**Function*************************************************************
168 
169  Synopsis []
170 
171  Description []
172 
173  SideEffects []
174 
175  SeeAlso []
176 
177 ***********************************************************************/
178 static inline void Gia_ManTerSimulateCo( Gia_ManTer_t * p, int iCo, Gia_Obj_t * pObj )
179 {
180  int Value = Gia_ManTerSimInfoGet( p->pDataSim, Gia_ObjDiff0(pObj) );
181  Gia_ManTerSimInfoSet( p->pDataSimCos, iCo, Gia_XsimNotCond( Value, Gia_ObjFaninC0(pObj) ) );
182 }
183 
184 /**Function*************************************************************
185 
186  Synopsis []
187 
188  Description []
189 
190  SideEffects []
191 
192  SeeAlso []
193 
194 ***********************************************************************/
195 static inline void Gia_ManTerSimulateNode( Gia_ManTer_t * p, Gia_Obj_t * pObj )
196 {
197  int Value0 = Gia_ManTerSimInfoGet( p->pDataSim, Gia_ObjDiff0(pObj) );
198  int Value1 = Gia_ManTerSimInfoGet( p->pDataSim, Gia_ObjDiff1(pObj) );
199  Gia_ManTerSimInfoSet( p->pDataSim, Gia_ObjValue(pObj), Gia_XsimAndCond( Value0, Gia_ObjFaninC0(pObj), Value1, Gia_ObjFaninC1(pObj) ) );
200 }
201 
202 /**Function*************************************************************
203 
204  Synopsis []
205 
206  Description []
207 
208  SideEffects []
209 
210  SeeAlso []
211 
212 ***********************************************************************/
213 static inline void Gia_ManTerSimInfoInit( Gia_ManTer_t * p )
214 {
215  int i = 0;
216  for ( ; i < Gia_ManPiNum(p->pAig); i++ )
217  Gia_ManTerSimInfoSet( p->pDataSimCis, i, GIA_UND );
218  for ( ; i < Gia_ManCiNum(p->pAig); i++ )
219  Gia_ManTerSimInfoSet( p->pDataSimCis, i, GIA_ZER );
220 }
221 
222 /**Function*************************************************************
223 
224  Synopsis []
225 
226  Description []
227 
228  SideEffects []
229 
230  SeeAlso []
231 
232 ***********************************************************************/
233 static inline void Gia_ManTerSimInfoTransfer( Gia_ManTer_t * p )
234 {
235  int i = 0;
236  for ( ; i < Gia_ManPiNum(p->pAig); i++ )
237  Gia_ManTerSimInfoSet( p->pDataSimCis, i, GIA_UND );
238  for ( ; i < Gia_ManCiNum(p->pAig); i++ )
239  Gia_ManTerSimInfoSet( p->pDataSimCis, i, Gia_ManTerSimInfoGet( p->pDataSimCos, Gia_ManCoNum(p->pAig)-Gia_ManCiNum(p->pAig)+i ) );
240 }
241 
242 
243 /**Function*************************************************************
244 
245  Synopsis [Computes hash value of the node using its simulation info.]
246 
247  Description []
248 
249  SideEffects []
250 
251  SeeAlso []
252 
253 ***********************************************************************/
254 int Gia_ManTerStateHash( unsigned * pState, int nWords, int nTableSize )
255 {
256  static int s_FPrimes[128] = {
257  1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459,
258  1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997,
259  2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543,
260  2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089,
261  3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671,
262  3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243,
263  4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871,
264  4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471,
265  5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073,
266  6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689,
267  6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309,
268  7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933,
269  8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147
270  };
271  unsigned uHash;
272  int i;
273  uHash = 0;
274  for ( i = 0; i < nWords; i++ )
275  uHash ^= pState[i] * s_FPrimes[i & 0x7F];
276  return uHash % nTableSize;
277 }
278 
279 /**Function*************************************************************
280 
281  Synopsis [Inserts value into the table.]
282 
283  Description []
284 
285  SideEffects []
286 
287  SeeAlso []
288 
289 ***********************************************************************/
290 unsigned * Gia_ManTerStateLookup( unsigned * pState, int nWords, unsigned ** pBins, int nBins )
291 {
292  unsigned * pEntry;
293  int Hash = Gia_ManTerStateHash( pState, nWords, nBins );
294  for ( pEntry = pBins[Hash]; pEntry; pEntry = Gia_ManTerStateNext(pEntry, nWords) )
295  if ( !memcmp( pEntry, pState, sizeof(unsigned) * nWords ) )
296  return pEntry;
297  return NULL;
298 }
299 
300 /**Function*************************************************************
301 
302  Synopsis [Inserts value into the table.]
303 
304  Description []
305 
306  SideEffects []
307 
308  SeeAlso []
309 
310 ***********************************************************************/
311 void Gia_ManTerStateInsert( unsigned * pState, int nWords, unsigned ** pBins, int nBins )
312 {
313  int Hash = Gia_ManTerStateHash( pState, nWords, nBins );
314  assert( !Gia_ManTerStateLookup( pState, nWords, pBins, nBins ) );
315  Gia_ManTerStateSetNext( pState, nWords, pBins[Hash] );
316  pBins[Hash] = pState;
317 }
318 
319 /**Function*************************************************************
320 
321  Synopsis [Allocs new ternary state.]
322 
323  Description []
324 
325  SideEffects []
326 
327  SeeAlso []
328 
329 ***********************************************************************/
330 unsigned * Gia_ManTerStateAlloc( int nWords )
331 {
332  return (unsigned *)ABC_CALLOC( char, sizeof(unsigned) * nWords + sizeof(unsigned *) );
333 }
334 
335 /**Function*************************************************************
336 
337  Synopsis [Creates new ternary state.]
338 
339  Description []
340 
341  SideEffects []
342 
343  SeeAlso []
344 
345 ***********************************************************************/
346 unsigned * Gia_ManTerStateCreate( Gia_ManTer_t * p )
347 {
348  int i, Value, nPis = Gia_ManPiNum(p->pAig);
349  unsigned * pRes = Gia_ManTerStateAlloc( p->nStateWords );
350  for ( i = nPis; i < Gia_ManCiNum(p->pAig); i++ )
351  {
352  Value = Gia_ManTerSimInfoGet( p->pDataSimCis, i );
353  Gia_ManTerSimInfoSet( pRes, i-nPis, Value );
354  if ( Value == GIA_ZER )
355  p->pCount0[i-nPis]++;
356  if ( Value == GIA_UND )
357  p->pCountX[i-nPis]++;
358  }
359  Vec_PtrPush( p->vStates, pRes );
360  return pRes;
361 }
362 
363 /**Function*************************************************************
364 
365  Synopsis [Performs one round of ternary simulation.]
366 
367  Description []
368 
369  SideEffects []
370 
371  SeeAlso []
372 
373 ***********************************************************************/
374 static inline void Gia_ManTerSimulateRound( Gia_ManTer_t * p )
375 {
376  Gia_Obj_t * pObj;
377  int i, iCis = 0, iCos = 0;
378  assert( p->pAig->nFront > 0 );
379  assert( Gia_ManConst0(p->pAig)->Value == 0 );
380  Gia_ManTerSimInfoSet( p->pDataSim, 0, GIA_ZER );
381  Gia_ManForEachObj1( p->pAig, pObj, i )
382  {
383  if ( Gia_ObjIsAndOrConst0(pObj) )
384  {
385  assert( Gia_ObjValue(pObj) < p->pAig->nFront );
386  Gia_ManTerSimulateNode( p, pObj );
387  }
388  else if ( Gia_ObjIsCi(pObj) )
389  {
390  assert( Gia_ObjValue(pObj) < p->pAig->nFront );
391  Gia_ManTerSimulateCi( p, pObj, iCis++ );
392  }
393  else // if ( Gia_ObjIsCo(pObj) )
394  {
395  assert( Gia_ObjValue(pObj) == GIA_NONE );
396  Gia_ManTerSimulateCo( p, iCos++, pObj );
397  }
398  }
399  assert( Gia_ManCiNum(p->pAig) == iCis );
400  assert( Gia_ManCoNum(p->pAig) == iCos );
401 }
402 
403 /**Function*************************************************************
404 
405  Synopsis [Retires a set of registers to speed up convergence.]
406 
407  Description [Retire all non-ternary registers which has max number
408  of ternary values so far.]
409 
410  SideEffects []
411 
412  SeeAlso []
413 
414 ***********************************************************************/
415 int Gia_ManTerRetire2( Gia_ManTer_t * p, unsigned * pState )
416 {
417  int i, Entry, iMaxTerValue = -1;
418  // find non-retired register with this value
419  for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
420  if ( Gia_ManTerSimInfoGet( pState, i ) != GIA_UND && !p->pRetired[i] && iMaxTerValue < p->pCountX[i] )
421  iMaxTerValue = p->pCountX[i];
422  assert( iMaxTerValue >= 0 );
423  // retire the first registers with this value
424  for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
425  if ( Gia_ManTerSimInfoGet( pState, i ) != GIA_UND && !p->pRetired[i] && iMaxTerValue == p->pCountX[i] )
426  {
427  assert( p->pRetired[i] == 0 );
428  p->pRetired[i] = 1;
429  Vec_IntPush( p->vRetired, i );
430  if ( iMaxTerValue == 0 )
431  break;
432  }
433  // update all the retired registers
434  Vec_IntForEachEntry( p->vRetired, Entry, i )
435  Gia_ManTerSimInfoSet( p->pDataSimCis, Gia_ManPiNum(p->pAig)+Entry, GIA_UND );
436  return Vec_IntSize(p->vRetired);
437 }
438 
439 /**Function*************************************************************
440 
441  Synopsis [Retires a set of registers to speed up convergence.]
442 
443  Description [Retire all non-ternary registers which has max number
444  of ternary values so far.]
445 
446  SideEffects []
447 
448  SeeAlso []
449 
450 ***********************************************************************/
451 int Gia_ManTerRetire( Gia_ManTer_t * p, unsigned * pThis, unsigned * pPrev )
452 {
453  int i, Entry;
454  // find registers whose value has changed
455  Vec_IntClear( p->vRetired );
456  for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
457  if ( Gia_ManTerSimInfoGet( pThis, i ) != Gia_ManTerSimInfoGet( pPrev, i ) )
458  Vec_IntPush( p->vRetired, i );
459  // set all of them to zero
460  Vec_IntForEachEntry( p->vRetired, Entry, i )
461  Gia_ManTerSimInfoSet( p->pDataSimCis, Gia_ManPiNum(p->pAig)+Entry, GIA_UND );
462  return Vec_IntSize(p->vRetired);
463 }
464 
465 /**Function*************************************************************
466 
467  Synopsis [Inserts value into the table.]
468 
469  Description []
470 
471  SideEffects []
472 
473  SeeAlso []
474 
475 ***********************************************************************/
476 void Gia_ManTerStatePrint( unsigned * pState, int nRegs, int iNum )
477 {
478  int i, nZeros = 0, nOnes = 0, nDcs = 0;
479  printf( " %4d : ", iNum );
480  for ( i = 0; i < nRegs; i++ )
481  {
482  if ( Gia_ManTerSimInfoGet(pState, i) == GIA_ZER )
483  printf( "0" ), nZeros++;
484  else if ( Gia_ManTerSimInfoGet(pState, i) == GIA_ONE )
485  printf( "1" ), nOnes++;
486  else if ( Gia_ManTerSimInfoGet(pState, i) == GIA_UND )
487  printf( "x" ), nDcs++;
488  else
489  assert( 0 );
490  }
491  printf( " (0=%4d, 1=%4d, x=%4d)\n", nZeros, nOnes, nDcs );
492 }
493 
494 /**Function*************************************************************
495 
496  Synopsis []
497 
498  Description []
499 
500  SideEffects []
501 
502  SeeAlso []
503 
504 ***********************************************************************/
505 void Gia_ManTerAnalyze2( Vec_Ptr_t * vStates, int nRegs )
506 {
507  unsigned * pTemp, * pStates = (unsigned *)Vec_PtrPop( vStates );
508  int i, w, nZeros, nConsts, nStateWords;
509  // detect constant zero registers
510  nStateWords = Abc_BitWordNum( 2*nRegs );
511  memset( pStates, 0, sizeof(int) * nStateWords );
512  Vec_PtrForEachEntry( unsigned *, vStates, pTemp, i )
513  for ( w = 0; w < nStateWords; w++ )
514  pStates[w] |= pTemp[w];
515  // count the number of zeros
516  nZeros = 0;
517  for ( i = 0; i < nRegs; i++ )
518  if ( Gia_ManTerSimInfoGet(pStates, i) == GIA_ZER )
519  nZeros++;
520  printf( "Found %d constant registers.\n", nZeros );
521  // detect non-ternary registers
522  memset( pStates, 0, sizeof(int) * nStateWords );
523  Vec_PtrForEachEntry( unsigned *, vStates, pTemp, i )
524  for ( w = 0; w < nStateWords; w++ )
525  pStates[w] |= (~(pTemp[w] ^ (pTemp[w] >> 1)) & 0x55555555);
526  // count the nonternary registers
527  nConsts = 0;
528  for ( i = 0; i < nRegs; i++ )
529  if ( Gia_ManTerSimInfoGet(pStates, i) == 0 )
530  nConsts++;
531  printf( "Found %d non-ternary registers.\n", nConsts );
532  // return the state back
533  Vec_PtrPush( vStates, pStates );
534 }
535 
536 /**Function*************************************************************
537 
538  Synopsis []
539 
540  Description []
541 
542  SideEffects []
543 
544  SeeAlso []
545 
546 ***********************************************************************/
547 void Gia_ManTerAnalyze( Gia_ManTer_t * p )
548 {
549  int i, nZeros = 0, nConsts = 0;
550  for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
551  if ( p->pCount0[i] == Vec_PtrSize(p->vStates) )
552  nZeros++;
553  else if ( p->pCountX[i] == 0 )
554  nConsts++;
555 // printf( "Found %d constant registers.\n", nZeros );
556 // printf( "Found %d non-ternary registers.\n", nConsts );
557 }
558 
559 
560 
561 /**Function*************************************************************
562 
563  Synopsis [Transposes state vector for non-ternary registers.]
564 
565  Description []
566 
567  SideEffects []
568 
569  SeeAlso []
570 
571 ***********************************************************************/
572 Vec_Ptr_t * Gia_ManTerTranspose( Gia_ManTer_t * p )
573 {
574  Vec_Ptr_t * vFlops;
575  unsigned * pState, * pFlop;
576  int i, k, nFlopWords;
577  vFlops = Vec_PtrAlloc( 100 );
578  nFlopWords = Abc_BitWordNum( 2*Vec_PtrSize(p->vStates) );
579  for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
580  {
581  if ( p->pCount0[i] == Vec_PtrSize(p->vStates) )
582  continue;
583  if ( p->pCountX[i] > 0 )
584  continue;
585  pFlop = Gia_ManTerStateAlloc( nFlopWords );
586  Vec_PtrPush( vFlops, pFlop );
587  Vec_PtrForEachEntry( unsigned *, p->vStates, pState, k )
588  Gia_ManTerSimInfoSet( pFlop, k, Gia_ManTerSimInfoGet(pState, i) );
589 //Gia_ManTerStatePrint( pFlop, Vec_PtrSize(p->vStates), i );
590  }
591  return vFlops;
592 }
593 
594 /**Function*************************************************************
595 
596  Synopsis [Transposes state vector for non-ternary registers.]
597 
598  Description []
599 
600  SideEffects []
601 
602  SeeAlso []
603 
604 ***********************************************************************/
605 int Gia_ManFindEqualFlop( Vec_Ptr_t * vFlops, int iFlop, int nFlopWords )
606 {
607  unsigned * pFlop, * pTemp;
608  int i;
609  pFlop = (unsigned *)Vec_PtrEntry( vFlops, iFlop );
610  Vec_PtrForEachEntryStop( unsigned *, vFlops, pTemp, i, iFlop )
611  if ( !memcmp( pTemp, pFlop, sizeof(unsigned) * nFlopWords ) )
612  return i;
613  return -1;
614 }
615 
616 /**Function*************************************************************
617 
618  Synopsis [Creates map of registers to replace.]
619 
620  Description []
621 
622  SideEffects []
623 
624  SeeAlso []
625 
626 ***********************************************************************/
627 int * Gia_ManTerCreateMap( Gia_ManTer_t * p, int fVerbose )
628 {
629  int * pCi2Lit;
630  Gia_Obj_t * pObj;
631  Vec_Int_t * vMapKtoI;
632  int i, iRepr, nFlopWords, Counter0 = 0, CounterE = 0;
633  nFlopWords = Abc_BitWordNum( 2*Vec_PtrSize(p->vStates) );
634  p->vFlops = Gia_ManTerTranspose( p );
635  pCi2Lit = ABC_FALLOC( int, Gia_ManCiNum(p->pAig) );
636  vMapKtoI = Vec_IntAlloc( 100 );
637  for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
638  if ( p->pCount0[i] == Vec_PtrSize(p->vStates) )
639  pCi2Lit[Gia_ManPiNum(p->pAig)+i] = 0, Counter0++;
640  else if ( p->pCountX[i] == 0 )
641  {
642  iRepr = Gia_ManFindEqualFlop( p->vFlops, Vec_IntSize(vMapKtoI), nFlopWords );
643  Vec_IntPush( vMapKtoI, i );
644  if ( iRepr < 0 )
645  continue;
646  pObj = Gia_ManCi( p->pAig, Gia_ManPiNum(p->pAig)+Vec_IntEntry(vMapKtoI, iRepr) );
647  pCi2Lit[Gia_ManPiNum(p->pAig)+i] = Abc_Var2Lit( Gia_ObjId( p->pAig, pObj ), 0 );
648  CounterE++;
649  }
650  Vec_IntFree( vMapKtoI );
651  if ( fVerbose )
652  printf( "Transforming %d const and %d equiv registers.\n", Counter0, CounterE );
653  return pCi2Lit;
654 }
655 
656 
657 /**Function*************************************************************
658 
659  Synopsis []
660 
661  Description []
662 
663  SideEffects []
664 
665  SeeAlso []
666 
667 ***********************************************************************/
668 Gia_ManTer_t * Gia_ManTerSimulate( Gia_Man_t * pAig, int fVerbose )
669 {
670  Gia_ManTer_t * p;
671  unsigned * pState, * pPrev, * pLoop;
672  int i, Counter;
673  abctime clk, clkTotal = Abc_Clock();
674  assert( Gia_ManRegNum(pAig) > 0 );
675  // create manager
676  clk = Abc_Clock();
677  p = Gia_ManTerCreate( pAig );
678  if ( 0 )
679  {
680  printf( "Obj = %8d (%8d). F = %6d. ",
681  pAig->nObjs, Gia_ManCiNum(pAig) + Gia_ManAndNum(pAig), p->pAig->nFront );
682  printf( "AIG = %7.2f MB. F-mem = %7.2f MB. Other = %7.2f MB. ",
683  12.0*Gia_ManObjNum(p->pAig)/(1<<20),
684  4.0*Abc_BitWordNum(2 * p->pAig->nFront)/(1<<20),
685  4.0*Abc_BitWordNum(2 * (Gia_ManCiNum(pAig) + Gia_ManCoNum(pAig)))/(1<<20) );
686  ABC_PRT( "Time", Abc_Clock() - clk );
687  }
688  // perform simulation
689  Gia_ManTerSimInfoInit( p );
690  // hash the first state
691  pState = Gia_ManTerStateCreate( p );
692  Gia_ManTerStateInsert( pState, p->nStateWords, p->pBins, p->nBins );
693 //Gia_ManTerStatePrint( pState, Gia_ManRegNum(pAig), 0 );
694  // perform simuluation till convergence
695  pPrev = NULL;
696  for ( i = 0; ; i++ )
697  {
698  Gia_ManTerSimulateRound( p );
699  Gia_ManTerSimInfoTransfer( p );
700  pState = Gia_ManTerStateCreate( p );
701 //Gia_ManTerStatePrint( pState, Gia_ManRegNum(pAig), i+1 );
702  if ( (pLoop = Gia_ManTerStateLookup(pState, p->nStateWords, p->pBins, p->nBins)) )
703  {
704  pAig->nTerStates = Vec_PtrSize( p->vStates );
705  pAig->nTerLoop = Vec_PtrFind( p->vStates, pLoop );
706  break;
707  }
708  Gia_ManTerStateInsert( pState, p->nStateWords, p->pBins, p->nBins );
709  if ( i >= p->nIters && i % 10 == 0 )
710  {
711  Counter = Gia_ManTerRetire( p, pState, pPrev );
712 // Counter = Gia_ManTerRetire2( p, pState );
713 // if ( fVerbose )
714 // printf( "Retired %d registers.\n", Counter );
715  }
716  pPrev = pState;
717  }
718  if ( fVerbose )
719  {
720  printf( "Ternary simulation saturated after %d iterations. ", i+1 );
721  ABC_PRT( "Time", Abc_Clock() - clkTotal );
722  }
723  return p;
724 }
725 
726 /**Function*************************************************************
727 
728  Synopsis []
729 
730  Description []
731 
732  SideEffects []
733 
734  SeeAlso []
735 
736 ***********************************************************************/
737 Gia_Man_t * Gia_ManReduceConst( Gia_Man_t * pAig, int fVerbose )
738 {
739  Gia_ManTer_t * p;
740  Gia_Man_t * pNew = NULL;
741  int * pCi2Lit;
742  p = Gia_ManTerSimulate( pAig, fVerbose );
743  Gia_ManTerAnalyze( p );
744  pCi2Lit = Gia_ManTerCreateMap( p, fVerbose );
745  Gia_ManTerDelete( p );
746  pNew = Gia_ManDupDfsCiMap( pAig, pCi2Lit, NULL );
747  ABC_FREE( pCi2Lit );
748  return pNew;
749 }
750 
751 ////////////////////////////////////////////////////////////////////////
752 /// END OF FILE ///
753 ////////////////////////////////////////////////////////////////////////
754 
755 
756 ABC_NAMESPACE_IMPL_END
757 
memset
char * memset()
Gia_ManTerStatesFree
void Gia_ManTerStatesFree(Vec_Ptr_t *vStates)
Definition: giaTsim.c:113
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_PrimeCudd
static int Abc_PrimeCudd(unsigned int p)
Definition: abc_global.h:383
Gia_ManTer_t_::nIters
int nIters
Definition: giaTsim.c:49
GIA_UND
#define GIA_UND
Definition: gia.h:749
Gia_ManStop
void Gia_ManStop(Gia_Man_t *p)
Definition: giaMan.c:77
Gia_ManTer_t_::vFlops
Vec_Ptr_t * vFlops
Definition: giaTsim.c:52
Gia_ManTerSimInfoTransfer
static void Gia_ManTerSimInfoTransfer(Gia_ManTer_t *p)
Definition: giaTsim.c:233
Gia_ManTer_t_::pRetired
char * pRetired
Definition: giaTsim.c:54
Gia_ManTer_t_::pBins
unsigned ** pBins
Definition: giaTsim.c:59
Gia_ManTer_t_::vStates
Vec_Ptr_t * vStates
Definition: giaTsim.c:51
Gia_ObjFaninC1
static int Gia_ObjFaninC1(Gia_Obj_t *pObj)
Definition: gia.h:452
Gia_ManCi
static Gia_Obj_t * Gia_ManCi(Gia_Man_t *p, int v)
Definition: gia.h:403
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Gia_Man_t_::nFront
int nFront
Definition: gia.h:119
Gia_ManTer_t_::pDataSimCis
unsigned * pDataSimCis
Definition: giaTsim.c:62
GIA_ZER
#define GIA_ZER
Definition: gia.h:747
Gia_ObjDiff1
static int Gia_ObjDiff1(Gia_Obj_t *pObj)
Definition: gia.h:450
Abc_Var2Lit
static int Abc_Var2Lit(int Var, int fCompl)
Definition: abc_global.h:263
Gia_Man_t_::nTerStates
int nTerStates
Definition: gia.h:126
Gia_ObjValue
static int Gia_ObjValue(Gia_Obj_t *pObj)
Definition: gia.h:413
Gia_ManTer_t_::pDataSim
unsigned * pDataSim
Definition: giaTsim.c:61
Gia_ManTerSimulateCi
static void Gia_ManTerSimulateCi(Gia_ManTer_t *p, Gia_Obj_t *pObj, int iCi)
Definition: giaTsim.c:162
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Gia_XsimNotCond
static int Gia_XsimNotCond(int Value, int fCompl)
Definition: gia.h:751
Gia_ManTerDelete
void Gia_ManTerDelete(Gia_ManTer_t *p)
Definition: giaTsim.c:133
Gia_ManTerRetire2
int Gia_ManTerRetire2(Gia_ManTer_t *p, unsigned *pState)
Definition: giaTsim.c:415
Gia_XsimAndCond
static int Gia_XsimAndCond(int Value0, int fCompl0, int Value1, int fCompl1)
Definition: gia.h:759
Gia_ManTerStateCreate
unsigned * Gia_ManTerStateCreate(Gia_ManTer_t *p)
Definition: giaTsim.c:346
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Gia_Man_t_::nObjs
int nObjs
Definition: gia.h:101
Gia_ManTerStateAlloc
unsigned * Gia_ManTerStateAlloc(int nWords)
Definition: giaTsim.c:330
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Gia_ManTer_t_::pDataSimCos
unsigned * pDataSimCos
Definition: giaTsim.c:63
Vec_PtrPop
static void * Vec_PtrPop(Vec_Ptr_t *p)
Definition: vecPtr.h:677
nWords
int nWords
Definition: abcNpn.c:127
Gia_ManTerStateSetNext
static void Gia_ManTerStateSetNext(unsigned *pState, int nWords, unsigned *pNext)
Definition: giaTsim.c:42
Gia_Obj_t_
Definition: gia.h:75
Vec_PtrFind
static int Vec_PtrFind(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:694
Gia_ManTerSimulateRound
static void Gia_ManTerSimulateRound(Gia_ManTer_t *p)
Definition: giaTsim.c:374
Gia_ManTerSimInfoInit
static void Gia_ManTerSimInfoInit(Gia_ManTer_t *p)
Definition: giaTsim.c:213
Gia_ManTerSimInfoSet
static void Gia_ManTerSimInfoSet(unsigned *pInfo, int i, int Value)
Definition: giaTsim.c:34
Gia_ManAndNum
static int Gia_ManAndNum(Gia_Man_t *p)
Definition: gia.h:389
Gia_ManTerStateInsert
void Gia_ManTerStateInsert(unsigned *pState, int nWords, unsigned **pBins, int nBins)
Definition: giaTsim.c:311
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Gia_ManTerStateHash
int Gia_ManTerStateHash(unsigned *pState, int nWords, int nTableSize)
Definition: giaTsim.c:254
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
Gia_ManFront
Gia_Man_t * Gia_ManFront(Gia_Man_t *p)
Definition: giaFront.c:147
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Gia_ObjIsAndOrConst0
static int Gia_ObjIsAndOrConst0(Gia_Obj_t *pObj)
Definition: gia.h:419
Gia_ManTer_t_::pCountX
int * pCountX
Definition: giaTsim.c:56
memcmp
int memcmp()
Gia_ManTerStateNext
static unsigned * Gia_ManTerStateNext(unsigned *pState, int nWords)
Definition: giaTsim.c:41
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Gia_ObjId
static int Gia_ObjId(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:410
Gia_ManTer_t_::vRetired
Vec_Int_t * vRetired
Definition: giaTsim.c:53
Counter
static int Counter
Definition: extraBddMisc.c:1877
Gia_ManTer_t_::pCount0
int * pCount0
Definition: giaTsim.c:55
Gia_ManTerRetire
int Gia_ManTerRetire(Gia_ManTer_t *p, unsigned *pThis, unsigned *pPrev)
Definition: giaTsim.c:451
Gia_ManTer_t_::nStateWords
int nStateWords
Definition: giaTsim.c:50
Gia_ObjDiff0
static int Gia_ObjDiff0(Gia_Obj_t *pObj)
Definition: gia.h:449
Gia_ManTer_t_
Definition: giaTsim.c:46
Gia_ManTer_t_::pAig
Gia_Man_t * pAig
Definition: giaTsim.c:48
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Gia_ManDupDfsCiMap
Gia_Man_t * Gia_ManDupDfsCiMap(Gia_Man_t *p, int *pCi2Lit, Vec_Int_t *vLits)
Definition: giaDup.c:1890
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Gia_ManCiNum
static int Gia_ManCiNum(Gia_Man_t *p)
Definition: gia.h:383
Gia_ManTerAnalyze
void Gia_ManTerAnalyze(Gia_ManTer_t *p)
Definition: giaTsim.c:547
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Vec_PtrForEachEntryStop
#define Vec_PtrForEachEntryStop(Type, vVec, pEntry, i, Stop)
Definition: vecPtr.h:59
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Gia_Man_t_
Definition: gia.h:95
ABC_PRT
#define ABC_PRT(a, t)
Definition: abc_global.h:220
Gia_ManTerCreateMap
int * Gia_ManTerCreateMap(Gia_ManTer_t *p, int fVerbose)
Definition: giaTsim.c:627
Gia_ManTerCreate
Gia_ManTer_t * Gia_ManTerCreate(Gia_Man_t *pAig)
FUNCTION DEFINITIONS ///.
Definition: giaTsim.c:81
Gia_ManConst0
static Gia_Obj_t * Gia_ManConst0(Gia_Man_t *p)
Definition: gia.h:400
GIA_NONE
#define GIA_NONE
INCLUDES ///.
Definition: gia.h:44
Gia_Man_t_::nTerLoop
int nTerLoop
Definition: gia.h:125
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
Gia_ManTerStateLookup
unsigned * Gia_ManTerStateLookup(unsigned *pState, int nWords, unsigned **pBins, int nBins)
Definition: giaTsim.c:290
Gia_ManReduceConst
Gia_Man_t * Gia_ManReduceConst(Gia_Man_t *pAig, int fVerbose)
Definition: giaTsim.c:737
Abc_BitWordNum
static int Abc_BitWordNum(int nBits)
Definition: abc_global.h:255
assert
#define assert(ex)
Definition: util_old.h:213
Gia_Obj_t_::Value
unsigned Value
Definition: gia.h:87
Gia_ManForEachObj1
#define Gia_ManForEachObj1(p, pObj, i)
Definition: gia.h:986
Gia_ManFindEqualFlop
int Gia_ManFindEqualFlop(Vec_Ptr_t *vFlops, int iFlop, int nFlopWords)
Definition: giaTsim.c:605
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
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Gia_ManPiNum
static int Gia_ManPiNum(Gia_Man_t *p)
Definition: gia.h:385
Vec_IntClear
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Gia_ObjIsCi
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
Gia_ManTerTranspose
Vec_Ptr_t * Gia_ManTerTranspose(Gia_ManTer_t *p)
Definition: giaTsim.c:572
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Gia_ManTerSimulateNode
static void Gia_ManTerSimulateNode(Gia_ManTer_t *p, Gia_Obj_t *pObj)
Definition: giaTsim.c:195
Gia_ManTerSimulate
Gia_ManTer_t * Gia_ManTerSimulate(Gia_Man_t *pAig, int fVerbose)
Definition: giaTsim.c:668
Gia_ManTerSimulateCo
static void Gia_ManTerSimulateCo(Gia_ManTer_t *p, int iCo, Gia_Obj_t *pObj)
Definition: giaTsim.c:178
Gia_ManTerStatePrint
void Gia_ManTerStatePrint(unsigned *pState, int nRegs, int iNum)
Definition: giaTsim.c:476
Gia_ManObjNum
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
ABC_FALLOC
#define ABC_FALLOC(type, num)
Definition: abc_global.h:231
GIA_ONE
#define GIA_ONE
Definition: gia.h:748
Gia_ManTer_t_::nBins
int nBins
Definition: giaTsim.c:58
Gia_ManTerSimInfoGet
static ABC_NAMESPACE_IMPL_START int Gia_ManTerSimInfoGet(unsigned *pInfo, int i)
DECLARATIONS ///.
Definition: giaTsim.c:30
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
Gia_ManCoNum
static int Gia_ManCoNum(Gia_Man_t *p)
Definition: gia.h:384
Gia_ManTerAnalyze2
void Gia_ManTerAnalyze2(Vec_Ptr_t *vStates, int nRegs)
Definition: giaTsim.c:505
Gia_ManRegNum
static int Gia_ManRegNum(Gia_Man_t *p)
Definition: gia.h:387