| /**CFile**************************************************************** |
| |
| FileName [mapperTable.c] |
| |
| PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] |
| |
| Synopsis [Generic technology mapping engine.] |
| |
| Author [MVSIS Group] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 2.0. Started - June 1, 2004.] |
| |
| Revision [$Id: mapperTable.c,v 1.6 2005/01/23 06:59:44 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "mapperInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| // the table function for the tables |
| #define MAP_TABLE_HASH(u1,u2,nSize) (((u1) + 2003 * (u2)) % nSize) |
| |
| static void Map_SuperTableResize( Map_HashTable_t * pLib ); |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates the hash table for supergates.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Map_HashTable_t * Map_SuperTableCreate( Map_SuperLib_t * pLib ) |
| { |
| Map_HashTable_t * p; |
| // allocate the table |
| p = ABC_ALLOC( Map_HashTable_t, 1 ); |
| memset( p, 0, sizeof(Map_HashTable_t) ); |
| p->mmMan = pLib->mmEntries; |
| // allocate and clean the bins |
| p->nBins = Abc_PrimeCudd(20000); |
| p->pBins = ABC_ALLOC( Map_HashEntry_t *, p->nBins ); |
| memset( p->pBins, 0, sizeof(Map_HashEntry_t *) * p->nBins ); |
| return p; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Deallocates the supergate hash table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Map_SuperTableFree( Map_HashTable_t * p ) |
| { |
| ABC_FREE( p->pBins ); |
| ABC_FREE( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts a new entry into the hash table.] |
| |
| Description [This function inserts the new gate (pGate), which will be |
| accessible through its canonical form (uTruthC).] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Map_SuperTableInsertC( Map_HashTable_t * p, unsigned uTruthC[], Map_Super_t * pGate ) |
| { |
| Map_HashEntry_t * pEnt; |
| unsigned Key; |
| // resize the table |
| if ( p->nEntries >= 2 * p->nBins ) |
| Map_SuperTableResize( p ); |
| // check if another supergate with the same canonical form exists |
| Key = MAP_TABLE_HASH( uTruthC[0], uTruthC[1], p->nBins ); |
| for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext ) |
| if ( pEnt->uTruth[0] == uTruthC[0] && pEnt->uTruth[1] == uTruthC[1] ) |
| break; |
| // create a new entry if it does not exist |
| if ( pEnt == NULL ) |
| { |
| // add the new entry to the table |
| pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan ); |
| memset( pEnt, 0, sizeof(Map_HashEntry_t) ); |
| pEnt->uTruth[0] = uTruthC[0]; |
| pEnt->uTruth[1] = uTruthC[1]; |
| // add the hash table entry to the corresponding linked list in the table |
| pEnt->pNext = p->pBins[Key]; |
| p->pBins[Key] = pEnt; |
| p->nEntries++; |
| } |
| // add the supergate to the entry |
| pGate->pNext = pEnt->pGates; |
| pEnt->pGates = pGate; |
| return 0; |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts a new entry into the library.] |
| |
| Description [This function inserts the new gate (pGate), which will be |
| accessible through its unfolded function (uTruth).] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Map_SuperTableInsert( Map_HashTable_t * p, unsigned uTruth[], Map_Super_t * pGate, unsigned uPhase ) |
| { |
| Map_HashEntry_t * pEnt; |
| unsigned Key; |
| // resize the table |
| if ( p->nEntries >= 2 * p->nBins ) |
| Map_SuperTableResize( p ); |
| // check if this entry already exists |
| Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins ); |
| for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext ) |
| if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] ) |
| return 1; |
| // add the new hash table entry to the table |
| pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan ); |
| memset( pEnt, 0, sizeof(Map_HashEntry_t) ); |
| pEnt->uTruth[0] = uTruth[0]; |
| pEnt->uTruth[1] = uTruth[1]; |
| pEnt->pGates = pGate; |
| pEnt->uPhase = uPhase; |
| // add the hash table to the corresponding linked list in the table |
| pEnt->pNext = p->pBins[Key]; |
| p->pBins[Key] = pEnt; |
| p->nEntries++; |
| /* |
| printf( "Adding gate: %10u ", Key ); |
| Map_LibraryPrintSupergate( pGate ); |
| Extra_PrintBinary( stdout, uTruth, 32 ); |
| printf( "\n" ); |
| */ |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Looks up an entry in the library.] |
| |
| Description [This function looks up the function, given by its truth table, |
| and return two things: (1) the linked list of supergates, which can implement |
| the functions of this N-class; (2) the phase, which should be applied to the |
| given function, in order to derive the canonical form of this N-class.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Map_Super_t * Map_SuperTableLookupC( Map_SuperLib_t * p, unsigned uTruth[] ) |
| { |
| Map_HashEntry_t * pEnt; |
| unsigned Key; |
| Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->tTableC->nBins ); |
| for ( pEnt = p->tTableC->pBins[Key]; pEnt; pEnt = pEnt->pNext ) |
| if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] ) |
| return pEnt->pGates; |
| return NULL; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Looks up an entry in the library.] |
| |
| Description [This function looks up the function, given by its truth table, |
| and return two things: (1) the linked list of supergates, which can implement |
| the functions of this N-class; (2) the phase, which should be applied to the |
| given function, in order to derive the canonical form of this N-class.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Map_Super_t * Map_SuperTableLookup( Map_HashTable_t * p, unsigned uTruth[], unsigned * puPhase ) |
| { |
| Map_HashEntry_t * pEnt; |
| unsigned Key; |
| Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins ); |
| for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext ) |
| if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] ) |
| { |
| *puPhase = pEnt->uPhase; |
| return pEnt->pGates; |
| } |
| return NULL; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Resizes the table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Map_SuperTableResize( Map_HashTable_t * p ) |
| { |
| Map_HashEntry_t ** pBinsNew; |
| Map_HashEntry_t * pEnt, * pEnt2; |
| int nBinsNew, Counter, i; |
| unsigned Key; |
| // get the new table size |
| nBinsNew = Abc_PrimeCudd(2 * p->nBins); |
| // allocate a new array |
| pBinsNew = ABC_ALLOC( Map_HashEntry_t *, nBinsNew ); |
| memset( pBinsNew, 0, sizeof(Map_HashEntry_t *) * nBinsNew ); |
| // rehash the entries from the old table |
| Counter = 0; |
| for ( i = 0; i < p->nBins; i++ ) |
| for ( pEnt = p->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; |
| pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL ) |
| { |
| Key = MAP_TABLE_HASH( pEnt->uTruth[0], pEnt->uTruth[1], nBinsNew ); |
| pEnt->pNext = pBinsNew[Key]; |
| pBinsNew[Key] = pEnt; |
| Counter++; |
| } |
| assert( Counter == p->nEntries ); |
| // replace the table and the parameters |
| ABC_FREE( p->pBins ); |
| p->pBins = pBinsNew; |
| p->nBins = nBinsNew; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compares the supergates by the number of times they are used.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Map_SuperTableCompareSupergates( Map_Super_t ** ppS1, Map_Super_t ** ppS2 ) |
| { |
| if ( (*ppS1)->nUsed > (*ppS2)->nUsed ) |
| return -1; |
| if ( (*ppS1)->nUsed < (*ppS2)->nUsed ) |
| return 1; |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compares the supergates by the number of times they are used.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Map_SuperTableCompareGatesInList( Map_Super_t ** ppS1, Map_Super_t ** ppS2 ) |
| { |
| // if ( (*ppS1)->tDelayMax.Rise > (*ppS2)->tDelayMax.Rise ) |
| if ( (*ppS1)->Area > (*ppS2)->Area ) |
| return -1; |
| // if ( (*ppS1)->tDelayMax.Rise < (*ppS2)->tDelayMax.Rise ) |
| if ( (*ppS1)->Area < (*ppS2)->Area ) |
| return 1; |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Sorts supergates by usefulness and prints out most useful.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Map_SuperTableSortSupergates( Map_HashTable_t * p, int nSupersMax ) |
| { |
| Map_HashEntry_t * pEnt; |
| Map_Super_t ** ppSupers; |
| Map_Super_t * pSuper; |
| int nSupers, i; |
| |
| // copy all the supergates into one array |
| ppSupers = ABC_ALLOC( Map_Super_t *, nSupersMax ); |
| nSupers = 0; |
| for ( i = 0; i < p->nBins; i++ ) |
| for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext ) |
| for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext ) |
| ppSupers[nSupers++] = pSuper; |
| |
| // sort by usage |
| qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), |
| (int (*)(const void *, const void *)) Map_SuperTableCompareSupergates ); |
| assert( Map_SuperTableCompareSupergates( ppSupers, ppSupers + nSupers - 1 ) <= 0 ); |
| |
| // print out the "top ten" |
| // for ( i = 0; i < nSupers; i++ ) |
| for ( i = 0; i < 10; i++ ) |
| { |
| if ( ppSupers[i]->nUsed == 0 ) |
| break; |
| printf( "%5d : ", ppSupers[i]->nUsed ); |
| printf( "%5d ", ppSupers[i]->Num ); |
| printf( "A = %5.2f ", ppSupers[i]->Area ); |
| printf( "D = %5.2f ", ppSupers[i]->tDelayMax.Rise ); |
| printf( "%s", ppSupers[i]->pFormula ); |
| printf( "\n" ); |
| } |
| ABC_FREE( ppSupers ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Sorts supergates by max delay for each truth table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Map_SuperTableSortSupergatesByDelay( Map_HashTable_t * p, int nSupersMax ) |
| { |
| Map_HashEntry_t * pEnt; |
| Map_Super_t ** ppSupers; |
| Map_Super_t * pSuper; |
| int nSupers, i, k; |
| |
| ppSupers = ABC_ALLOC( Map_Super_t *, nSupersMax ); |
| for ( i = 0; i < p->nBins; i++ ) |
| for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext ) |
| { |
| // collect the gates in this entry |
| nSupers = 0; |
| for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext ) |
| { |
| // skip supergates, whose root is the AND gate |
| // if ( strcmp( Mio_GateReadName(pSuper->pRoot), "and" ) == 0 ) |
| // continue; |
| ppSupers[nSupers++] = pSuper; |
| } |
| pEnt->pGates = NULL; |
| if ( nSupers == 0 ) |
| continue; |
| // sort the gates by delay |
| qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), |
| (int (*)(const void *, const void *)) Map_SuperTableCompareGatesInList ); |
| assert( Map_SuperTableCompareGatesInList( ppSupers, ppSupers + nSupers - 1 ) <= 0 ); |
| // link them in the reverse order |
| for ( k = 0; k < nSupers; k++ ) |
| { |
| ppSupers[k]->pNext = pEnt->pGates; |
| pEnt->pGates = ppSupers[k]; |
| } |
| // save the number of supergates in the list |
| pEnt->pGates->nSupers = nSupers; |
| } |
| ABC_FREE( ppSupers ); |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
