/**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