summaryrefslogtreecommitdiffstats
path: root/src/map/mapper/mapperTable.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/mapper/mapperTable.c')
-rw-r--r--src/map/mapper/mapperTable.c402
1 files changed, 402 insertions, 0 deletions
diff --git a/src/map/mapper/mapperTable.c b/src/map/mapper/mapperTable.c
new file mode 100644
index 00000000..747fe1c8
--- /dev/null
+++ b/src/map/mapper/mapperTable.c
@@ -0,0 +1,402 @@
+/**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 DEFITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**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(int),
+ (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(int),
+ (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 ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 08:29:52 +0000