cuddlcache.c

主要进行大规模的电路综合

/**CFile***********************************************************************

  FileName    [cuddLCache.c]

  PackageName [cudd]

  Synopsis    [Functions for local caches.]

  Description [Internal procedures included in this module:
		<ul>
		<li> cuddLocalCacheInit()
		<li> cuddLocalCacheQuit()
		<li> cuddLocalCacheInsert()
		<li> cuddLocalCacheLookup()
		<li> cuddLocalCacheClearDead()
		<li> cuddLocalCacheClearAll()
		<li> cuddLocalCacheProfile()
		<li> cuddHashTableInit()
		<li> cuddHashTableQuit()
		<li> cuddHashTableInsert()
		<li> cuddHashTableLookup()
		<li> cuddHashTableInsert2()
		<li> cuddHashTableLookup2()
		<li> cuddHashTableInsert3()
		<li> cuddHashTableLookup3()
		</ul>
	    Static procedures included in this module:
		<ul>
		<li> cuddLocalCacheResize()
		<li> ddLCHash()
		<li> cuddLocalCacheAddToList()
		<li> cuddLocalCacheRemoveFromList()
		<li> cuddHashTableResize()
		<li> cuddHashTableAlloc()
		</ul> ]

  SeeAlso     []

  Author      [Fabio Somenzi]

  Copyright [ This file was created at the University of Colorado at
  Boulder.  The University of Colorado at Boulder makes no warranty
  about the suitability of this software for any purpose.  It is
  presented on an AS IS basis.]

******************************************************************************/

#include    "util.h"
#include    "cuddInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

#define DD_MAX_HASHTABLE_DENSITY 2	/* tells when to resize a table */

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef lint
static char rcsid[] DD_UNUSED = "$Id: cuddLCache.c,v 1.1.1.1 2003/02/24 22:23:52 wjiang Exp $";
#endif

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/**Macro***********************************************************************

  Synopsis    [Computes hash function for keys of two operands.]

  Description []

  SideEffects [None]

  SeeAlso     [ddLCHash3 ddLCHash]

******************************************************************************/
#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
#define ddLCHash2(f,g,shift) \
((((unsigned)(unsigned long)(f) * DD_P1 + \
   (unsigned)(unsigned long)(g)) * DD_P2) >> (shift))
#else
#define ddLCHash2(f,g,shift) \
((((unsigned)(f) * DD_P1 + (unsigned)(g)) * DD_P2) >> (shift))
#endif


/**Macro***********************************************************************

  Synopsis    [Computes hash function for keys of three operands.]

  Description []

  SideEffects [None]

  SeeAlso     [ddLCHash2 ddLCHash]

******************************************************************************/
#define ddLCHash3(f,g,h,shift) ddCHash2(f,g,h,shift)


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void cuddLocalCacheResize ARGS((DdLocalCache *cache));
DD_INLINE static unsigned int ddLCHash ARGS((DdNodePtr *key, unsigned int keysize, int shift));
static void cuddLocalCacheAddToList ARGS((DdLocalCache *cache));
static void cuddLocalCacheRemoveFromList ARGS((DdLocalCache *cache));
static int cuddHashTableResize ARGS((DdHashTable *hash));
DD_INLINE static DdHashItem * cuddHashTableAlloc ARGS((DdHashTable *hash));

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


/**Function********************************************************************

  Synopsis    [Initializes a local computed table.]

  Description [Initializes a computed table.  Returns a pointer the
  the new local cache in case of success; NULL otherwise.]

  SideEffects [None]

  SeeAlso     [cuddInitCache]

******************************************************************************/
DdLocalCache *
cuddLocalCacheInit(
  DdManager * manager /* manager */,
  unsigned int  keySize /* size of the key (number of operands) */,
  unsigned int  cacheSize /* Initial size of the cache */,
  unsigned int  maxCacheSize /* Size of the cache beyond which no resizing occurs */)
{
    DdLocalCache *cache;
    int logSize;

    cache = ALLOC(DdLocalCache,1);
    if (cache == NULL) {
	manager->errorCode = CUDD_MEMORY_OUT;
	return(NULL);
    }
    cache->manager = manager;
    cache->keysize = keySize;
    cache->itemsize = (keySize + 1) * sizeof(DdNode *);
#ifdef DD_CACHE_PROFILE
    cache->itemsize += sizeof(ptrint);
#endif
    logSize = cuddComputeFloorLog2(ddMax(cacheSize,manager->slots/2));
    cacheSize = 1 << logSize;
    cache->item = (DdLocalCacheItem *)
	ALLOC(char, cacheSize * cache->itemsize);
    if (cache->item == NULL) {
	manager->errorCode = CUDD_MEMORY_OUT;
	FREE(cache);
	return(NULL);
    }
    cache->slots = cacheSize;
    cache->shift = sizeof(int) * 8 - logSize;
    cache->maxslots = ddMin(maxCacheSize,manager->slots);
    cache->minHit = manager->minHit;
    /* Initialize to avoid division by 0 and immediate resizing. */
    cache->lookUps = (double) (int) (cacheSize * cache->minHit + 1);
    cache->hits = 0;
    manager->memused += cacheSize * cache->itemsize + sizeof(DdLocalCache);

    /* Initialize the cache. */
    memset(cache->item, 0, cacheSize * cache->itemsize);

    /* Add to manager's list of local caches for GC. */
    cuddLocalCacheAddToList(cache);

    return(cache);

} /* end of cuddLocalCacheInit */


/**Function********************************************************************

  Synopsis    [Shuts down a local computed table.]

  Description [Initializes the computed table. It is called by
  Cudd_Init. Returns a pointer the the new local cache in case of
  success; NULL otherwise.]

  SideEffects [None]

  SeeAlso     [cuddLocalCacheInit]

******************************************************************************/
void
cuddLocalCacheQuit(
  DdLocalCache * cache /* cache to be shut down */)
{
    cache->manager->memused -=
	cache->slots * cache->itemsize + sizeof(DdLocalCache);
    cuddLocalCacheRemoveFromList(cache);
    FREE(cache->item);
    FREE(cache);

    return;

} /* end of cuddLocalCacheQuit */


/**Function********************************************************************

  Synopsis    [Inserts a result in a local cache.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
void
cuddLocalCacheInsert(
  DdLocalCache * cache,
  DdNodePtr * key,
  DdNode * value)
{
    unsigned int posn;
    DdLocalCacheItem *entry;

    posn = ddLCHash(key,cache->keysize,cache->shift);
    entry = (DdLocalCacheItem *) ((char *) cache->item +
				  posn * cache->itemsize);
    memcpy(entry->key,key,cache->keysize * sizeof(DdNode *));
    entry->value = value;
#ifdef DD_CACHE_PROFILE
    entry->count++;
#endif

} /* end of cuddLocalCacheInsert */


/**Function********************************************************************

  Synopsis [Looks up in a local cache.]

  Description [Looks up in a local cache. Returns the result if found;
  it returns NULL if no result is found.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
DdNode *
cuddLocalCacheLookup(
  DdLocalCache * cache,
  DdNodePtr * key)
{
    unsigned int posn;
    DdLocalCacheItem *entry;
    DdNode *value;

    cache->lookUps++;
    posn = ddLCHash(key,cache->keysize,cache->shift);
    entry = (DdLocalCacheItem *) ((char *) cache->item +
				  posn * cache->itemsize);
    if (entry->value != NULL &&
	memcmp(key,entry->key,cache->keysize*sizeof(DdNode *)) == 0) {
	cache->hits++;
	value = Cudd_Regular(entry->value);
	if (value->ref == 0) {
	    cuddReclaim(cache->manager,value);
	}
	return(entry->value);
    }

    /* Cache miss: decide whether to resize */

    if (cache->slots < cache->maxslots &&
	cache->hits > cache->lookUps * cache->minHit) {
	cuddLocalCacheResize(cache);
    }

    return(NULL);

} /* end of cuddLocalCacheLookup */


/**Function********************************************************************

  Synopsis [Clears the dead entries of the local caches of a manager.]

  Description [Clears the dead entries of the local caches of a manager.
  Used during garbage collection.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
void
cuddLocalCacheClearDead(
  DdManager * manager)
{
    DdLocalCache *cache = manager->localCaches;
    unsigned int keysize;
    unsigned int itemsize;
    unsigned int slots;
    DdLocalCacheItem *item;
    DdNodePtr *key;
    unsigned int i, j;

    while (cache != NULL) {
	keysize = cache->keysize;
	itemsize = cache->itemsize;
	slots = cache->slots;
	item = cache->item;
	for (i = 0; i < slots; i++) {
	    if (item->value != NULL && Cudd_Regular(item->value)->ref == 0) {
		item->value = NULL;
	    } else {
		key = item->key;
		for (j = 0; j < keysize; j++) {
		    if (Cudd_Regular(key[j])->ref == 0) {
			item->value = NULL;
			break;
		    }
		}
	    }
	    item = (DdLocalCacheItem *) ((char *) item + itemsize);
	}
	cache = cache->next;
    }
    return;

} /* end of cuddLocalCacheClearDead */


/**Function********************************************************************

  Synopsis [Clears the local caches of a manager.]

  Description [Clears the local caches of a manager.
  Used before reordering.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
void
cuddLocalCacheClearAll(
  DdManager * manager)
{
    DdLocalCache *cache = manager->localCaches;

    while (cache != NULL) {
	memset(cache->item, 0, cache->slots * cache->itemsize);
	cache = cache->next;
    }
    return;

} /* end of cuddLocalCacheClearAll */


#ifdef DD_CACHE_PROFILE

#define DD_HYSTO_BINS 8

/**Function********************************************************************

  Synopsis    [Computes and prints a profile of a local cache usage.]

  Description [Computes and prints a profile of a local cache usage.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
int
cuddLocalCacheProfile(
  DdLocalCache * cache)
{
    double count, mean, meansq, stddev, expected;
    long max, min;
    int imax, imin;
    int i, retval, slots;
    long *hystogram;
    int nbins = DD_HYSTO_BINS;
    int bin;
    long thiscount;
    double totalcount;
    int nzeroes;
    DdLocalCacheItem *entry;
    FILE *fp = cache->manager->out;

    slots = cache->slots;

    meansq = mean = expected = 0.0;
    max = min = (long) cache->item[0].count;
    imax = imin = nzeroes = 0;
    totalcount = 0.0;

    hystogram = ALLOC(long, nbins);
    if (hystogram == NULL) {
	return(0);
    }
    for (i = 0; i < nbins; i++) {
	hystogram[i] = 0;
    }

    for (i = 0; i < slots; i++) {
	entry = (DdLocalCacheItem *) ((char *) cache->item +
				      i * cache->itemsize);
	thiscount = (long) entry->count;
	if (thiscount > max) {
	    max = thiscount;
	    imax = i;
	}
	if (thiscount < min) {
	    min = thiscount;
	    imin = i;
	}
	if (thiscount == 0) {
	    nzeroes++;
	}
	count = (double) thiscount;
	mean += count;
	meansq += count * count;
	totalcount += count;
	expected += count * (double) i;
	bin = (i * nbins) / slots;
	hystogram[bin] += thiscount;
    }
    mean /= (double) slots;
    meansq /= (double) slots;
    stddev = sqrt(meansq - mean*mean);

    retval = fprintf(fp,"Cache stats: slots = %d average = %g ", slots, mean);
    if (retval == EOF) return(0);
    retval = fprintf(fp,"standard deviation = %g\n", stddev);
    if (retval == EOF) return(0);
    retval = fprintf(fp,"Cache max accesses = %ld for slot %d\n", max, imax);
    if (retval == EOF) return(0);
    retval = fprintf(fp,"Cache min accesses = %ld for slot %d\n", min, imin);
    if (retval == EOF) return(0);
    retval = fprintf(fp,"Cache unused slots = %d\n", nzeroes);
    if (retval == EOF) return(0);

    if (totalcount) {
	expected /= totalcount;
	retval = fprintf(fp,"Cache access hystogram for %d bins", nbins);
	if (retval == EOF) return(0);
	retval = fprintf(fp," (expected bin value = %g)\n# ", expected);
	if (retval == EOF) return(0);
	for (i = nbins - 1; i>=0; i--) {