mapperTable.c File Reference

#include "mapperInt.h"

Include dependency graph for mapperTable.c:

Go to the source code of this file.

Macros
#define	MAP_TABLE_HASH(u1, u2, nSize)
	DECLARATIONS ///.

Functions
Map_HashTable_t *	Map_SuperTableCreate (Map_SuperLib_t *pLib)
	FUNCTION DEFINITIONS ///.
void	Map_SuperTableFree (Map_HashTable_t *p)
int	Map_SuperTableInsertC (Map_HashTable_t *p, unsigned uTruthC[], Map_Super_t *pGate)
int	Map_SuperTableInsert (Map_HashTable_t *p, unsigned uTruth[], Map_Super_t *pGate, unsigned uPhase)
Map_Super_t *	Map_SuperTableLookupC (Map_SuperLib_t *p, unsigned uTruth[])
Map_Super_t *	Map_SuperTableLookup (Map_HashTable_t *p, unsigned uTruth[], unsigned *puPhase)
int	Map_SuperTableCompareSupergates (Map_Super_t **ppS1, Map_Super_t **ppS2)
int	Map_SuperTableCompareGatesInList (Map_Super_t **ppS1, Map_Super_t **ppS2)
void	Map_SuperTableSortSupergates (Map_HashTable_t *p, int nSupersMax)
void	Map_SuperTableSortSupergatesByDelay (Map_HashTable_t *p, int nSupersMax)

Macro Definition Documentation

MAP_TABLE_HASH

#define MAP_TABLE_HASH	(		u1,
			u2,
			nSize )

Value:

(((u1) + 2003 * (u2)) % nSize)

DECLARATIONS ///.

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

]

Definition at line 29 of file mapperTable.c.

Function Documentation

Map_SuperTableCompareGatesInList()

int Map_SuperTableCompareGatesInList	(	Map_Super_t **	ppS1,
		Map_Super_t **	ppS2 )

Function*************************************************************

Synopsis [Compares the supergates by the number of times they are used.]

Description []

SideEffects []

SeeAlso []

Definition at line 293 of file mapperTable.c.

{
//   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;
}

Here is the caller graph for this function:

Map_SuperTableCompareSupergates()

int Map_SuperTableCompareSupergates	(	Map_Super_t **	ppS1,
		Map_Super_t **	ppS2 )

Function*************************************************************

Synopsis [Compares the supergates by the number of times they are used.]

Description []

SideEffects []

SeeAlso []

Definition at line 273 of file mapperTable.c.

{
    if ( (*ppS1)->nUsed > (*ppS2)->nUsed )
        return -1;
    if ( (*ppS1)->nUsed < (*ppS2)->nUsed )
        return 1;
    return 0;
}

Here is the caller graph for this function:

Map_SuperTableCreate()

Map_HashTable_t * Map_SuperTableCreate

(

Map_SuperLib_t *

pLib

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Creates the hash table for supergates.]

Description []

SideEffects []

SeeAlso []

Definition at line 48 of file mapperTable.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Map_SuperTableFree()

void Map_SuperTableFree

(

Map_HashTable_t *

p

)

Function*************************************************************

Synopsis [Deallocates the supergate hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 74 of file mapperTable.c.

{
    ABC_FREE( p->pBins );
    ABC_FREE( p );
}

Here is the caller graph for this function:

Map_SuperTableInsert()

int Map_SuperTableInsert	(	Map_HashTable_t *	p,
		unsigned	uTruth[],
		Map_Super_t *	pGate,
		unsigned	uPhase )

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 []

Definition at line 137 of file mapperTable.c.

{
    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;
}

Here is the call graph for this function:

Map_SuperTableInsertC()

int Map_SuperTableInsertC	(	Map_HashTable_t *	p,
		unsigned	uTruthC[],
		Map_Super_t *	pGate )

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 []

Definition at line 92 of file mapperTable.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Map_SuperTableLookup()

Map_Super_t * Map_SuperTableLookup	(	Map_HashTable_t *	p,
		unsigned	uTruth[],
		unsigned *	puPhase )

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 []

Definition at line 208 of file mapperTable.c.

{
    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;
}

Map_SuperTableLookupC()

Map_Super_t * Map_SuperTableLookupC	(	Map_SuperLib_t *	p,
		unsigned	uTruth[] )

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 []

Definition at line 183 of file mapperTable.c.

{
    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;
}

Map_SuperTableSortSupergates()

void Map_SuperTableSortSupergates	(	Map_HashTable_t *	p,
		int	nSupersMax )

Function*************************************************************

Synopsis [Sorts supergates by usefulness and prints out most useful.]

Description []

SideEffects []

SeeAlso []

Definition at line 315 of file mapperTable.c.

{
    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, (size_t)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 );
}

Here is the call graph for this function:

Map_SuperTableSortSupergatesByDelay()

void Map_SuperTableSortSupergatesByDelay	(	Map_HashTable_t *	p,
		int	nSupersMax )

Function*************************************************************

Synopsis [Sorts supergates by max delay for each truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 362 of file mapperTable.c.

{
    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, (size_t)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 );
}

Here is the call graph for this function:

Here is the caller graph for this function: