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