abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
mapperTable.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [mapperTable.c]
4 
5  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6 
7  Synopsis [Generic technology mapping engine.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 2.0. Started - June 1, 2004.]
14 
15  Revision [$Id: mapperTable.c,v 1.6 2005/01/23 06:59:44 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "mapperInt.h"
20 
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 // the table function for the tables
29 #define MAP_TABLE_HASH(u1,u2,nSize) (((u1) + 2003 * (u2)) % nSize)
30 
31 static void Map_SuperTableResize( Map_HashTable_t * pLib );
32 
33 ////////////////////////////////////////////////////////////////////////
34 /// FUNCTION DEFINITIONS ///
35 ////////////////////////////////////////////////////////////////////////
36 
37 /**Function*************************************************************
38 
39  Synopsis [Creates the hash table for supergates.]
40 
41  Description []
42 
43  SideEffects []
44 
45  SeeAlso []
46 
47 ***********************************************************************/
49 {
51  // allocate the table
52  p = ABC_ALLOC( Map_HashTable_t, 1 );
53  memset( p, 0, sizeof(Map_HashTable_t) );
54  p->mmMan = pLib->mmEntries;
55  // allocate and clean the bins
56  p->nBins = Abc_PrimeCudd(20000);
57  p->pBins = ABC_ALLOC( Map_HashEntry_t *, p->nBins );
58  memset( p->pBins, 0, sizeof(Map_HashEntry_t *) * p->nBins );
59  return p;
60 }
61 
62 
63 /**Function*************************************************************
64 
65  Synopsis [Deallocates the supergate hash table.]
66 
67  Description []
68 
69  SideEffects []
70 
71  SeeAlso []
72 
73 ***********************************************************************/
75 {
76  ABC_FREE( p->pBins );
77  ABC_FREE( p );
78 }
79 
80 /**Function*************************************************************
81 
82  Synopsis [Inserts a new entry into the hash table.]
83 
84  Description [This function inserts the new gate (pGate), which will be
85  accessible through its canonical form (uTruthC).]
86 
87  SideEffects []
88 
89  SeeAlso []
90 
91 ***********************************************************************/
92 int Map_SuperTableInsertC( Map_HashTable_t * p, unsigned uTruthC[], Map_Super_t * pGate )
93 {
94  Map_HashEntry_t * pEnt;
95  unsigned Key;
96  // resize the table
97  if ( p->nEntries >= 2 * p->nBins )
99  // check if another supergate with the same canonical form exists
100  Key = MAP_TABLE_HASH( uTruthC[0], uTruthC[1], p->nBins );
101  for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
102  if ( pEnt->uTruth[0] == uTruthC[0] && pEnt->uTruth[1] == uTruthC[1] )
103  break;
104  // create a new entry if it does not exist
105  if ( pEnt == NULL )
106  {
107  // add the new entry to the table
109  memset( pEnt, 0, sizeof(Map_HashEntry_t) );
110  pEnt->uTruth[0] = uTruthC[0];
111  pEnt->uTruth[1] = uTruthC[1];
112  // add the hash table entry to the corresponding linked list in the table
113  pEnt->pNext = p->pBins[Key];
114  p->pBins[Key] = pEnt;
115  p->nEntries++;
116  }
117  // add the supergate to the entry
118  pGate->pNext = pEnt->pGates;
119  pEnt->pGates = pGate;
120  return 0;
121 }
122 
123 
124 
125 /**Function*************************************************************
126 
127  Synopsis [Inserts a new entry into the library.]
128 
129  Description [This function inserts the new gate (pGate), which will be
130  accessible through its unfolded function (uTruth).]
131 
132  SideEffects []
133 
134  SeeAlso []
135 
136 ***********************************************************************/
137 int Map_SuperTableInsert( Map_HashTable_t * p, unsigned uTruth[], Map_Super_t * pGate, unsigned uPhase )
138 {
139  Map_HashEntry_t * pEnt;
140  unsigned Key;
141  // resize the table
142  if ( p->nEntries >= 2 * p->nBins )
144  // check if this entry already exists
145  Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins );
146  for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
147  if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
148  return 1;
149  // add the new hash table entry to the table
151  memset( pEnt, 0, sizeof(Map_HashEntry_t) );
152  pEnt->uTruth[0] = uTruth[0];
153  pEnt->uTruth[1] = uTruth[1];
154  pEnt->pGates = pGate;
155  pEnt->uPhase = uPhase;
156  // add the hash table to the corresponding linked list in the table
157  pEnt->pNext = p->pBins[Key];
158  p->pBins[Key] = pEnt;
159  p->nEntries++;
160 /*
161 printf( "Adding gate: %10u ", Key );
162 Map_LibraryPrintSupergate( pGate );
163 Extra_PrintBinary( stdout, uTruth, 32 );
164 printf( "\n" );
165 */
166  return 0;
167 }
168 
169 /**Function*************************************************************
170 
171  Synopsis [Looks up an entry in the library.]
172 
173  Description [This function looks up the function, given by its truth table,
174  and return two things: (1) the linked list of supergates, which can implement
175  the functions of this N-class; (2) the phase, which should be applied to the
176  given function, in order to derive the canonical form of this N-class.]
177 
178  SideEffects []
179 
180  SeeAlso []
181 
182 ***********************************************************************/
184 {
185  Map_HashEntry_t * pEnt;
186  unsigned Key;
187  Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->tTableC->nBins );
188  for ( pEnt = p->tTableC->pBins[Key]; pEnt; pEnt = pEnt->pNext )
189  if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
190  return pEnt->pGates;
191  return NULL;
192 }
193 
194 /**Function*************************************************************
195 
196  Synopsis [Looks up an entry in the library.]
197 
198  Description [This function looks up the function, given by its truth table,
199  and return two things: (1) the linked list of supergates, which can implement
200  the functions of this N-class; (2) the phase, which should be applied to the
201  given function, in order to derive the canonical form of this N-class.]
202 
203  SideEffects []
204 
205  SeeAlso []
206 
207 ***********************************************************************/
208 Map_Super_t * Map_SuperTableLookup( Map_HashTable_t * p, unsigned uTruth[], unsigned * puPhase )
209 {
210  Map_HashEntry_t * pEnt;
211  unsigned Key;
212  Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins );
213  for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
214  if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
215  {
216  *puPhase = pEnt->uPhase;
217  return pEnt->pGates;
218  }
219  return NULL;
220 }
221 
222 /**Function*************************************************************
223 
224  Synopsis [Resizes the table.]
225 
226  Description []
227 
228  SideEffects []
229 
230  SeeAlso []
231 
232 ***********************************************************************/
234 {
235  Map_HashEntry_t ** pBinsNew;
236  Map_HashEntry_t * pEnt, * pEnt2;
237  int nBinsNew, Counter, i;
238  unsigned Key;
239  // get the new table size
240  nBinsNew = Abc_PrimeCudd(2 * p->nBins);
241  // allocate a new array
242  pBinsNew = ABC_ALLOC( Map_HashEntry_t *, nBinsNew );
243  memset( pBinsNew, 0, sizeof(Map_HashEntry_t *) * nBinsNew );
244  // rehash the entries from the old table
245  Counter = 0;
246  for ( i = 0; i < p->nBins; i++ )
247  for ( pEnt = p->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt;
248  pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
249  {
250  Key = MAP_TABLE_HASH( pEnt->uTruth[0], pEnt->uTruth[1], nBinsNew );
251  pEnt->pNext = pBinsNew[Key];
252  pBinsNew[Key] = pEnt;
253  Counter++;
254  }
255  assert( Counter == p->nEntries );
256  // replace the table and the parameters
257  ABC_FREE( p->pBins );
258  p->pBins = pBinsNew;
259  p->nBins = nBinsNew;
260 }
261 
262 /**Function*************************************************************
263 
264  Synopsis [Compares the supergates by the number of times they are used.]
265 
266  Description []
267 
268  SideEffects []
269 
270  SeeAlso []
271 
272 ***********************************************************************/
274 {
275  if ( (*ppS1)->nUsed > (*ppS2)->nUsed )
276  return -1;
277  if ( (*ppS1)->nUsed < (*ppS2)->nUsed )
278  return 1;
279  return 0;
280 }
281 
282 /**Function*************************************************************
283 
284  Synopsis [Compares the supergates by the number of times they are used.]
285 
286  Description []
287 
288  SideEffects []
289 
290  SeeAlso []
291 
292 ***********************************************************************/
294 {
295 // if ( (*ppS1)->tDelayMax.Rise > (*ppS2)->tDelayMax.Rise )
296  if ( (*ppS1)->Area > (*ppS2)->Area )
297  return -1;
298 // if ( (*ppS1)->tDelayMax.Rise < (*ppS2)->tDelayMax.Rise )
299  if ( (*ppS1)->Area < (*ppS2)->Area )
300  return 1;
301  return 0;
302 }
303 
304 /**Function*************************************************************
305 
306  Synopsis [Sorts supergates by usefulness and prints out most useful.]
307 
308  Description []
309 
310  SideEffects []
311 
312  SeeAlso []
313 
314 ***********************************************************************/
316 {
317  Map_HashEntry_t * pEnt;
318  Map_Super_t ** ppSupers;
319  Map_Super_t * pSuper;
320  int nSupers, i;
321 
322  // copy all the supergates into one array
323  ppSupers = ABC_ALLOC( Map_Super_t *, nSupersMax );
324  nSupers = 0;
325  for ( i = 0; i < p->nBins; i++ )
326  for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext )
327  for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext )
328  ppSupers[nSupers++] = pSuper;
329 
330  // sort by usage
331  qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *),
332  (int (*)(const void *, const void *)) Map_SuperTableCompareSupergates );
333  assert( Map_SuperTableCompareSupergates( ppSupers, ppSupers + nSupers - 1 ) <= 0 );
334 
335  // print out the "top ten"
336 // for ( i = 0; i < nSupers; i++ )
337  for ( i = 0; i < 10; i++ )
338  {
339  if ( ppSupers[i]->nUsed == 0 )
340  break;
341  printf( "%5d : ", ppSupers[i]->nUsed );
342  printf( "%5d ", ppSupers[i]->Num );
343  printf( "A = %5.2f ", ppSupers[i]->Area );
344  printf( "D = %5.2f ", ppSupers[i]->tDelayMax.Rise );
345  printf( "%s", ppSupers[i]->pFormula );
346  printf( "\n" );
347  }
348  ABC_FREE( ppSupers );
349 }
350 
351 /**Function*************************************************************
352 
353  Synopsis [Sorts supergates by max delay for each truth table.]
354 
355  Description []
356 
357  SideEffects []
358 
359  SeeAlso []
360 
361 ***********************************************************************/
363 {
364  Map_HashEntry_t * pEnt;
365  Map_Super_t ** ppSupers;
366  Map_Super_t * pSuper;
367  int nSupers, i, k;
368 
369  ppSupers = ABC_ALLOC( Map_Super_t *, nSupersMax );
370  for ( i = 0; i < p->nBins; i++ )
371  for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext )
372  {
373  // collect the gates in this entry
374  nSupers = 0;
375  for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext )
376  {
377  // skip supergates, whose root is the AND gate
378 // if ( strcmp( Mio_GateReadName(pSuper->pRoot), "and" ) == 0 )
379 // continue;
380  ppSupers[nSupers++] = pSuper;
381  }
382  pEnt->pGates = NULL;
383  if ( nSupers == 0 )
384  continue;
385  // sort the gates by delay
386  qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *),
387  (int (*)(const void *, const void *)) Map_SuperTableCompareGatesInList );
388  assert( Map_SuperTableCompareGatesInList( ppSupers, ppSupers + nSupers - 1 ) <= 0 );
389  // link them in the reverse order
390  for ( k = 0; k < nSupers; k++ )
391  {
392  ppSupers[k]->pNext = pEnt->pGates;
393  pEnt->pGates = ppSupers[k];
394  }
395  // save the number of supergates in the list
396  pEnt->pGates->nSupers = nSupers;
397  }
398  ABC_FREE( ppSupers );
399 }
400 
401 ////////////////////////////////////////////////////////////////////////
402 /// END OF FILE ///
403 ////////////////////////////////////////////////////////////////////////
404 
405 
407 
Map_HashEntry_t * pNext
Definition: mapperInt.h:321
char * memset()
static int Abc_PrimeCudd(unsigned int p)
Definition: abc_global.h:383
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Map_Super_t * Map_SuperTableLookupC(Map_SuperLib_t *p, unsigned uTruth[])
Definition: mapperTable.c:183
unsigned nSupers
Definition: mapperInt.h:283
void Map_SuperTableSortSupergates(Map_HashTable_t *p, int nSupersMax)
Definition: mapperTable.c:315
#define MAP_TABLE_HASH(u1, u2, nSize)
DECLARATIONS ///.
Definition: mapperTable.c:29
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Map_HashEntry_t ** pBins
Definition: mapperInt.h:309
void Map_SuperTableFree(Map_HashTable_t *p)
Definition: mapperTable.c:74
int Map_SuperTableInsertC(Map_HashTable_t *p, unsigned uTruthC[], Map_Super_t *pGate)
Definition: mapperTable.c:92
char * Extra_MmFixedEntryFetch(Extra_MmFixed_t *p)
static void Map_SuperTableResize(Map_HashTable_t *pLib)
Definition: mapperTable.c:233
void Map_SuperTableSortSupergatesByDelay(Map_HashTable_t *p, int nSupersMax)
Definition: mapperTable.c:362
Map_HashTable_t * Map_SuperTableCreate(Map_SuperLib_t *pLib)
FUNCTION DEFINITIONS ///.
Definition: mapperTable.c:48
unsigned uTruth[2]
Definition: mapperInt.h:318
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
int Map_SuperTableCompareGatesInList(Map_Super_t **ppS1, Map_Super_t **ppS2)
Definition: mapperTable.c:293
static int Counter
Map_Super_t * Map_SuperTableLookup(Map_HashTable_t *p, unsigned uTruth[], unsigned *puPhase)
Definition: mapperTable.c:208
Extra_MmFixed_t * mmEntries
Definition: mapperInt.h:196
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
#define ABC_FREE(obj)
Definition: abc_global.h:232
Map_Super_t * pGates
Definition: mapperInt.h:320
int Map_SuperTableInsert(Map_HashTable_t *p, unsigned uTruth[], Map_Super_t *pGate, unsigned uPhase)
Definition: mapperTable.c:137
Extra_MmFixed_t * mmMan
Definition: mapperInt.h:312
#define assert(ex)
Definition: util_old.h:213
Map_HashTable_t * tTableC
Definition: mapperInt.h:180
int Map_SuperTableCompareSupergates(Map_Super_t **ppS1, Map_Super_t **ppS2)
Definition: mapperTable.c:273
Map_Super_t * pNext
Definition: mapperInt.h:295