1 /**CFile****************************************************************
2
3 FileName [mapperTree.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: mapperTree.c,v 1.9 2005/01/23 06:59:45 alanmi Exp $]
16
17 ***********************************************************************/
18
19 #ifdef __linux__
20 #include <libgen.h>
21 #endif
22
23 #include "mapperInt.h"
24
25 ABC_NAMESPACE_IMPL_START
26
27
28 ////////////////////////////////////////////////////////////////////////
29 /// DECLARATIONS ///
30 ////////////////////////////////////////////////////////////////////////
31
32 static void Map_LibraryAddFaninDelays( Map_SuperLib_t * pLib, Map_Super_t * pGate, Map_Super_t * pFanin, Mio_Pin_t * pPin );
33 static int Map_LibraryGetMaxSuperPi_rec( Map_Super_t * pGate );
34 static unsigned Map_LibraryGetGateSupp_rec( Map_Super_t * pGate );
35
36 // fanout limits
37 static const int s_MapFanoutLimits[10] = { 1/*0*/, 10/*1*/, 5/*2*/, 2/*3*/, 1/*4*/, 1/*5*/, 1/*6*/ };
38
39 ////////////////////////////////////////////////////////////////////////
40 /// FUNCTION DEFINITIONS ///
41 ////////////////////////////////////////////////////////////////////////
42
43 /**Function*************************************************************
44
45 Synopsis [Reads one gate.]
46
47 Description []
48
49 SideEffects []
50
51 SeeAlso []
52
53 ***********************************************************************/
Map_LibraryReadGateTree(Map_SuperLib_t * pLib,char * pBuffer,int Number,int nVarsMax)54 Map_Super_t * Map_LibraryReadGateTree( Map_SuperLib_t * pLib, char * pBuffer, int Number, int nVarsMax )
55 {
56 Map_Super_t * pGate;
57 char * pTemp;
58 int i, Num;
59
60 // start and clean the gate
61 pGate = (Map_Super_t *)Extra_MmFixedEntryFetch( pLib->mmSupers );
62 memset( pGate, 0, sizeof(Map_Super_t) );
63
64 // set the gate number
65 pGate->Num = Number;
66
67 // read the mark
68 pTemp = strtok( pBuffer, " " );
69 if ( pTemp[0] == '*' )
70 {
71 pGate->fSuper = 1;
72 pTemp = strtok( NULL, " " );
73 }
74
75 // read the root gate
76 pGate->pRoot = Mio_LibraryReadGateByName( pLib->pGenlib, pTemp, NULL );
77 if ( pGate->pRoot == NULL )
78 {
79 printf( "Cannot read the root gate names %s.\n", pTemp );
80 return NULL;
81 }
82 // set the max number of fanouts
83 pGate->nFanLimit = s_MapFanoutLimits[ Mio_GateReadPinNum(pGate->pRoot) ];
84
85 // read the pin-to-pin delay
86 for ( i = 0; ( pTemp = strtok( NULL, " \n\0" ) ); i++ )
87 {
88 if ( pTemp[0] == '#' )
89 break;
90 if ( i == nVarsMax )
91 {
92 printf( "There are too many entries on the line.\n" );
93 return NULL;
94 }
95 Num = atoi(pTemp);
96 if ( Num < 0 )
97 {
98 printf( "The number of a child supergate is negative.\n" );
99 return NULL;
100 }
101 if ( Num > pLib->nLines )
102 {
103 printf( "The number of a child supergate (%d) exceeded the number of lines (%d).\n",
104 Num, pLib->nLines );
105 return NULL;
106 }
107 pGate->pFanins[i] = pLib->ppSupers[Num];
108 }
109 pGate->nFanins = i;
110 if ( pGate->nFanins != (unsigned)Mio_GateReadPinNum(pGate->pRoot) )
111 {
112 printf( "The number of fanins of a root gate is wrong.\n" );
113 return NULL;
114 }
115
116 // save the gate name, just in case
117 if ( pTemp && pTemp[0] == '#' )
118 {
119 if ( pTemp[1] == 0 )
120 pTemp = strtok( NULL, " \n\0" );
121 else // skip spaces
122 for ( pTemp++; *pTemp == ' '; pTemp++ );
123 // save the formula
124 pGate->pFormula = Extra_MmFlexEntryFetch( pLib->mmForms, strlen(pTemp)+1 );
125 strcpy( pGate->pFormula, pTemp );
126 }
127 // check the rest of the string
128 pTemp = strtok( NULL, " \n\0" );
129 if ( pTemp != NULL )
130 printf( "The following trailing symbols found \"%s\".\n", pTemp );
131 return pGate;
132 }
133
134 /**Function*************************************************************
135
136 Synopsis [Reads the supergate library from file.]
137
138 Description []
139
140 SideEffects []
141
142 SeeAlso []
143
144 ***********************************************************************/
145 /*
146 int Map_LibraryReadFileTree( Map_SuperLib_t * pLib, FILE * pFile, char *pFileName )
147 {
148 ProgressBar * pProgress;
149 char pBuffer[5000];
150 Map_Super_t * pGate;
151 char * pTemp = 0, * pLibName;
152 int nCounter, k, i;
153 int RetValue;
154
155 // skip empty and comment lines
156 while ( fgets( pBuffer, 5000, pFile ) != NULL )
157 {
158 // skip leading spaces
159 for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ );
160 // skip comment lines and empty lines
161 if ( *pTemp != 0 && *pTemp != '#' )
162 break;
163 }
164
165 pLibName = strtok( pTemp, " \t\r\n" );
166 pLib->pGenlib = (Mio_Library_t *)Abc_FrameReadLibGen();
167 if ( pLib->pGenlib == NULL || strcmp( Mio_LibraryReadName(pLib->pGenlib), pLibName ) )
168 {
169 printf( "Supergate library \"%s\" requires the use of genlib library \"%s\".\n", pFileName, pLibName );
170 return 0;
171 }
172
173 // read the number of variables
174 RetValue = fscanf( pFile, "%d\n", &pLib->nVarsMax );
175 if ( pLib->nVarsMax < 2 || pLib->nVarsMax > 10 )
176 {
177 printf( "Suspicious number of variables (%d).\n", pLib->nVarsMax );
178 return 0;
179 }
180
181 // read the number of gates
182 RetValue = fscanf( pFile, "%d\n", &pLib->nSupersReal );
183 if ( pLib->nSupersReal < 1 || pLib->nSupersReal > 10000000 )
184 {
185 printf( "Suspicious number of gates (%d).\n", pLib->nSupersReal );
186 return 0;
187 }
188
189 // read the number of lines
190 RetValue = fscanf( pFile, "%d\n", &pLib->nLines );
191 if ( pLib->nLines < 1 || pLib->nLines > 10000000 )
192 {
193 printf( "Suspicious number of lines (%d).\n", pLib->nLines );
194 return 0;
195 }
196
197 // allocate room for supergate pointers
198 pLib->ppSupers = ABC_ALLOC( Map_Super_t *, pLib->nLines + 10000 );
199
200 // create the elementary supergates
201 for ( i = 0; i < pLib->nVarsMax; i++ )
202 {
203 // get a new gate
204 pGate = (Map_Super_t *)Extra_MmFixedEntryFetch( pLib->mmSupers );
205 memset( pGate, 0, sizeof(Map_Super_t) );
206 // assign the elementary variable, the truth table, and the delays
207 pGate->Num = i;
208 // set the truth table
209 pGate->uTruth[0] = pLib->uTruths[i][0];
210 pGate->uTruth[1] = pLib->uTruths[i][1];
211 // set the arrival times of all input to non-existent delay
212 for ( k = 0; k < pLib->nVarsMax; k++ )
213 {
214 pGate->tDelaysR[k].Rise = pGate->tDelaysR[k].Fall = MAP_NO_VAR;
215 pGate->tDelaysF[k].Rise = pGate->tDelaysF[k].Fall = MAP_NO_VAR;
216 }
217 // set an existent arrival time for rise and fall
218 pGate->tDelaysR[i].Rise = 0.0;
219 pGate->tDelaysF[i].Fall = 0.0;
220 // set the gate
221 pLib->ppSupers[i] = pGate;
222 }
223
224 // read the lines
225 nCounter = pLib->nVarsMax;
226 pProgress = Extra_ProgressBarStart( stdout, pLib->nLines );
227 while ( fgets( pBuffer, 5000, pFile ) != NULL )
228 {
229 for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ );
230 if ( pTemp[0] == '\0' )
231 continue;
232 // if ( pTemp[0] == 'a' || pTemp[2] == 'a' )
233 // {
234 // pLib->nLines--;
235 // continue;
236 // }
237
238 // get the gate
239 pGate = Map_LibraryReadGateTree( pLib, pTemp, nCounter, pLib->nVarsMax );
240 if ( pGate == NULL )
241 {
242 Extra_ProgressBarStop( pProgress );
243 return 0;
244 }
245 pLib->ppSupers[nCounter++] = pGate;
246 // later we will derive: truth table, delays, area, number of component gates, etc
247
248 // update the progress bar
249 Extra_ProgressBarUpdate( pProgress, nCounter, NULL );
250 }
251 Extra_ProgressBarStop( pProgress );
252 if ( nCounter != pLib->nLines )
253 printf( "The number of lines read (%d) is different what the file says (%d).\n", nCounter, pLib->nLines );
254 pLib->nSupersAll = nCounter;
255 // count the number of real supergates
256 nCounter = 0;
257 for ( k = 0; k < pLib->nLines; k++ )
258 nCounter += pLib->ppSupers[k]->fSuper;
259 if ( nCounter != pLib->nSupersReal )
260 printf( "The number of gates read (%d) is different what the file says (%d).\n", nCounter, pLib->nSupersReal );
261 pLib->nSupersReal = nCounter;
262 return 1;
263 }
264 int Map_LibraryReadTree2( Map_SuperLib_t * pLib, char * pFileName, char * pExcludeFile )
265 {
266 FILE * pFile;
267 int Status, num;
268 Abc_Frame_t * pAbc;
269 st__table * tExcludeGate = 0;
270
271 // read the beginning of the file
272 assert( pLib->pGenlib == NULL );
273 pFile = Io_FileOpen( pFileName, "open_path", "r", 1 );
274 // pFile = fopen( pFileName, "r" );
275 if ( pFile == NULL )
276 {
277 printf( "Cannot open input file \"%s\".\n", pFileName );
278 return 0;
279 }
280
281 if ( pExcludeFile )
282 {
283 pAbc = Abc_FrameGetGlobalFrame();
284
285 tExcludeGate = st__init_table(strcmp, st__strhash);
286 if ( (num = Mio_LibraryReadExclude( pExcludeFile, tExcludeGate )) == -1 )
287 {
288 st__free_table( tExcludeGate );
289 tExcludeGate = 0;
290 return 0;
291 }
292
293 fprintf ( Abc_FrameReadOut( pAbc ), "Read %d gates from exclude file\n", num );
294 }
295
296 Status = Map_LibraryReadFileTree( pLib, pFile, pFileName );
297 fclose( pFile );
298 if ( Status == 0 )
299 return 0;
300 // prepare the info about the library
301 return Map_LibraryDeriveGateInfo( pLib, tExcludeGate );
302 }
303 */
304
305 /**Function*************************************************************
306
307 Synopsis [Similar to fgets.]
308
309 Description []
310
311 SideEffects []
312
313 SeeAlso []
314
315 ***********************************************************************/
Vec_StrGets(char * pBuffer,int nBufferSize,Vec_Str_t * vStr,int * pPos)316 int Vec_StrGets( char * pBuffer, int nBufferSize, Vec_Str_t * vStr, int * pPos )
317 {
318 char * pCur;
319 char * pBeg = Vec_StrArray(vStr) + *pPos;
320 char * pEnd = Vec_StrArray(vStr) + Vec_StrSize(vStr);
321 assert( nBufferSize > 1 );
322 if ( pBeg == pEnd )
323 {
324 *pBuffer = 0;
325 return 0;
326 }
327 assert( pBeg < pEnd );
328 for ( pCur = pBeg; pCur < pEnd; pCur++ )
329 {
330 *pBuffer++ = *pCur;
331 if ( *pCur == 0 )
332 {
333 *pPos += pCur - pBeg;
334 return 0;
335 }
336 if ( *pCur == '\n' )
337 {
338 *pPos += pCur - pBeg + 1;
339 *pBuffer = 0;
340 return 1;
341 }
342 if ( pCur - pBeg == nBufferSize-1 )
343 {
344 *pPos += pCur - pBeg + 1;
345 *pBuffer = 0;
346 return 1;
347 }
348 }
349 return 0;
350 }
351
352 /**Function*************************************************************
353
354 Synopsis []
355
356 Description []
357
358 SideEffects []
359
360 SeeAlso []
361
362 ***********************************************************************/
Map_LibraryCompareLibNames(char * pName1,char * pName2)363 int Map_LibraryCompareLibNames( char * pName1, char * pName2 )
364 {
365 char * p1 = Abc_UtilStrsav( pName1 );
366 char * p2 = Abc_UtilStrsav( pName2 );
367 int i, RetValue;
368 for ( i = 0; p1[i]; i++ )
369 if ( p1[i] == '>' || p1[i] == '\\' || p1[i] == '/' )
370 p1[i] = '/';
371 for ( i = 0; p2[i]; i++ )
372 if ( p2[i] == '>' || p2[i] == '\\' || p2[i] == '/' )
373 p2[i] = '/';
374 RetValue = strcmp( p1, p2 );
375 ABC_FREE( p1 );
376 ABC_FREE( p2 );
377 return RetValue;
378 }
379
380 /**Function*************************************************************
381
382 Synopsis [Reads the supergate library from file.]
383
384 Description []
385
386 SideEffects []
387
388 SeeAlso []
389
390 ***********************************************************************/
Map_LibraryReadFileTreeStr(Map_SuperLib_t * pLib,Mio_Library_t * pGenlib,Vec_Str_t * vStr,char * pFileName)391 int Map_LibraryReadFileTreeStr( Map_SuperLib_t * pLib, Mio_Library_t * pGenlib, Vec_Str_t * vStr, char * pFileName )
392 {
393 ProgressBar * pProgress;
394 char pBuffer[5000];
395 Map_Super_t * pGate;
396 char * pTemp = 0, * pLibName;
397 int nCounter, k, i;
398 int RetValue, nPos = 0;
399
400 // skip empty and comment lines
401 // while ( fgets( pBuffer, 5000, pFile ) != NULL )
402 while ( 1 )
403 {
404 RetValue = Vec_StrGets( pBuffer, 5000, vStr, &nPos );
405 if ( RetValue == 0 )
406 return 0;
407 // skip leading spaces
408 for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ );
409 // skip comment lines and empty lines
410 if ( *pTemp != 0 && *pTemp != '#' )
411 break;
412 }
413
414 pLibName = strtok( pTemp, " \t\r\n" );
415 // pLib->pGenlib = (Mio_Library_t *)Abc_FrameReadLibGen();
416 pLib->pGenlib = pGenlib;
417 // if ( pLib->pGenlib == NULL || strcmp( , pLibName ) )
418 if ( pLib->pGenlib == NULL || Map_LibraryCompareLibNames(Mio_LibraryReadName(pLib->pGenlib), pLibName) )
419 {
420 printf( "Supergate library \"%s\" requires the use of genlib library \"%s\".\n", pFileName, pLibName );
421 return 0;
422 }
423
424 // read the number of variables
425 RetValue = Vec_StrGets( pBuffer, 5000, vStr, &nPos );
426 if ( RetValue == 0 )
427 return 0;
428 RetValue = sscanf( pBuffer, "%d\n", &pLib->nVarsMax );
429 if ( pLib->nVarsMax < 2 || pLib->nVarsMax > 10 )
430 {
431 printf( "Suspicious number of variables (%d).\n", pLib->nVarsMax );
432 return 0;
433 }
434
435 // read the number of gates
436 RetValue = Vec_StrGets( pBuffer, 5000, vStr, &nPos );
437 if ( RetValue == 0 )
438 return 0;
439 RetValue = sscanf( pBuffer, "%d\n", &pLib->nSupersReal );
440 if ( pLib->nSupersReal < 1 || pLib->nSupersReal > 10000000 )
441 {
442 printf( "Suspicious number of gates (%d).\n", pLib->nSupersReal );
443 return 0;
444 }
445
446 // read the number of lines
447 RetValue = Vec_StrGets( pBuffer, 5000, vStr, &nPos );
448 if ( RetValue == 0 )
449 return 0;
450 RetValue = sscanf( pBuffer, "%d\n", &pLib->nLines );
451 if ( pLib->nLines < 1 || pLib->nLines > 10000000 )
452 {
453 printf( "Suspicious number of lines (%d).\n", pLib->nLines );
454 return 0;
455 }
456
457 // allocate room for supergate pointers
458 pLib->ppSupers = ABC_ALLOC( Map_Super_t *, pLib->nLines + 10000 );
459
460 // create the elementary supergates
461 for ( i = 0; i < pLib->nVarsMax; i++ )
462 {
463 // get a new gate
464 pGate = (Map_Super_t *)Extra_MmFixedEntryFetch( pLib->mmSupers );
465 memset( pGate, 0, sizeof(Map_Super_t) );
466 // assign the elementary variable, the truth table, and the delays
467 pGate->Num = i;
468 // set the truth table
469 pGate->uTruth[0] = pLib->uTruths[i][0];
470 pGate->uTruth[1] = pLib->uTruths[i][1];
471 // set the arrival times of all input to non-existent delay
472 for ( k = 0; k < pLib->nVarsMax; k++ )
473 {
474 pGate->tDelaysR[k].Rise = pGate->tDelaysR[k].Fall = MAP_NO_VAR;
475 pGate->tDelaysF[k].Rise = pGate->tDelaysF[k].Fall = MAP_NO_VAR;
476 }
477 // set an existent arrival time for rise and fall
478 pGate->tDelaysR[i].Rise = 0.0;
479 pGate->tDelaysF[i].Fall = 0.0;
480 // set the gate
481 pLib->ppSupers[i] = pGate;
482 }
483
484 // read the lines
485 nCounter = pLib->nVarsMax;
486 pProgress = Extra_ProgressBarStart( stdout, pLib->nLines );
487 // while ( fgets( pBuffer, 5000, pFile ) != NULL )
488 while ( Vec_StrGets( pBuffer, 5000, vStr, &nPos ) )
489 {
490 for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ );
491 if ( pTemp[0] == '\0' )
492 continue;
493 // if ( pTemp[0] == 'a' || pTemp[2] == 'a' )
494 // {
495 // pLib->nLines--;
496 // continue;
497 // }
498
499 // get the gate
500 pGate = Map_LibraryReadGateTree( pLib, pTemp, nCounter, pLib->nVarsMax );
501 if ( pGate == NULL )
502 {
503 Extra_ProgressBarStop( pProgress );
504 return 0;
505 }
506 pLib->ppSupers[nCounter++] = pGate;
507 // later we will derive: truth table, delays, area, number of component gates, etc
508
509 // update the progress bar
510 Extra_ProgressBarUpdate( pProgress, nCounter, NULL );
511 }
512 Extra_ProgressBarStop( pProgress );
513 if ( nCounter != pLib->nLines )
514 printf( "The number of lines read (%d) is different from what the file says (%d).\n", nCounter, pLib->nLines );
515 pLib->nSupersAll = nCounter;
516 // count the number of real supergates
517 nCounter = 0;
518 for ( k = 0; k < pLib->nLines; k++ )
519 nCounter += pLib->ppSupers[k]->fSuper;
520 if ( nCounter != pLib->nSupersReal )
521 printf( "The number of gates read (%d) is different what the file says (%d).\n", nCounter, pLib->nSupersReal );
522 pLib->nSupersReal = nCounter;
523 return 1;
524 }
Map_LibraryReadTree(Map_SuperLib_t * pLib,Mio_Library_t * pGenlib,char * pFileName,char * pExcludeFile)525 int Map_LibraryReadTree( Map_SuperLib_t * pLib, Mio_Library_t * pGenlib, char * pFileName, char * pExcludeFile )
526 {
527 char * pBuffer;
528 Vec_Str_t * vStr;
529 int Status, num;
530 Abc_Frame_t * pAbc;
531 st__table * tExcludeGate = 0;
532
533 // read the beginning of the file
534 assert( pLib->pGenlib == NULL );
535 // pFile = Io_FileOpen( pFileName, "open_path", "r", 1 );
536 pBuffer = Mio_ReadFile( pFileName, 0 );
537 if ( pBuffer == NULL )
538 {
539 printf( "Cannot open input file \"%s\".\n", pFileName );
540 return 0;
541 }
542 vStr = Vec_StrAllocArray( pBuffer, strlen(pBuffer) );
543
544 if ( pExcludeFile )
545 {
546 pAbc = Abc_FrameGetGlobalFrame();
547
548 tExcludeGate = st__init_table(strcmp, st__strhash);
549 if ( (num = Mio_LibraryReadExclude( pExcludeFile, tExcludeGate )) == -1 )
550 {
551 st__free_table( tExcludeGate );
552 tExcludeGate = 0;
553 Vec_StrFree( vStr );
554 return 0;
555 }
556
557 fprintf ( Abc_FrameReadOut( pAbc ), "Read %d gates from exclude file\n", num );
558 }
559
560 Status = Map_LibraryReadFileTreeStr( pLib, pGenlib, vStr, pFileName );
561 Vec_StrFree( vStr );
562 if ( Status == 0 )
563 return 0;
564 // prepare the info about the library
565 return Map_LibraryDeriveGateInfo( pLib, tExcludeGate );
566 }
567
568
569
570
571
572
573
574
575 /**Function*************************************************************
576
577 Synopsis [Derives information about the library.]
578
579 Description []
580
581 SideEffects []
582
583 SeeAlso []
584
585 ***********************************************************************/
Map_LibraryDeriveGateInfo(Map_SuperLib_t * pLib,st__table * tExcludeGate)586 int Map_LibraryDeriveGateInfo( Map_SuperLib_t * pLib, st__table * tExcludeGate )
587 {
588 Map_Super_t * pGate, * pFanin;
589 Mio_Pin_t * pPin;
590 unsigned uCanon[2];
591 unsigned uTruths[6][2];
592 int i, k, nRealVars;
593
594 // set all the derivable info related to the supergates
595 for ( i = pLib->nVarsMax; i < (int)pLib->nLines; i++ )
596 {
597 pGate = pLib->ppSupers[i];
598
599 if ( tExcludeGate )
600 {
601 if ( st__is_member( tExcludeGate, Mio_GateReadName( pGate->pRoot ) ) )
602 pGate->fExclude = 1;
603 for ( k = 0; k < (int)pGate->nFanins; k++ )
604 {
605 pFanin = pGate->pFanins[k];
606 if ( pFanin->fExclude )
607 {
608 pGate->fExclude = 1;
609 continue;
610 }
611 }
612 }
613
614 // collect the truth tables of the fanins
615 for ( k = 0; k < (int)pGate->nFanins; k++ )
616 {
617 pFanin = pGate->pFanins[k];
618 uTruths[k][0] = pFanin->uTruth[0];
619 uTruths[k][1] = pFanin->uTruth[1];
620 }
621 // derive the new truth table
622 Mio_DeriveTruthTable( pGate->pRoot, uTruths, pGate->nFanins, 6, pGate->uTruth );
623
624 // set the initial delays of the supergate
625 for ( k = 0; k < pLib->nVarsMax; k++ )
626 {
627 pGate->tDelaysR[k].Rise = pGate->tDelaysR[k].Fall = MAP_NO_VAR;
628 pGate->tDelaysF[k].Rise = pGate->tDelaysF[k].Fall = MAP_NO_VAR;
629 }
630 // get the linked list of pins for the given root gate
631 pPin = Mio_GateReadPins( pGate->pRoot );
632 // update the initial delay of the supergate using info from the corresponding pin
633 for ( k = 0; k < (int)pGate->nFanins; k++, pPin = Mio_PinReadNext(pPin) )
634 {
635 // if there is no corresponding pin, this is a bug, return fail
636 if ( pPin == NULL )
637 {
638 printf( "There are less pins than gate inputs.\n" );
639 return 0;
640 }
641 // update the delay information of k-th fanins info from the corresponding pin
642 Map_LibraryAddFaninDelays( pLib, pGate, pGate->pFanins[k], pPin );
643 }
644 // if there are some pins left, this is a bug, return fail
645 if ( pPin != NULL )
646 {
647 printf( "There are more pins than gate inputs.\n" );
648 return 0;
649 }
650 // find the max delay
651 pGate->tDelayMax.Rise = pGate->tDelayMax.Fall = MAP_NO_VAR;
652 for ( k = 0; k < pLib->nVarsMax; k++ )
653 {
654 // the rise of the output depends on the rise and fall of the output
655 if ( pGate->tDelayMax.Rise < pGate->tDelaysR[k].Rise )
656 pGate->tDelayMax.Rise = pGate->tDelaysR[k].Rise;
657 if ( pGate->tDelayMax.Rise < pGate->tDelaysR[k].Fall )
658 pGate->tDelayMax.Rise = pGate->tDelaysR[k].Fall;
659 // the fall of the output depends on the rise and fall of the output
660 if ( pGate->tDelayMax.Fall < pGate->tDelaysF[k].Rise )
661 pGate->tDelayMax.Fall = pGate->tDelaysF[k].Rise;
662 if ( pGate->tDelayMax.Fall < pGate->tDelaysF[k].Fall )
663 pGate->tDelayMax.Fall = pGate->tDelaysF[k].Fall;
664
665 pGate->tDelaysF[k].Worst = MAP_MAX( pGate->tDelaysF[k].Fall, pGate->tDelaysF[k].Rise );
666 pGate->tDelaysR[k].Worst = MAP_MAX( pGate->tDelaysR[k].Fall, pGate->tDelaysR[k].Rise );
667 }
668
669 // count gates and area of the supergate
670 pGate->nGates = 1;
671 pGate->Area = (float)Mio_GateReadArea(pGate->pRoot);
672 for ( k = 0; k < (int)pGate->nFanins; k++ )
673 {
674 pGate->nGates += pGate->pFanins[k]->nGates;
675 pGate->Area += pGate->pFanins[k]->Area;
676 }
677 // do not add the gate to the table, if this gate is an internal gate
678 // of some supegate and does not correspond to a supergate output
679 if ( ( !pGate->fSuper ) || pGate->fExclude )
680 continue;
681
682 // find the maximum index of a variable in the support of the supergates
683 // this is important for two reasons:
684 // (1) to limit the number of permutations considered for canonicization
685 // (2) to get rid of equivalence phases to speed-up matching
686 nRealVars = Map_LibraryGetMaxSuperPi_rec( pGate ) + 1;
687 assert( nRealVars > 0 && nRealVars <= pLib->nVarsMax );
688 // if there are some problems with this code, try this instead
689 // nRealVars = pLib->nVarsMax;
690
691 // find the N-canonical form of this supergate
692 pGate->nPhases = Map_CanonComputeSlow( pLib->uTruths, pLib->nVarsMax, nRealVars, pGate->uTruth, pGate->uPhases, uCanon );
693 // add the supergate into the table by its N-canonical table
694 Map_SuperTableInsertC( pLib->tTableC, uCanon, pGate );
695 /*
696 {
697 int uCanon1, uCanon2;
698 uCanon1 = uCanon[0];
699 pGate->uTruth[0] = ~pGate->uTruth[0];
700 pGate->uTruth[1] = ~pGate->uTruth[1];
701 Map_CanonComputeSlow( pLib->uTruths, pLib->nVarsMax, nRealVars, pGate->uTruth, pGate->uPhases, uCanon );
702 uCanon2 = uCanon[0];
703 Rwt_Man5ExploreCount( uCanon1 < uCanon2 ? uCanon1 : uCanon2 );
704 }
705 */
706 }
707 // sort the gates in each line
708 Map_SuperTableSortSupergatesByDelay( pLib->tTableC, pLib->nSupersAll );
709
710 // let the glory be manifest
711 // Map_LibraryPrintTree( pLib );
712 return 1;
713 }
714
715 /**Function*************************************************************
716
717 Synopsis [Finds the largest PI number in the support of the supergate.]
718
719 Description []
720
721 SideEffects []
722
723 SeeAlso []
724
725 ***********************************************************************/
Map_LibraryGetMaxSuperPi_rec(Map_Super_t * pGate)726 int Map_LibraryGetMaxSuperPi_rec( Map_Super_t * pGate )
727 {
728 int i, VarCur, VarMax = 0;
729 if ( pGate->pRoot == NULL )
730 return pGate->Num;
731 for ( i = 0; i < (int)pGate->nFanins; i++ )
732 {
733 VarCur = Map_LibraryGetMaxSuperPi_rec( pGate->pFanins[i] );
734 if ( VarMax < VarCur )
735 VarMax = VarCur;
736 }
737 return VarMax;
738 }
739
740 /**Function*************************************************************
741
742 Synopsis [Finds the largest PI number in the support of the supergate.]
743
744 Description []
745
746 SideEffects []
747
748 SeeAlso []
749
750 ***********************************************************************/
Map_LibraryGetGateSupp_rec(Map_Super_t * pGate)751 unsigned Map_LibraryGetGateSupp_rec( Map_Super_t * pGate )
752 {
753 unsigned uSupport;
754 int i;
755 if ( pGate->pRoot == NULL )
756 return (unsigned)(1 << (pGate->Num));
757 uSupport = 0;
758 for ( i = 0; i < (int)pGate->nFanins; i++ )
759 uSupport |= Map_LibraryGetGateSupp_rec( pGate->pFanins[i] );
760 return uSupport;
761 }
762
763 /**Function*************************************************************
764
765 Synopsis [Derives the pin-to-pin delay constraints for the supergate.]
766
767 Description []
768
769 SideEffects []
770
771 SeeAlso []
772
773 ***********************************************************************/
Map_LibraryAddFaninDelays(Map_SuperLib_t * pLib,Map_Super_t * pGate,Map_Super_t * pFanin,Mio_Pin_t * pPin)774 void Map_LibraryAddFaninDelays( Map_SuperLib_t * pLib, Map_Super_t * pGate, Map_Super_t * pFanin, Mio_Pin_t * pPin )
775 {
776 Mio_PinPhase_t PinPhase;
777 float tDelayBlockRise, tDelayBlockFall, tDelayPin;
778 int fMaxDelay = 0;
779 int i;
780
781 // use this node to enable max-delay model
782 if ( fMaxDelay )
783 {
784 float tDelayBlockMax;
785 // get the maximum delay
786 tDelayBlockMax = (float)Mio_PinReadDelayBlockMax(pPin);
787 // go through the supergate inputs
788 for ( i = 0; i < pLib->nVarsMax; i++ )
789 {
790 if ( pFanin->tDelaysR[i].Rise < 0 )
791 continue;
792 tDelayPin = pFanin->tDelaysR[i].Rise + tDelayBlockMax;
793 if ( pGate->tDelaysR[i].Rise < tDelayPin )
794 pGate->tDelaysR[i].Rise = tDelayPin;
795 }
796 // go through the supergate inputs
797 for ( i = 0; i < pLib->nVarsMax; i++ )
798 {
799 if ( pFanin->tDelaysF[i].Fall < 0 )
800 continue;
801 tDelayPin = pFanin->tDelaysF[i].Fall + tDelayBlockMax;
802 if ( pGate->tDelaysF[i].Fall < tDelayPin )
803 pGate->tDelaysF[i].Fall = tDelayPin;
804 }
805 return;
806 }
807
808 // get the interesting parameters of this pin
809 PinPhase = Mio_PinReadPhase(pPin);
810 tDelayBlockRise = (float)Mio_PinReadDelayBlockRise( pPin );
811 tDelayBlockFall = (float)Mio_PinReadDelayBlockFall( pPin );
812
813 // update the rise and fall of the output depending on the phase of the pin
814 if ( PinPhase != MIO_PHASE_INV ) // NONINV phase is present
815 {
816 // the rise of the gate is determined by the rise of the fanin
817 // the fall of the gate is determined by the fall of the fanin
818 for ( i = 0; i < pLib->nVarsMax; i++ )
819 {
820 ////////////////////////////////////////////////////////
821 // consider the rise of the gate
822 ////////////////////////////////////////////////////////
823 // check two types of constraints on the rise of the fanin:
824 // (1) the constraints related to the rise of the PIs
825 // (2) the constraints related to the fall of the PIs
826 if ( pFanin->tDelaysR[i].Rise >= 0 ) // case (1)
827 { // fanin's rise depends on the rise of i-th PI
828 // update the rise of the gate's output
829 if ( pGate->tDelaysR[i].Rise < pFanin->tDelaysR[i].Rise + tDelayBlockRise )
830 pGate->tDelaysR[i].Rise = pFanin->tDelaysR[i].Rise + tDelayBlockRise;
831 }
832 if ( pFanin->tDelaysR[i].Fall >= 0 ) // case (2)
833 { // fanin's rise depends on the fall of i-th PI
834 // update the rise of the gate's output
835 if ( pGate->tDelaysR[i].Fall < pFanin->tDelaysR[i].Fall + tDelayBlockRise )
836 pGate->tDelaysR[i].Fall = pFanin->tDelaysR[i].Fall + tDelayBlockRise;
837 }
838 ////////////////////////////////////////////////////////
839
840 ////////////////////////////////////////////////////////
841 // consider the fall of the gate (similar)
842 ////////////////////////////////////////////////////////
843 // check two types of constraints on the fall of the fanin:
844 // (1) the constraints related to the rise of the PIs
845 // (2) the constraints related to the fall of the PIs
846 if ( pFanin->tDelaysF[i].Rise >= 0 ) // case (1)
847 {
848 if ( pGate->tDelaysF[i].Rise < pFanin->tDelaysF[i].Rise + tDelayBlockFall )
849 pGate->tDelaysF[i].Rise = pFanin->tDelaysF[i].Rise + tDelayBlockFall;
850 }
851 if ( pFanin->tDelaysF[i].Fall >= 0 ) // case (2)
852 {
853 if ( pGate->tDelaysF[i].Fall < pFanin->tDelaysF[i].Fall + tDelayBlockFall )
854 pGate->tDelaysF[i].Fall = pFanin->tDelaysF[i].Fall + tDelayBlockFall;
855 }
856 ////////////////////////////////////////////////////////
857 }
858 }
859 if ( PinPhase != MIO_PHASE_NONINV ) // INV phase is present
860 {
861 // the rise of the gate is determined by the fall of the fanin
862 // the fall of the gate is determined by the rise of the fanin
863 for ( i = 0; i < pLib->nVarsMax; i++ )
864 {
865 ////////////////////////////////////////////////////////
866 // consider the rise of the gate's output
867 ////////////////////////////////////////////////////////
868 // check two types of constraints on the fall of the fanin:
869 // (1) the constraints related to the rise of the PIs
870 // (2) the constraints related to the fall of the PIs
871 if ( pFanin->tDelaysF[i].Rise >= 0 ) // case (1)
872 { // fanin's rise depends on the rise of i-th PI
873 // update the rise of the gate
874 if ( pGate->tDelaysR[i].Rise < pFanin->tDelaysF[i].Rise + tDelayBlockRise )
875 pGate->tDelaysR[i].Rise = pFanin->tDelaysF[i].Rise + tDelayBlockRise;
876 }
877 if ( pFanin->tDelaysF[i].Fall >= 0 ) // case (2)
878 { // fanin's rise depends on the fall of i-th PI
879 // update the rise of the gate
880 if ( pGate->tDelaysR[i].Fall < pFanin->tDelaysF[i].Fall + tDelayBlockRise )
881 pGate->tDelaysR[i].Fall = pFanin->tDelaysF[i].Fall + tDelayBlockRise;
882 }
883 ////////////////////////////////////////////////////////
884
885 ////////////////////////////////////////////////////////
886 // consider the fall of the gate (similar)
887 ////////////////////////////////////////////////////////
888 // check two types of constraints on the rise of the fanin:
889 // (1) the constraints related to the rise of the PIs
890 // (2) the constraints related to the fall of the PIs
891 if ( pFanin->tDelaysR[i].Rise >= 0 ) // case (1)
892 {
893 if ( pGate->tDelaysF[i].Rise < pFanin->tDelaysR[i].Rise + tDelayBlockFall )
894 pGate->tDelaysF[i].Rise = pFanin->tDelaysR[i].Rise + tDelayBlockFall;
895 }
896 if ( pFanin->tDelaysR[i].Fall >= 0 ) // case (2)
897 {
898 if ( pGate->tDelaysF[i].Fall < pFanin->tDelaysR[i].Fall + tDelayBlockFall )
899 pGate->tDelaysF[i].Fall = pFanin->tDelaysR[i].Fall + tDelayBlockFall;
900 }
901 ////////////////////////////////////////////////////////
902 }
903 }
904 }
905
906
907 /**Function*************************************************************
908
909 Synopsis [Performs phase transformation for one function.]
910
911 Description []
912
913 SideEffects []
914
915 SeeAlso []
916
917 ***********************************************************************/
Map_CalculatePhase(unsigned uTruths[][2],int nVars,unsigned uTruth,unsigned uPhase)918 unsigned Map_CalculatePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase )
919 {
920 int v, Shift;
921 for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
922 if ( uPhase & Shift )
923 uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift));
924 return uTruth;
925 }
926
927 /**Function*************************************************************
928
929 Synopsis [Performs phase transformation for one function.]
930
931 Description []
932
933 SideEffects []
934
935 SeeAlso []
936
937 ***********************************************************************/
Map_CalculatePhase6(unsigned uTruths[][2],int nVars,unsigned uTruth[],unsigned uPhase,unsigned uTruthRes[])938 void Map_CalculatePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] )
939 {
940 unsigned uTemp;
941 int v, Shift;
942
943 // initialize the result
944 uTruthRes[0] = uTruth[0];
945 uTruthRes[1] = uTruth[1];
946 if ( uPhase == 0 )
947 return;
948 // compute the phase
949 for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
950 if ( uPhase & Shift )
951 {
952 if ( Shift < 32 )
953 {
954 uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift));
955 uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift));
956 }
957 else
958 {
959 uTemp = uTruthRes[0];
960 uTruthRes[0] = uTruthRes[1];
961 uTruthRes[1] = uTemp;
962 }
963 }
964 }
965
966 /**Function*************************************************************
967
968 Synopsis [Prints the supergate library after deriving parameters.]
969
970 Description [This procedure is very useful to see the library after
971 it has been read into the mapper by "read_super" and all the information
972 about the supergates derived.]
973
974 SideEffects []
975
976 SeeAlso []
977
978 ***********************************************************************/
Map_LibraryPrintTree(Map_SuperLib_t * pLib)979 void Map_LibraryPrintTree( Map_SuperLib_t * pLib )
980 {
981 Map_Super_t * pGate;
982 int i, k;
983
984 // print all the info related to the supergates
985 // for ( i = pLib->nVarsMax; i < (int)pLib->nLines; i++ )
986 for ( i = pLib->nVarsMax; i < 20; i++ )
987 {
988 pGate = pLib->ppSupers[i];
989
990 // write the gate's fanin info and formula
991 printf( "%6d ", pGate->Num );
992 printf( "%c ", pGate->fSuper? '*' : ' ' );
993 printf( "%6s", Mio_GateReadName(pGate->pRoot) );
994 for ( k = 0; k < (int)pGate->nFanins; k++ )
995 printf( " %6d", pGate->pFanins[k]->Num );
996 printf( " %s", pGate->pFormula );
997 printf( "\n" );
998
999 // write the gate's derived info
1000 Extra_PrintBinary( stdout, pGate->uTruth, 64 );
1001 printf( " %3d", pGate->nGates );
1002 printf( " %6.2f", pGate->Area );
1003 printf( " (%4.2f, %4.2f)", pGate->tDelayMax.Rise, pGate->tDelayMax.Fall );
1004 printf( "\n" );
1005 for ( k = 0; k < pLib->nVarsMax; k++ )
1006 {
1007 // print the constraint on the rise of the gate in the form (D1, D2),
1008 // where D1 is the constraint related to the rise of the k-th PI
1009 // where D2 is the constraint related to the fall of the k-th PI
1010 if ( pGate->tDelaysR[k].Rise < 0 && pGate->tDelaysR[k].Fall < 0 )
1011 printf( " (----, ----)" );
1012 else if ( pGate->tDelaysR[k].Fall < 0 )
1013 printf( " (%4.2f, ----)", pGate->tDelaysR[k].Rise );
1014 else if ( pGate->tDelaysR[k].Rise < 0 )
1015 printf( " (----, %4.2f)", pGate->tDelaysR[k].Fall );
1016 else
1017 printf( " (%4.2f, %4.2f)", pGate->tDelaysR[k].Rise, pGate->tDelaysR[k].Fall );
1018
1019 // print the constraint on the fall of the gate in the form (D1, D2),
1020 // where D1 is the constraint related to the rise of the k-th PI
1021 // where D2 is the constraint related to the fall of the k-th PI
1022 if ( pGate->tDelaysF[k].Rise < 0 && pGate->tDelaysF[k].Fall < 0 )
1023 printf( " (----, ----)" );
1024 else if ( pGate->tDelaysF[k].Fall < 0 )
1025 printf( " (%4.2f, ----)", pGate->tDelaysF[k].Rise );
1026 else if ( pGate->tDelaysF[k].Rise < 0 )
1027 printf( " (----, %4.2f)", pGate->tDelaysF[k].Fall );
1028 else
1029 printf( " (%4.2f, %4.2f)", pGate->tDelaysF[k].Rise, pGate->tDelaysF[k].Fall );
1030 printf( "\n" );
1031 }
1032 printf( "\n" );
1033 }
1034 }
1035
1036 ////////////////////////////////////////////////////////////////////////
1037 /// END OF FILE ///
1038 ////////////////////////////////////////////////////////////////////////
1039
1040
1041 ABC_NAMESPACE_IMPL_END
1042
1043