diff options
Diffstat (limited to 'src/map/mapper/mapperTable.c')
-rw-r--r-- | src/map/mapper/mapperTable.c | 402 |
1 files changed, 0 insertions, 402 deletions
diff --git a/src/map/mapper/mapperTable.c b/src/map/mapper/mapperTable.c deleted file mode 100644 index d0cb7a01..00000000 --- a/src/map/mapper/mapperTable.c +++ /dev/null @@ -1,402 +0,0 @@ -/**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" - -//////////////////////////////////////////////////////////////////////// -/// 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 = ALLOC( Map_HashTable_t, 1 ); - memset( p, 0, sizeof(Map_HashTable_t) ); - p->mmMan = pLib->mmEntries; - // allocate and clean the bins - p->nBins = Cudd_Prime(20000); - p->pBins = 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 ) -{ - FREE( p->pBins ); - 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, clk = clock(); - unsigned Key; - // get the new table size - nBinsNew = Cudd_Prime(2 * p->nBins); - // allocate a new array - pBinsNew = 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 - 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 = 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" ); - } - 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 = 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; - } - FREE( ppSupers ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |