1 /**CFile****************************************************************
2
3 FileName [superGate.c]
4
5 PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6
7 Synopsis [Pre-computation of supergates.]
8
9 Author [MVSIS Group]
10
11 Affiliation [UC Berkeley]
12
13 Date [Ver. 1.0. Started - September 8, 2003.]
14
15 Revision [$Id: superGate.c,v 1.7 2004/08/03 00:11:40 satrajit Exp $]
16
17 ***********************************************************************/
18
19 #include <math.h>
20 #include "superInt.h"
21
22 ABC_NAMESPACE_IMPL_START
23
24
25 ////////////////////////////////////////////////////////////////////////
26 /// DECLARATIONS ///
27 ////////////////////////////////////////////////////////////////////////
28
29 // the bit masks
30 #define SUPER_MASK(n) ((~((unsigned)0)) >> (32-(n)))
31 #define SUPER_FULL (~((unsigned)0))
32 #define SUPER_NO_VAR (-9999.0)
33 #define SUPER_EPSILON (0.001)
34
35 // data structure for supergate precomputation
36 typedef struct Super_ManStruct_t_ Super_Man_t; // manager
37 typedef struct Super_GateStruct_t_ Super_Gate_t; // supergate
38
39 struct Super_ManStruct_t_
40 {
41 // parameters
42 char * pName; // the original genlib file name
43 int nVarsMax; // the number of inputs
44 int nMints; // the number of minterms
45 int nLevels; // the number of logic levels
46 int nGatesMax; // the number of gates computed
47 float tDelayMax; // the max delay of the supergates in the library
48 float tAreaMax; // the max area of the supergates in the library
49 int fSkipInv; // the flag says about skipping inverters
50 int fWriteOldFormat; // in addition, writes the file in the old format
51 int fVerbose;
52
53 // supergates
54 Super_Gate_t * pInputs[10]; // the input supergates
55 int nGates; // the number of gates in the library
56 Super_Gate_t ** pGates; // the gates themselves
57 stmm_table * tTable; // mapping of truth tables into gates
58
59 // memory managers
60 Extra_MmFixed_t * pMem; // memory manager for the supergates
61 Extra_MmFlex_t * pMemFlex; // memory manager for the fanin arrays
62
63 // statistics
64 int nTried; // the total number of tried
65 int nAdded; // the number of entries added
66 int nRemoved; // the number of entries removed
67 int nClasses; // the number of gate classes
68 int nUnique; // the number of unique gates
69 int nLookups; // the number of hash table lookups
70 int nAliases; // the number of hash table lookups thrown away due to aliasing
71
72 // runtime
73 abctime Time; // the runtime of the generation procedure
74 int TimeLimit; // the runtime limit (in seconds)
75 int TimeSec; // the time passed (in seconds)
76 abctime TimeStop; // the time to stop computation (in miliseconds)
77 abctime TimePrint; // the time to print message
78 };
79
80 struct Super_GateStruct_t_
81 {
82 Mio_Gate_t * pRoot; // the root gate for this supergate
83 unsigned fVar : 1; // the flag signaling the elementary variable
84 unsigned fSuper : 1; // the flag signaling the elementary variable
85 unsigned nFanins : 6; // the number of fanin gates
86 unsigned Number : 24; // the number assigned in the process
87 unsigned uTruth[2]; // the truth table of this supergate
88 Super_Gate_t * pFanins[6]; // the fanins of the gate
89 float Area; // the area of this gate
90 float ptDelays[6]; // the pin-to-pin delays for all inputs
91 float tDelayMax; // the maximum delay
92 Super_Gate_t * pNext; // the next gate in the table
93 };
94
95
96 // iterating through the gates in the library
97 #define Super_ManForEachGate( GateArray, Limit, Index, Gate ) \
98 for ( Index = 0; \
99 Index < Limit && (Gate = GateArray[Index]); \
100 Index++ )
101
102 // static functions
103 static Super_Man_t * Super_ManStart();
104 static void Super_ManStop( Super_Man_t * pMan );
105
106 static void Super_AddGateToTable( Super_Man_t * pMan, Super_Gate_t * pGate );
107 static void Super_First( Super_Man_t * pMan, int nVarsMax );
108 static Super_Man_t * Super_Compute( Super_Man_t * pMan, Mio_Gate_t ** ppGates, int nGates, int nGatesMax, int fSkipInv );
109 static Super_Gate_t * Super_CreateGateNew( Super_Man_t * pMan, Mio_Gate_t * pRoot, Super_Gate_t ** pSupers, int nSupers, unsigned uTruth[], float Area, float tPinDelaysRes[], float tDelayMax, int nPins );
110 static int Super_CompareGates( Super_Man_t * pMan, unsigned uTruth[], float Area, float tPinDelaysRes[], int nPins );
111 static int Super_DelayCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 );
112 static int Super_AreaCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 );
113 static void Super_TranferGatesToArray( Super_Man_t * pMan );
114 static int Super_CheckTimeout( ProgressBar * pPro, Super_Man_t * pMan );
115
116 static Vec_Str_t * Super_Write( Super_Man_t * pMan );
117 static int Super_WriteCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 );
118 static void Super_WriteFileHeader( Super_Man_t * pMan, FILE * pFile );
119
120 static void Super_WriteLibrary( Super_Man_t * pMan );
121
122 static void Super_WriteLibraryTreeFile( Super_Man_t * pMan );
123 static Vec_Str_t * Super_WriteLibraryTreeStr( Super_Man_t * pMan );
124
125 ////////////////////////////////////////////////////////////////////////
126 /// FUNCTION DEFINITIONS ///
127 ////////////////////////////////////////////////////////////////////////
128
129 /**Function*************************************************************
130
131 Synopsis [Precomputes the library of supergates.]
132
133 Description []
134
135 SideEffects []
136
137 SeeAlso []
138
139 ***********************************************************************/
Super_Precompute(Mio_Library_t * pLibGen,int nVarsMax,int nLevels,int nGatesMax,float tDelayMax,float tAreaMax,int TimeLimit,int fSkipInv,int fVerbose,char * pFileName)140 void Super_Precompute( Mio_Library_t * pLibGen, int nVarsMax, int nLevels, int nGatesMax, float tDelayMax, float tAreaMax, int TimeLimit, int fSkipInv, int fVerbose, char * pFileName )
141 {
142 Vec_Str_t * vStr;
143 FILE * pFile = fopen( pFileName, "wb" );
144 if ( pFile == NULL )
145 {
146 printf( "Cannot open output file \"%s\".\n", pFileName );
147 return;
148 }
149 vStr = Super_PrecomputeStr( pLibGen, nVarsMax, nLevels, nGatesMax, tDelayMax, tAreaMax, TimeLimit, fSkipInv, fVerbose );
150 fwrite( Vec_StrArray(vStr), 1, Vec_StrSize(vStr), pFile );
151 fclose( pFile );
152 Vec_StrFree( vStr );
153 // report the result of writing
154 if ( fVerbose )
155 {
156 printf( "The supergates are written using new format \"%s\" ", pFileName );
157 printf( "(%0.3f MB).\n", ((double)Extra_FileSize(pFileName))/(1<<20) );
158 }
159 }
160
161 /**Function*************************************************************
162
163 Synopsis [Precomputes the library of supergates.]
164
165 Description []
166
167 SideEffects []
168
169 SeeAlso []
170
171 ***********************************************************************/
Super_PrecomputeStr(Mio_Library_t * pLibGen,int nVarsMax,int nLevels,int nGatesMax,float tDelayMax,float tAreaMax,int TimeLimit,int fSkipInv,int fVerbose)172 Vec_Str_t * Super_PrecomputeStr( Mio_Library_t * pLibGen, int nVarsMax, int nLevels, int nGatesMax, float tDelayMax, float tAreaMax, int TimeLimit, int fSkipInv, int fVerbose )
173 {
174 Vec_Str_t * vStr;
175 Super_Man_t * pMan;
176 Mio_Gate_t ** ppGates;
177 int nGates, Level;
178 abctime clk, clockStart;
179
180 assert( nVarsMax < 7 );
181 if ( nGatesMax && nGatesMax < nVarsMax )
182 {
183 fprintf( stderr, "Erro! The number of supergates requested (%d) in less than the number of variables (%d).\n", nGatesMax, nVarsMax );
184 fprintf( stderr, "The library cannot be computed.\n" );
185 return NULL;
186 }
187
188 // get the root gates
189 ppGates = Mio_CollectRoots( pLibGen, nVarsMax, tDelayMax, 0, &nGates, fVerbose );
190 if ( nGatesMax && nGates >= nGatesMax )
191 {
192 fprintf( stdout, "Warning! Genlib library contains more gates than can be computed.\n");
193 fprintf( stdout, "Only one-gate supergates are included in the supergate library.\n" );
194 }
195
196 // start the manager
197 pMan = Super_ManStart();
198 pMan->pName = Mio_LibraryReadName(pLibGen);
199 pMan->nGatesMax = nGatesMax;
200 pMan->fSkipInv = fSkipInv;
201 pMan->tDelayMax = tDelayMax;
202 pMan->tAreaMax = tAreaMax;
203 pMan->TimeLimit = TimeLimit; // in seconds
204 pMan->TimeStop = TimeLimit ? TimeLimit * CLOCKS_PER_SEC + Abc_Clock() : 0; // in CPU ticks
205 pMan->fVerbose = fVerbose;
206
207 if ( nGates == 0 )
208 {
209 fprintf( stderr, "Error: No genlib gates satisfy the limits criteria. Stop.\n");
210 fprintf( stderr, "Limits: max delay = %.2f, max area = %.2f, time limit = %d sec.\n",
211 pMan->tDelayMax, pMan->tAreaMax, pMan->TimeLimit );
212
213 // stop the manager
214 Super_ManStop( pMan );
215 ABC_FREE( ppGates );
216
217 return NULL;
218 }
219
220 // get the starting supergates
221 Super_First( pMan, nVarsMax );
222
223 // perform the computation of supergates
224 clockStart = Abc_Clock();
225 if ( fVerbose )
226 {
227 printf( "Computing supergates with %d inputs, %d levels, and %d max gates.\n",
228 pMan->nVarsMax, nLevels, nGatesMax );
229 printf( "Limits: max delay = %.2f, max area = %.2f, time limit = %d sec.\n",
230 pMan->tDelayMax, pMan->tAreaMax, pMan->TimeLimit );
231 }
232
233 for ( Level = 1; Level <= nLevels; Level++ )
234 {
235 if ( pMan->TimeStop && Abc_Clock() > pMan->TimeStop )
236 break;
237 clk = Abc_Clock();
238 Super_Compute( pMan, ppGates, nGates, nGatesMax, fSkipInv );
239 pMan->nLevels = Level;
240 if ( fVerbose )
241 {
242 printf( "Lev %d: Try =%12d. Add =%6d. Rem =%5d. Save =%6d. Lookups =%12d. Aliases =%12d. ",
243 Level, pMan->nTried, pMan->nAdded, pMan->nRemoved, pMan->nAdded - pMan->nRemoved, pMan->nLookups, pMan->nAliases );
244 ABC_PRT( "Time", Abc_Clock() - clk );
245 fflush( stdout );
246 }
247 }
248 pMan->Time = Abc_Clock() - clockStart;
249
250 if ( fVerbose )
251 {
252 printf( "Writing the output file...\n" );
253 fflush( stdout );
254 }
255 // write them into a file
256 vStr = Super_Write( pMan );
257
258 // stop the manager
259 Super_ManStop( pMan );
260 ABC_FREE( ppGates );
261 return vStr;
262 }
263
264
265 /**Function*************************************************************
266
267 Synopsis [Derives the starting supergates.]
268
269 Description []
270
271 SideEffects []
272
273 SeeAlso []
274
275 ***********************************************************************/
Super_First(Super_Man_t * pMan,int nVarsMax)276 void Super_First( Super_Man_t * pMan, int nVarsMax )
277 {
278 Super_Gate_t * pSuper;
279 int nMintLimit, nVarLimit;
280 int v, m;
281 // set the parameters
282 pMan->nVarsMax = nVarsMax;
283 pMan->nMints = (1 << nVarsMax);
284 pMan->nLevels = 0;
285 // allocate room for the gates
286 pMan->nGates = nVarsMax;
287 pMan->pGates = ABC_ALLOC( Super_Gate_t *, nVarsMax + 2 );
288 // create the gates corresponding to the elementary variables
289 for ( v = 0; v < nVarsMax; v++ )
290 {
291 // get a new gate
292 pSuper = (Super_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
293 memset( pSuper, 0, sizeof(Super_Gate_t) );
294 // assign the elementary variable, the truth table, and the delays
295 pSuper->fVar = 1;
296 pSuper->Number = v;
297 for ( m = 0; m < nVarsMax; m++ )
298 pSuper->ptDelays[m] = SUPER_NO_VAR;
299 pSuper->ptDelays[v] = 0.0;
300 // set the gate
301 pMan->pGates[v] = pSuper;
302 Super_AddGateToTable( pMan, pSuper );
303 pMan->pInputs[v] = pSuper;
304 }
305 // set up their truth tables
306 nVarLimit = (nVarsMax >= 5)? 5 : nVarsMax;
307 nMintLimit = (1 << nVarLimit);
308 for ( m = 0; m < nMintLimit; m++ )
309 for ( v = 0; v < nVarLimit; v++ )
310 if ( m & (1 << v) )
311 pMan->pGates[v]->uTruth[0] |= (1 << m);
312 // make adjustments for the case of 6 variables
313 if ( nVarsMax == 6 )
314 {
315 for ( v = 0; v < 5; v++ )
316 pMan->pGates[v]->uTruth[1] = pMan->pGates[v]->uTruth[0];
317 pMan->pGates[5]->uTruth[0] = 0;
318 pMan->pGates[5]->uTruth[1] = ~((unsigned)0);
319 }
320 else
321 {
322 for ( v = 0; v < nVarsMax; v++ )
323 pMan->pGates[v]->uTruth[1] = 0;
324 }
325 }
326
327 /**Function*************************************************************
328
329 Synopsis [Precomputes one level of supergates.]
330
331 Description [This procedure computes the set of supergates that can be
332 derived from the given set of root gates (from genlib library) by composing
333 the root gates with the currently available supergates. This procedure is
334 smart in the sense that it tries to avoid useless emuration by imposing
335 tight bounds by area and delay. Only the supergates and are guaranteed to
336 have smaller area and delay are enumereated. See comments below for details.]
337
338 SideEffects []
339
340 SeeAlso []
341
342 ***********************************************************************/
Super_Compute(Super_Man_t * pMan,Mio_Gate_t ** ppGates,int nGates,int nGatesMax,int fSkipInv)343 Super_Man_t * Super_Compute( Super_Man_t * pMan, Mio_Gate_t ** ppGates, int nGates, int nGatesMax, int fSkipInv )
344 {
345 Super_Gate_t * pSupers[6], * pGate0, * pGate1, * pGate2, * pGate3, * pGate4, * pGate5, * pGateNew;
346 float tPinDelaysRes[6], * ptPinDelays[6], tPinDelayMax, tDelayMio;
347 float Area = 0.0; // Suppress "might be used uninitialized"
348 float Area0, Area1, Area2, Area3, Area4, AreaMio;
349 unsigned uTruth[2], uTruths[6][2];
350 int i0, i1, i2, i3, i4, i5;
351 Super_Gate_t ** ppGatesLimit;
352 int nFanins, nGatesLimit, k, s, t;
353 ProgressBar * pProgress;
354 int fTimeOut;
355 int fPrune = 1; // Shall we prune?
356 int iPruneLimit = 3; // Each of the gates plugged into the root gate will have
357 // less than these many fanins
358 int iPruneLimitRoot = 4; // The root gate may have only less than these many fanins
359
360 // put the gates from the unique table into the array
361 // the gates from the array will be used to compose other gates
362 // the gates in tbe table are used to check uniqueness of collected gates
363 Super_TranferGatesToArray( pMan );
364
365 // sort the gates in the increasing order of maximum delay
366 if ( pMan->nGates > 10000 )
367 {
368 printf( "Sorting array of %d supergates...\r", pMan->nGates );
369 fflush( stdout );
370 }
371 qsort( (void *)pMan->pGates, (size_t)pMan->nGates, sizeof(Super_Gate_t *),
372 (int (*)(const void *, const void *)) Super_DelayCompare );
373 assert( Super_DelayCompare( pMan->pGates, pMan->pGates + pMan->nGates - 1 ) <= 0 );
374 if ( pMan->nGates > 10000 )
375 {
376 printf( " \r" );
377 }
378
379 pProgress = Extra_ProgressBarStart( stdout, pMan->TimeLimit );
380 pMan->TimePrint = Abc_Clock() + CLOCKS_PER_SEC;
381 ppGatesLimit = ABC_ALLOC( Super_Gate_t *, pMan->nGates );
382 // go through the root gates
383 // the root gates are sorted in the increasing gelay
384 fTimeOut = 0;
385 for ( k = 0; k < nGates; k++ )
386 {
387 if ( fTimeOut ) break;
388
389 if ( fPrune )
390 {
391 if ( pMan->nLevels >= 1 ) // First level gates have been computed
392 {
393 if ( Mio_GateReadPinNum(ppGates[k]) >= iPruneLimitRoot )
394 continue;
395 }
396 }
397 /*
398 if ( strcmp(Mio_GateReadName(ppGates[k]), "MUX2IX0") == 0 )
399 {
400 int s = 0;
401 }
402 */
403 // select the subset of gates to be considered with this root gate
404 // all the gates past this point will lead to delay larger than the limit
405 tDelayMio = (float)Mio_GateReadDelayMax(ppGates[k]);
406 for ( s = 0, t = 0; s < pMan->nGates; s++ )
407 {
408 if ( fPrune && ( pMan->nLevels >= 1 ) && ( ((int)pMan->pGates[s]->nFanins) >= iPruneLimit ))
409 continue;
410
411 ppGatesLimit[t] = pMan->pGates[s];
412 if ( ppGatesLimit[t++]->tDelayMax + tDelayMio > pMan->tDelayMax && pMan->tDelayMax > 0.0 )
413 break;
414 }
415 nGatesLimit = t;
416
417 if ( pMan->fVerbose )
418 {
419 printf ("Trying %d choices for %d inputs\r", t, Mio_GateReadPinNum(ppGates[k]) );
420 }
421
422 // resort part of this range by area
423 // now we can prune the search by going up in the list until we reach the limit on area
424 // all the gates beyond this point can be skipped because their area can be only larger
425 if ( nGatesLimit > 10000 )
426 printf( "Sorting array of %d supergates...\r", nGatesLimit );
427 qsort( (void *)ppGatesLimit, (size_t)nGatesLimit, sizeof(Super_Gate_t *),
428 (int (*)(const void *, const void *)) Super_AreaCompare );
429 assert( Super_AreaCompare( ppGatesLimit, ppGatesLimit + nGatesLimit - 1 ) <= 0 );
430 if ( nGatesLimit > 10000 )
431 printf( " \r" );
432
433 // consider the combinations of gates with the root gate on top
434 AreaMio = (float)Mio_GateReadArea(ppGates[k]);
435 nFanins = Mio_GateReadPinNum(ppGates[k]);
436 switch ( nFanins )
437 {
438 case 0: // should not happen
439 assert( 0 );
440 break;
441 case 1: // interter root
442 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 )
443 {
444 if ( fTimeOut ) break;
445 fTimeOut = Super_CheckTimeout( pProgress, pMan );
446 // skip the inverter as the root gate before the elementary variable
447 // as a result, the supergates will not have inverters on the input side
448 // but inverters still may occur at the output of or inside complex supergates
449 if ( fSkipInv && pGate0->tDelayMax == 0 )
450 continue;
451 // compute area
452 Area = AreaMio + pGate0->Area;
453 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
454 break;
455
456 pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays;
457 Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax );
458 Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth );
459 if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) )
460 continue;
461 // create a new gate
462 pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax );
463 Super_AddGateToTable( pMan, pGateNew );
464 if ( nGatesMax && pMan->nClasses > nGatesMax )
465 goto done;
466 }
467 break;
468 case 2: // two-input root gate
469 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 )
470 {
471 Area0 = AreaMio + pGate0->Area;
472 if ( pMan->tAreaMax > 0.0 && Area0 > pMan->tAreaMax )
473 break;
474 pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays;
475 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 )
476 if ( i1 != i0 )
477 {
478 if ( fTimeOut ) goto done;
479 fTimeOut = Super_CheckTimeout( pProgress, pMan );
480 // compute area
481 Area = Area0 + pGate1->Area;
482 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
483 break;
484
485 pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays;
486 Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax );
487 Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth );
488 if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) )
489 continue;
490 // create a new gate
491 pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax );
492 Super_AddGateToTable( pMan, pGateNew );
493 if ( nGatesMax && pMan->nClasses > nGatesMax )
494 goto done;
495 }
496 }
497 break;
498 case 3: // three-input root gate
499 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 )
500 {
501 Area0 = AreaMio + pGate0->Area;
502 if ( pMan->tAreaMax > 0.0 && Area0 > pMan->tAreaMax )
503 break;
504 pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays;
505
506 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 )
507 if ( i1 != i0 )
508 {
509 Area1 = Area0 + pGate1->Area;
510 if ( pMan->tAreaMax > 0.0 && Area1 > pMan->tAreaMax )
511 break;
512 pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays;
513
514 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 )
515 if ( i2 != i0 && i2 != i1 )
516 {
517 if ( fTimeOut ) goto done;
518 fTimeOut = Super_CheckTimeout( pProgress, pMan );
519 // compute area
520 Area = Area1 + pGate2->Area;
521 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
522 break;
523 pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays;
524
525 Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax );
526 Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth );
527 if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) )
528 continue;
529 // create a new gate
530 pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax );
531 Super_AddGateToTable( pMan, pGateNew );
532 if ( nGatesMax && pMan->nClasses > nGatesMax )
533 goto done;
534 }
535 }
536 }
537 break;
538 case 4: // four-input root gate
539 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 )
540 {
541 Area0 = AreaMio + pGate0->Area;
542 if ( pMan->tAreaMax > 0.0 && Area0 > pMan->tAreaMax )
543 break;
544 pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays;
545
546 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 )
547 if ( i1 != i0 )
548 {
549 Area1 = Area0 + pGate1->Area;
550 if ( pMan->tAreaMax > 0.0 && Area1 > pMan->tAreaMax )
551 break;
552 pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays;
553
554 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 )
555 if ( i2 != i0 && i2 != i1 )
556 {
557 Area2 = Area1 + pGate2->Area;
558 if ( pMan->tAreaMax > 0.0 && Area2 > pMan->tAreaMax )
559 break;
560 pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays;
561
562 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i3, pGate3 )
563 if ( i3 != i0 && i3 != i1 && i3 != i2 )
564 {
565 if ( fTimeOut ) goto done;
566 fTimeOut = Super_CheckTimeout( pProgress, pMan );
567 // compute area
568 Area = Area2 + pGate3->Area;
569 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
570 break;
571 pSupers[3] = pGate3; uTruths[3][0] = pGate3->uTruth[0]; uTruths[3][1] = pGate3->uTruth[1]; ptPinDelays[3] = pGate3->ptDelays;
572
573 Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax );
574 Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth );
575 if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) )
576 continue;
577 // create a new gate
578 pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax );
579 Super_AddGateToTable( pMan, pGateNew );
580 if ( nGatesMax && pMan->nClasses > nGatesMax )
581 goto done;
582 }
583 }
584 }
585 }
586 break;
587 case 5: // five-input root gate
588 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 )
589 {
590 Area0 = AreaMio + pGate0->Area;
591 if ( pMan->tAreaMax > 0.0 && Area0 > pMan->tAreaMax )
592 break;
593 pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays;
594
595 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 )
596 if ( i1 != i0 )
597 {
598 Area1 = Area0 + pGate1->Area;
599 if ( pMan->tAreaMax > 0.0 && Area1 > pMan->tAreaMax )
600 break;
601 pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays;
602
603 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 )
604 if ( i2 != i0 && i2 != i1 )
605 {
606 Area2 = Area1 + pGate2->Area;
607 if ( pMan->tAreaMax > 0.0 && Area2 > pMan->tAreaMax )
608 break;
609 pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays;
610
611 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i3, pGate3 )
612 if ( i3 != i0 && i3 != i1 && i3 != i2 )
613 {
614 Area3 = Area2 + pGate3->Area;
615 if ( pMan->tAreaMax > 0.0 && Area3 > pMan->tAreaMax )
616 break;
617 pSupers[3] = pGate3; uTruths[3][0] = pGate3->uTruth[0]; uTruths[3][1] = pGate3->uTruth[1]; ptPinDelays[3] = pGate3->ptDelays;
618
619 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i4, pGate4 )
620 if ( i4 != i0 && i4 != i1 && i4 != i2 && i4 != i3 )
621 {
622 if ( fTimeOut ) goto done;
623 fTimeOut = Super_CheckTimeout( pProgress, pMan );
624 // compute area
625 Area = Area3 + pGate4->Area;
626 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
627 break;
628 pSupers[4] = pGate4; uTruths[4][0] = pGate4->uTruth[0]; uTruths[4][1] = pGate4->uTruth[1]; ptPinDelays[4] = pGate4->ptDelays;
629
630 Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax );
631 Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth );
632 if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) )
633 continue;
634 // create a new gate
635 pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax );
636 Super_AddGateToTable( pMan, pGateNew );
637 if ( nGatesMax && pMan->nClasses > nGatesMax )
638 goto done;
639 }
640 }
641 }
642 }
643 }
644 break;
645 case 6: // six-input root gate
646 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 )
647 {
648 Area0 = AreaMio + pGate0->Area;
649 if ( pMan->tAreaMax > 0.0 && Area0 > pMan->tAreaMax )
650 break;
651 pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays;
652
653 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 )
654 if ( i1 != i0 )
655 {
656 Area1 = Area0 + pGate1->Area;
657 if ( pMan->tAreaMax > 0.0 && Area1 > pMan->tAreaMax )
658 break;
659 pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays;
660
661 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 )
662 if ( i2 != i0 && i2 != i1 )
663 {
664 Area2 = Area1 + pGate2->Area;
665 if ( pMan->tAreaMax > 0.0 && Area2 > pMan->tAreaMax )
666 break;
667 pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays;
668
669 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i3, pGate3 )
670 if ( i3 != i0 && i3 != i1 && i3 != i2 )
671 {
672 Area3 = Area2 + pGate3->Area;
673 if ( pMan->tAreaMax > 0.0 && Area3 > pMan->tAreaMax )
674 break;
675 pSupers[3] = pGate3; uTruths[3][0] = pGate3->uTruth[0]; uTruths[3][1] = pGate3->uTruth[1]; ptPinDelays[3] = pGate3->ptDelays;
676
677 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i4, pGate4 )
678 if ( i4 != i0 && i4 != i1 && i4 != i2 && i4 != i3 )
679 {
680 if ( fTimeOut ) break;
681 fTimeOut = Super_CheckTimeout( pProgress, pMan );
682 // compute area
683 Area4 = Area3 + pGate4->Area;
684 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
685 break;
686 pSupers[4] = pGate4; uTruths[4][0] = pGate4->uTruth[0]; uTruths[4][1] = pGate4->uTruth[1]; ptPinDelays[4] = pGate4->ptDelays;
687
688 Super_ManForEachGate( ppGatesLimit, nGatesLimit, i5, pGate5 )
689 if ( i5 != i0 && i5 != i1 && i5 != i2 && i5 != i3 && i5 != i4 )
690 {
691 if ( fTimeOut ) goto done;
692 fTimeOut = Super_CheckTimeout( pProgress, pMan );
693 // compute area
694 Area = Area4 + pGate5->Area;
695 if ( pMan->tAreaMax > 0.0 && Area > pMan->tAreaMax )
696 break;
697 pSupers[5] = pGate5; uTruths[5][0] = pGate5->uTruth[0]; uTruths[5][1] = pGate5->uTruth[1]; ptPinDelays[5] = pGate5->ptDelays;
698
699 Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax );
700 Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth );
701 if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) )
702 continue;
703 // create a new gate
704 pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax );
705 Super_AddGateToTable( pMan, pGateNew );
706 if ( nGatesMax && pMan->nClasses > nGatesMax )
707 goto done;
708 }
709 }
710 }
711 }
712 }
713 }
714 break;
715 default :
716 assert( 0 );
717 break;
718 }
719 }
720 done:
721 Extra_ProgressBarStop( pProgress );
722 ABC_FREE( ppGatesLimit );
723 return pMan;
724 }
725
726 /**Function*************************************************************
727
728 Synopsis [Transfers gates from table into the array.]
729
730 Description []
731
732 SideEffects []
733
734 SeeAlso []
735
736 ***********************************************************************/
Super_CheckTimeout(ProgressBar * pPro,Super_Man_t * pMan)737 int Super_CheckTimeout( ProgressBar * pPro, Super_Man_t * pMan )
738 {
739 abctime TimeNow = Abc_Clock();
740 if ( TimeNow > pMan->TimePrint )
741 {
742 Extra_ProgressBarUpdate( pPro, ++pMan->TimeSec, NULL );
743 pMan->TimePrint = Abc_Clock() + CLOCKS_PER_SEC;
744 }
745 if ( pMan->TimeStop && TimeNow > pMan->TimeStop )
746 {
747 printf ("Timeout!\n");
748 return 1;
749 }
750 pMan->nTried++;
751 return 0;
752 }
753
754
755 /**Function*************************************************************
756
757 Synopsis [Transfers gates from table into the array.]
758
759 Description []
760
761 SideEffects []
762
763 SeeAlso []
764
765 ***********************************************************************/
Super_TranferGatesToArray(Super_Man_t * pMan)766 void Super_TranferGatesToArray( Super_Man_t * pMan )
767 {
768 stmm_generator * gen;
769 Super_Gate_t * pGate, * pList;
770 ABC_PTRUINT_T Key;
771
772 // put the gates fron the table into the array
773 ABC_FREE( pMan->pGates );
774 pMan->pGates = ABC_ALLOC( Super_Gate_t *, pMan->nAdded );
775 pMan->nGates = 0;
776 stmm_foreach_item( pMan->tTable, gen, (char **)&Key, (char **)&pList )
777 {
778 for ( pGate = pList; pGate; pGate = pGate->pNext )
779 pMan->pGates[ pMan->nGates++ ] = pGate;
780 }
781 // assert( pMan->nGates == pMan->nAdded - pMan->nRemoved );
782 }
783
784 /**Function*************************************************************
785
786 Synopsis [Adds one supergate into the unique table.]
787
788 Description []
789
790 SideEffects []
791
792 SeeAlso []
793
794 ***********************************************************************/
Super_AddGateToTable(Super_Man_t * pMan,Super_Gate_t * pGate)795 void Super_AddGateToTable( Super_Man_t * pMan, Super_Gate_t * pGate )
796 {
797 Super_Gate_t ** ppList;
798 ABC_PTRUINT_T Key;
799 // Key = pGate->uTruth[0] + 2003 * pGate->uTruth[1];
800 Key = pGate->uTruth[0] ^ pGate->uTruth[1];
801 if ( !stmm_find_or_add( pMan->tTable, (char *)Key, (char ***)&ppList ) )
802 {
803 *ppList = NULL;
804 pMan->nClasses++;
805 }
806 pGate->pNext = *ppList;
807 *ppList = pGate;
808 pMan->nAdded++;
809 }
810
811 /**Function*************************************************************
812
813 Synopsis [Check the manager's unique table for comparable gates.]
814
815 Description [Returns 0 if the gate is dominated by others. Returns 1
816 if the gate is new or is better than the available ones. In this case,
817 cleans the table by removing the gates that are worse than the given one.]
818
819 SideEffects []
820
821 SeeAlso []
822
823 ***********************************************************************/
Super_CompareGates(Super_Man_t * pMan,unsigned uTruth[],float Area,float tPinDelaysRes[],int nPins)824 int Super_CompareGates( Super_Man_t * pMan, unsigned uTruth[], float Area, float tPinDelaysRes[], int nPins )
825 {
826 Super_Gate_t ** ppList, * pPrev, * pGate, * pGate2;
827 int i, fNewIsBetter, fGateIsBetter;
828 ABC_PTRUINT_T Key;
829
830 // skip constant functions
831 if ( pMan->nVarsMax < 6 )
832 {
833 if ( uTruth[0] == 0 || ~uTruth[0] == 0 )
834 return 0;
835 }
836 else
837 {
838 if ( ( uTruth[0] == 0 && uTruth[1] == 0 ) || ( ~uTruth[0] == 0 && ~uTruth[1] == 0 ) )
839 return 0;
840 }
841
842 // get hold of the place where the entry is stored
843 // Key = uTruth[0] + 2003 * uTruth[1];
844 Key = uTruth[0] ^ uTruth[1];
845 if ( !stmm_find( pMan->tTable, (char *)Key, (char ***)&ppList ) )
846 return 1;
847 // the entry with this truth table is found
848 pPrev = NULL;
849 for ( pGate = *ppList, pGate2 = pGate? pGate->pNext: NULL; pGate;
850 pGate = pGate2, pGate2 = pGate? pGate->pNext: NULL )
851 {
852 pMan->nLookups++;
853 if ( pGate->uTruth[0] != uTruth[0] || pGate->uTruth[1] != uTruth[1] )
854 {
855 pMan->nAliases++;
856 continue;
857 }
858 fGateIsBetter = 0;
859 fNewIsBetter = 0;
860 if ( pGate->Area + SUPER_EPSILON < Area )
861 fGateIsBetter = 1;
862 else if ( pGate->Area > Area + SUPER_EPSILON )
863 fNewIsBetter = 1;
864 for ( i = 0; i < nPins; i++ )
865 {
866 if ( pGate->ptDelays[i] == SUPER_NO_VAR || tPinDelaysRes[i] == SUPER_NO_VAR )
867 continue;
868 if ( pGate->ptDelays[i] + SUPER_EPSILON < tPinDelaysRes[i] )
869 fGateIsBetter = 1;
870 else if ( pGate->ptDelays[i] > tPinDelaysRes[i] + SUPER_EPSILON )
871 fNewIsBetter = 1;
872 if ( fGateIsBetter && fNewIsBetter )
873 break;
874 }
875 // consider 4 cases
876 if ( fGateIsBetter && fNewIsBetter ) // Pareto points; save both
877 pPrev = pGate;
878 else if ( fNewIsBetter ) // gate is worse; remove the gate
879 {
880 if ( pPrev == NULL )
881 *ppList = pGate->pNext;
882 else
883 pPrev->pNext = pGate->pNext;
884 Extra_MmFixedEntryRecycle( pMan->pMem, (char *)pGate );
885 pMan->nRemoved++;
886 }
887 else if ( fGateIsBetter ) // new is worse, already dominated no need to see others
888 return 0;
889 else // if ( !fGateIsBetter && !fNewIsBetter ) // they are identical, no need to see others
890 return 0;
891 }
892 return 1;
893 }
894
895
896 /**Function*************************************************************
897
898 Synopsis [Create a new supergate.]
899
900 Description []
901
902 SideEffects []
903
904 SeeAlso []
905
906 ***********************************************************************/
Super_CreateGateNew(Super_Man_t * pMan,Mio_Gate_t * pRoot,Super_Gate_t ** pSupers,int nSupers,unsigned uTruth[],float Area,float tPinDelaysRes[],float tDelayMax,int nPins)907 Super_Gate_t * Super_CreateGateNew( Super_Man_t * pMan, Mio_Gate_t * pRoot, Super_Gate_t ** pSupers, int nSupers,
908 unsigned uTruth[], float Area, float tPinDelaysRes[], float tDelayMax, int nPins )
909 {
910 Super_Gate_t * pSuper;
911 pSuper = (Super_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
912 memset( pSuper, 0, sizeof(Super_Gate_t) );
913 pSuper->pRoot = pRoot;
914 pSuper->uTruth[0] = uTruth[0];
915 pSuper->uTruth[1] = uTruth[1];
916 memcpy( pSuper->ptDelays, tPinDelaysRes, sizeof(float) * nPins );
917 pSuper->Area = Area;
918 pSuper->nFanins = nSupers;
919 memcpy( pSuper->pFanins, pSupers, sizeof(Super_Gate_t *) * nSupers );
920 pSuper->pNext = NULL;
921 pSuper->tDelayMax = tDelayMax;
922 return pSuper;
923 }
924
925 /**Function*************************************************************
926
927 Synopsis [Starts the manager.]
928
929 Description []
930
931 SideEffects []
932
933 SeeAlso []
934
935 ***********************************************************************/
Super_ManStart()936 Super_Man_t * Super_ManStart()
937 {
938 Super_Man_t * pMan;
939 pMan = ABC_CALLOC( Super_Man_t, 1 );
940 pMan->pMem = Extra_MmFixedStart( sizeof(Super_Gate_t) );
941 pMan->tTable = stmm_init_table( st__ptrcmp, st__ptrhash );
942 return pMan;
943 }
944
945 /**Function*************************************************************
946
947 Synopsis [Stops the manager.]
948
949 Description []
950
951 SideEffects []
952
953 SeeAlso []
954
955 ***********************************************************************/
Super_ManStop(Super_Man_t * pMan)956 void Super_ManStop( Super_Man_t * pMan )
957 {
958 Extra_MmFixedStop( pMan->pMem );
959 if ( pMan->tTable ) stmm_free_table( pMan->tTable );
960 ABC_FREE( pMan->pGates );
961 ABC_FREE( pMan );
962 }
963
964
965
966
967
968 /**Function*************************************************************
969
970 Synopsis [Writes the supergate library into the file.]
971
972 Description []
973
974 SideEffects []
975
976 SeeAlso []
977
978 ***********************************************************************/
Super_Write(Super_Man_t * pMan)979 Vec_Str_t * Super_Write( Super_Man_t * pMan )
980 {
981 Vec_Str_t * vStr;
982 Super_Gate_t * pGateRoot, * pGate;
983 stmm_generator * gen;
984 int fZeroFound, v;
985 abctime clk;
986 ABC_PTRUINT_T Key;
987
988 if ( pMan->nGates < 1 )
989 {
990 printf( "The generated library is empty. No output file written.\n" );
991 return NULL;
992 }
993
994 // Filters the supergates by removing those that have fewer inputs than
995 // the given limit, provided that the inputs are not consequtive.
996 // For example, NAND2(a,c) is removed, but NAND2(a,b) is left,
997 // because a and b are consequtive.
998 ABC_FREE( pMan->pGates );
999 pMan->pGates = ABC_ALLOC( Super_Gate_t *, pMan->nAdded );
1000 pMan->nGates = 0;
1001 stmm_foreach_item( pMan->tTable, gen, (char **)&Key, (char **)&pGateRoot )
1002 {
1003 for ( pGate = pGateRoot; pGate; pGate = pGate->pNext )
1004 {
1005 // skip the elementary variables
1006 if ( pGate->pRoot == NULL )
1007 continue;
1008 // skip the non-consequtive gates
1009 fZeroFound = 0;
1010 for ( v = 0; v < pMan->nVarsMax; v++ )
1011 if ( pGate->ptDelays[v] < SUPER_NO_VAR + SUPER_EPSILON )
1012 fZeroFound = 1;
1013 else if ( fZeroFound )
1014 break;
1015 if ( v < pMan->nVarsMax )
1016 continue;
1017 // save the unique gate
1018 pMan->pGates[ pMan->nGates++ ] = pGate;
1019 }
1020 }
1021
1022 clk = Abc_Clock();
1023 // sort the supergates by truth table
1024 qsort( (void *)pMan->pGates, (size_t)pMan->nGates, sizeof(Super_Gate_t *),
1025 (int (*)(const void *, const void *)) Super_WriteCompare );
1026 assert( Super_WriteCompare( pMan->pGates, pMan->pGates + pMan->nGates - 1 ) <= 0 );
1027 if ( pMan->fVerbose )
1028 {
1029 ABC_PRT( "Sorting", Abc_Clock() - clk );
1030 }
1031
1032
1033 // write library in the old format
1034 clk = Abc_Clock();
1035 if ( pMan->fWriteOldFormat )
1036 Super_WriteLibrary( pMan );
1037 if ( pMan->fVerbose )
1038 {
1039 ABC_PRT( "Writing old format", Abc_Clock() - clk );
1040 }
1041
1042 // write the tree-like structure of supergates
1043 clk = Abc_Clock();
1044 vStr = Super_WriteLibraryTreeStr( pMan );
1045 if ( pMan->fVerbose )
1046 {
1047 ABC_PRT( "Writing new format", Abc_Clock() - clk );
1048 }
1049 return vStr;
1050 }
1051
1052
1053 /**Function*************************************************************
1054
1055 Synopsis [Writes the file header.]
1056
1057 Description []
1058
1059 SideEffects []
1060
1061 SeeAlso []
1062
1063 ***********************************************************************/
Super_WriteFileHeader(Super_Man_t * pMan,FILE * pFile)1064 void Super_WriteFileHeader( Super_Man_t * pMan, FILE * pFile )
1065 {
1066 fprintf( pFile, "#\n" );
1067 fprintf( pFile, "# Supergate library derived for \"%s\" on %s.\n", pMan->pName, Extra_TimeStamp() );
1068 fprintf( pFile, "#\n" );
1069 fprintf( pFile, "# Command line: \"super -I %d -L %d -N %d -T %d -D %.2f -A %.2f %s %s\".\n",
1070 pMan->nVarsMax, pMan->nLevels, pMan->nGatesMax, pMan->TimeLimit, pMan->tDelayMax, pMan->tAreaMax, (pMan->fSkipInv? "" : "-s"), pMan->pName );
1071 fprintf( pFile, "#\n" );
1072 fprintf( pFile, "# The number of inputs = %10d.\n", pMan->nVarsMax );
1073 fprintf( pFile, "# The number of levels = %10d.\n", pMan->nLevels );
1074 fprintf( pFile, "# The maximum delay = %10.2f.\n", pMan->tDelayMax );
1075 fprintf( pFile, "# The maximum area = %10.2f.\n", pMan->tAreaMax );
1076 fprintf( pFile, "# The maximum runtime (sec) = %10d.\n", pMan->TimeLimit );
1077 fprintf( pFile, "#\n" );
1078 fprintf( pFile, "# The number of attempts = %10d.\n", pMan->nTried );
1079 fprintf( pFile, "# The number of supergates = %10d.\n", pMan->nGates );
1080 fprintf( pFile, "# The number of functions = %10d.\n", pMan->nUnique );
1081 fprintf( pFile, "# The total functions = %.0f (2^%d).\n", pow((double)2,pMan->nMints), pMan->nMints );
1082 fprintf( pFile, "#\n" );
1083 fprintf( pFile, "# Generation time = %10.2f sec.\n", (float)(pMan->Time)/(float)(CLOCKS_PER_SEC) );
1084 fprintf( pFile, "#\n" );
1085 fprintf( pFile, "%s\n", pMan->pName );
1086 fprintf( pFile, "%d\n", pMan->nVarsMax );
1087 fprintf( pFile, "%d\n", pMan->nGates );
1088 }
Super_WriteFileHeaderStr(Super_Man_t * pMan,Vec_Str_t * vStr)1089 void Super_WriteFileHeaderStr( Super_Man_t * pMan, Vec_Str_t * vStr )
1090 {
1091 char pBuffer[1000];
1092 sprintf( pBuffer, "#\n" );
1093 Vec_StrPrintStr( vStr, pBuffer );
1094 sprintf( pBuffer, "# Supergate library derived for \"%s\" on %s.\n", pMan->pName, Extra_TimeStamp() );
1095 Vec_StrPrintStr( vStr, pBuffer );
1096 sprintf( pBuffer, "#\n" );
1097 Vec_StrPrintStr( vStr, pBuffer );
1098 sprintf( pBuffer, "# Command line: \"super -I %d -L %d -N %d -T %d -D %.2f -A %.2f %s %s\".\n",
1099 pMan->nVarsMax, pMan->nLevels, pMan->nGatesMax, pMan->TimeLimit, pMan->tDelayMax, pMan->tAreaMax, (pMan->fSkipInv? "" : "-s"), pMan->pName );
1100 Vec_StrPrintStr( vStr, pBuffer );
1101 sprintf( pBuffer, "#\n" );
1102 Vec_StrPrintStr( vStr, pBuffer );
1103 sprintf( pBuffer, "# The number of inputs = %10d.\n", pMan->nVarsMax );
1104 Vec_StrPrintStr( vStr, pBuffer );
1105 sprintf( pBuffer, "# The number of levels = %10d.\n", pMan->nLevels );
1106 Vec_StrPrintStr( vStr, pBuffer );
1107 sprintf( pBuffer, "# The maximum delay = %10.2f.\n", pMan->tDelayMax );
1108 Vec_StrPrintStr( vStr, pBuffer );
1109 sprintf( pBuffer, "# The maximum area = %10.2f.\n", pMan->tAreaMax );
1110 Vec_StrPrintStr( vStr, pBuffer );
1111 sprintf( pBuffer, "# The maximum runtime (sec) = %10d.\n", pMan->TimeLimit );
1112 Vec_StrPrintStr( vStr, pBuffer );
1113 sprintf( pBuffer, "#\n" );
1114 Vec_StrPrintStr( vStr, pBuffer );
1115 sprintf( pBuffer, "# The number of attempts = %10d.\n", pMan->nTried );
1116 Vec_StrPrintStr( vStr, pBuffer );
1117 sprintf( pBuffer, "# The number of supergates = %10d.\n", pMan->nGates );
1118 Vec_StrPrintStr( vStr, pBuffer );
1119 sprintf( pBuffer, "# The number of functions = %10d.\n", pMan->nUnique );
1120 Vec_StrPrintStr( vStr, pBuffer );
1121 sprintf( pBuffer, "# The total functions = %.0f (2^%d).\n", pow((double)2,pMan->nMints), pMan->nMints );
1122 Vec_StrPrintStr( vStr, pBuffer );
1123 sprintf( pBuffer, "#\n" );
1124 Vec_StrPrintStr( vStr, pBuffer );
1125 sprintf( pBuffer, "# Generation time = %10.2f sec.\n", (float)(pMan->Time)/(float)(CLOCKS_PER_SEC) );
1126 Vec_StrPrintStr( vStr, pBuffer );
1127 sprintf( pBuffer, "#\n" );
1128 Vec_StrPrintStr( vStr, pBuffer );
1129 sprintf( pBuffer, "%s\n", pMan->pName );
1130 Vec_StrPrintStr( vStr, pBuffer );
1131 sprintf( pBuffer, "%d\n", pMan->nVarsMax );
1132 Vec_StrPrintStr( vStr, pBuffer );
1133 sprintf( pBuffer, "%d\n", pMan->nGates );
1134 Vec_StrPrintStr( vStr, pBuffer );
1135 }
1136
1137 /**Function*************************************************************
1138
1139 Synopsis [Compares two gates.]
1140
1141 Description []
1142
1143 SideEffects []
1144
1145 SeeAlso []
1146
1147 ***********************************************************************/
Super_WriteCompare(Super_Gate_t ** ppG1,Super_Gate_t ** ppG2)1148 int Super_WriteCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 )
1149 {
1150 unsigned * pTruth1 = (*ppG1)->uTruth;
1151 unsigned * pTruth2 = (*ppG2)->uTruth;
1152 if ( pTruth1[1] < pTruth2[1] )
1153 return -1;
1154 if ( pTruth1[1] > pTruth2[1] )
1155 return 1;
1156 if ( pTruth1[0] < pTruth2[0] )
1157 return -1;
1158 if ( pTruth1[0] > pTruth2[0] )
1159 return 1;
1160 return 0;
1161 }
Super_DelayCompare(Super_Gate_t ** ppG1,Super_Gate_t ** ppG2)1162 int Super_DelayCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 )
1163 {
1164 if ( (*ppG1)->tDelayMax < (*ppG2)->tDelayMax )
1165 return -1;
1166 if ( (*ppG1)->tDelayMax > (*ppG2)->tDelayMax )
1167 return 1;
1168 return 0;
1169 }
Super_AreaCompare(Super_Gate_t ** ppG1,Super_Gate_t ** ppG2)1170 int Super_AreaCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 )
1171 {
1172 if ( (*ppG1)->Area < (*ppG2)->Area )
1173 return -1;
1174 if ( (*ppG1)->Area > (*ppG2)->Area )
1175 return 1;
1176 return 0;
1177 }
1178
1179
1180
1181
1182
1183
1184 /**Function*************************************************************
1185
1186 Synopsis [Writes the gates into the file.]
1187
1188 Description []
1189
1190 SideEffects []
1191
1192 SeeAlso []
1193
1194 ***********************************************************************/
Super_WriteLibraryGateName_rec(Super_Gate_t * pGate,char * pBuffer)1195 void Super_WriteLibraryGateName_rec( Super_Gate_t * pGate, char * pBuffer )
1196 {
1197 char Buffer[10];
1198 int i;
1199
1200 if ( pGate->pRoot == NULL )
1201 {
1202 sprintf( Buffer, "%c", 'a' + pGate->Number );
1203 strcat( pBuffer, Buffer );
1204 return;
1205 }
1206 strcat( pBuffer, Mio_GateReadName(pGate->pRoot) );
1207 strcat( pBuffer, "(" );
1208 for ( i = 0; i < (int)pGate->nFanins; i++ )
1209 {
1210 if ( i )
1211 strcat( pBuffer, "," );
1212 Super_WriteLibraryGateName_rec( pGate->pFanins[i], pBuffer );
1213 }
1214 strcat( pBuffer, ")" );
1215 }
Super_WriteLibraryGateName(Super_Gate_t * pGate)1216 char * Super_WriteLibraryGateName( Super_Gate_t * pGate )
1217 {
1218 static char Buffer[2000];
1219 Buffer[0] = 0;
1220 Super_WriteLibraryGateName_rec( pGate, Buffer );
1221 return Buffer;
1222 }
Super_WriteLibraryGate(FILE * pFile,Super_Man_t * pMan,Super_Gate_t * pGate,int Num)1223 void Super_WriteLibraryGate( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pGate, int Num )
1224 {
1225 int i;
1226 fprintf( pFile, "%04d ", Num ); // the number
1227 Extra_PrintBinary( pFile, pGate->uTruth, pMan->nMints ); // the truth table
1228 fprintf( pFile, " %5.2f", pGate->tDelayMax ); // the max delay
1229 fprintf( pFile, " " );
1230 for ( i = 0; i < pMan->nVarsMax; i++ ) // the pin-to-pin delays
1231 fprintf( pFile, " %5.2f", pGate->ptDelays[i]==SUPER_NO_VAR? 0.0 : pGate->ptDelays[i] );
1232 fprintf( pFile, " %5.2f", pGate->Area ); // the area
1233 fprintf( pFile, " " );
1234 fprintf( pFile, "%s", Super_WriteLibraryGateName(pGate) ); // the symbolic expression
1235 fprintf( pFile, "\n" );
1236 }
Super_WriteLibrary(Super_Man_t * pMan)1237 void Super_WriteLibrary( Super_Man_t * pMan )
1238 {
1239 Super_Gate_t * pGate, * pGateNext;
1240 FILE * pFile;
1241 char * FileName;
1242 char * pNameGeneric;
1243 int i, Counter;
1244
1245 FileName = ABC_ALLOC( char, 10000 );
1246
1247 // get the file name
1248 pNameGeneric = Extra_FileNameGeneric( pMan->pName );
1249 sprintf( FileName, "%s.super_old", pNameGeneric );
1250 ABC_FREE( pNameGeneric );
1251
1252 // count the number of unique functions
1253 pMan->nUnique = 1;
1254 Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pGate )
1255 {
1256 if ( i == pMan->nGates - 1 )
1257 break;
1258 // print the newline if this gate is different from the following one
1259 pGateNext = pMan->pGates[i+1];
1260 if ( pGateNext->uTruth[0] != pGate->uTruth[0] || pGateNext->uTruth[1] != pGate->uTruth[1] )
1261 pMan->nUnique++;
1262 }
1263
1264 // start the file
1265 pFile = fopen( FileName, "w" );
1266 Super_WriteFileHeader( pMan, pFile );
1267
1268 // print the gates
1269 Counter = 0;
1270 Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pGate )
1271 {
1272 Super_WriteLibraryGate( pFile, pMan, pGate, ++Counter );
1273 if ( i == pMan->nGates - 1 )
1274 break;
1275 // print the newline if this gate is different from the following one
1276 pGateNext = pMan->pGates[i+1];
1277 if ( pGateNext->uTruth[0] != pGate->uTruth[0] || pGateNext->uTruth[1] != pGate->uTruth[1] )
1278 fprintf( pFile, "\n" );
1279 }
1280 assert( Counter == pMan->nGates );
1281 fclose( pFile );
1282
1283 if ( pMan->fVerbose )
1284 {
1285 printf( "The supergates are written using old format \"%s\" ", FileName );
1286 printf( "(%0.3f MB).\n", ((double)Extra_FileSize(FileName))/(1<<20) );
1287 }
1288
1289 ABC_FREE( FileName );
1290 }
1291
1292
1293
1294
1295 /**Function*************************************************************
1296
1297 Synopsis [Recursively writes the gates.]
1298
1299 Description []
1300
1301 SideEffects []
1302
1303 SeeAlso []
1304
1305 ***********************************************************************/
Super_WriteLibraryTreeFile_rec(FILE * pFile,Super_Man_t * pMan,Super_Gate_t * pSuper,int * pCounter)1306 void Super_WriteLibraryTreeFile_rec( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pSuper, int * pCounter )
1307 {
1308 int nFanins, i;
1309 // skip an elementary variable and a gate that was already written
1310 if ( pSuper->fVar || pSuper->Number > 0 )
1311 return;
1312 // write the fanins
1313 nFanins = Mio_GateReadPinNum(pSuper->pRoot);
1314 for ( i = 0; i < nFanins; i++ )
1315 Super_WriteLibraryTreeFile_rec( pFile, pMan, pSuper->pFanins[i], pCounter );
1316 // finally write the gate
1317 pSuper->Number = (*pCounter)++;
1318 fprintf( pFile, "%s", pSuper->fSuper? "* " : "" );
1319 fprintf( pFile, "%s", Mio_GateReadName(pSuper->pRoot) );
1320 for ( i = 0; i < nFanins; i++ )
1321 fprintf( pFile, " %d", pSuper->pFanins[i]->Number );
1322 // write the formula
1323 // this step is optional, the resulting library will work in any case
1324 // however, it may be helpful to for debugging to compare the same library
1325 // written in the old format and written in the new format with formulas
1326 // fprintf( pFile, " # %s", Super_WriteLibraryGateName( pSuper ) );
1327 fprintf( pFile, "\n" );
1328 }
Super_WriteLibraryTreeFile(Super_Man_t * pMan)1329 void Super_WriteLibraryTreeFile( Super_Man_t * pMan )
1330 {
1331 Super_Gate_t * pSuper;
1332 FILE * pFile;
1333 char * FileName;
1334 char * pNameGeneric;
1335 int i, Counter;
1336 int posStart;
1337
1338 FileName = ABC_ALLOC( char, 10000 );
1339
1340 // get the file name
1341 pNameGeneric = Extra_FileNameGeneric( pMan->pName );
1342 sprintf( FileName, "%s.super", pNameGeneric );
1343 ABC_FREE( pNameGeneric );
1344
1345 // write the elementary variables
1346 pFile = fopen( FileName, "wb" );
1347 Super_WriteFileHeader( pMan, pFile );
1348 // write the place holder for the number of lines
1349 posStart = ftell( pFile );
1350 fprintf( pFile, " \n" );
1351 // mark the real supergates
1352 Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pSuper )
1353 pSuper->fSuper = 1;
1354 // write the supergates
1355 Counter = pMan->nVarsMax;
1356 Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pSuper )
1357 Super_WriteLibraryTreeFile_rec( pFile, pMan, pSuper, &Counter );
1358 fclose( pFile );
1359 // write the number of lines
1360 pFile = fopen( FileName, "rb+" );
1361 fseek( pFile, posStart, SEEK_SET );
1362 fprintf( pFile, "%d", Counter );
1363 fclose( pFile );
1364
1365 if ( pMan->fVerbose )
1366 {
1367 printf( "The supergates are written using new format \"%s\" ", FileName );
1368 printf( "(%0.3f MB).\n", ((double)Extra_FileSize(FileName))/(1<<20) );
1369 }
1370
1371 ABC_FREE( FileName );
1372 }
1373
1374
1375 /**Function*************************************************************
1376
1377 Synopsis [Recursively writes the gates.]
1378
1379 Description []
1380
1381 SideEffects []
1382
1383 SeeAlso []
1384
1385 ***********************************************************************/
Super_WriteLibraryTreeStr_rec(Vec_Str_t * vStr,Super_Man_t * pMan,Super_Gate_t * pSuper,int * pCounter)1386 void Super_WriteLibraryTreeStr_rec( Vec_Str_t * vStr, Super_Man_t * pMan, Super_Gate_t * pSuper, int * pCounter )
1387 {
1388 int nFanins, i;
1389 // skip an elementary variable and a gate that was already written
1390 if ( pSuper->fVar || pSuper->Number > 0 )
1391 return;
1392 // write the fanins
1393 nFanins = Mio_GateReadPinNum(pSuper->pRoot);
1394 for ( i = 0; i < nFanins; i++ )
1395 Super_WriteLibraryTreeStr_rec( vStr, pMan, pSuper->pFanins[i], pCounter );
1396 // finally write the gate
1397 pSuper->Number = (*pCounter)++;
1398 // fprintf( pFile, "%s", pSuper->fSuper? "* " : "" );
1399 // fprintf( pFile, "%s", Mio_GateReadName(pSuper->pRoot) );
1400 // for ( i = 0; i < nFanins; i++ )
1401 // fprintf( pFile, " %d", pSuper->pFanins[i]->Number );
1402 Vec_StrPrintStr( vStr, pSuper->fSuper? "* " : "" );
1403 Vec_StrPrintStr( vStr, Mio_GateReadName(pSuper->pRoot) );
1404 for ( i = 0; i < nFanins; i++ )
1405 {
1406 Vec_StrPrintStr( vStr, " " );
1407 Vec_StrPrintNum( vStr, pSuper->pFanins[i]->Number );
1408 }
1409 // write the formula
1410 // this step is optional, the resulting library will work in any case
1411 // however, it may be helpful to for debugging to compare the same library
1412 // written in the old format and written in the new format with formulas
1413 // fprintf( pFile, " # %s", Super_WriteLibraryGateName( pSuper ) );
1414 // fprintf( pFile, "\n" );
1415 Vec_StrPrintStr( vStr, "\n" );
1416 }
Super_WriteLibraryTreeStr(Super_Man_t * pMan)1417 Vec_Str_t * Super_WriteLibraryTreeStr( Super_Man_t * pMan )
1418 {
1419 char pInsert[16];
1420 Vec_Str_t * vStr;
1421 Super_Gate_t * pSuper;
1422 int i, Counter;
1423 int posStart;
1424 // write the elementary variables
1425 vStr = Vec_StrAlloc( 1000 );
1426 Super_WriteFileHeaderStr( pMan, vStr );
1427 // write the place holder for the number of lines
1428 posStart = Vec_StrSize( vStr );
1429 for ( i = 0; i < 9; i++ )
1430 Vec_StrPush( vStr, ' ' );
1431 Vec_StrPush( vStr, '\n' );
1432 // mark the real supergates
1433 Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pSuper )
1434 pSuper->fSuper = 1;
1435 // write the supergates
1436 Counter = pMan->nVarsMax;
1437 Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pSuper )
1438 Super_WriteLibraryTreeStr_rec( vStr, pMan, pSuper, &Counter );
1439 Vec_StrPush( vStr, 0 );
1440 // write the number of lines
1441 sprintf( pInsert, "%d", Counter );
1442 for ( i = 0; i < (int)strlen(pInsert); i++ )
1443 Vec_StrWriteEntry( vStr, posStart + i, pInsert[i] );
1444 return vStr;
1445 }
Super_WriteLibraryTree(Super_Man_t * pMan)1446 void Super_WriteLibraryTree( Super_Man_t * pMan )
1447 {
1448 Vec_Str_t * vStr;
1449 char * pFileName = Extra_FileNameGenericAppend( pMan->pName, ".super" );
1450 FILE * pFile = fopen( pFileName, "wb" );
1451 if ( pFile == NULL )
1452 {
1453 printf( "Cannot open output file \"%s\".\n", pFileName );
1454 return;
1455 }
1456 vStr = Super_WriteLibraryTreeStr( pMan );
1457 fwrite( Vec_StrArray(vStr), 1, Vec_StrSize(vStr), pFile );
1458 fclose( pFile );
1459 Vec_StrFree( vStr );
1460 // report the result of writing
1461 if ( pMan->fVerbose )
1462 {
1463 printf( "The supergates are written using new format \"%s\" ", pFileName );
1464 printf( "(%0.3f MB).\n", ((double)Extra_FileSize(pFileName))/(1<<20) );
1465 }
1466 }
1467
1468 ////////////////////////////////////////////////////////////////////////
1469 /// END OF FILE ///
1470 ////////////////////////////////////////////////////////////////////////
1471
1472 ABC_NAMESPACE_IMPL_END
1473
1474