cuddcache.c

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

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

  FileName    [cuddCache.c]

  PackageName [cudd]

  Synopsis    [Functions for cache insertion and lookup.]

  Description [Internal procedures included in this module:
		<ul>
		<li> cuddInitCache()
		<li> cuddCacheInsert()
		<li> cuddCacheInsert2()
		<li> cuddCacheLookup()
		<li> cuddCacheLookupZdd()
		<li> cuddCacheLookup2()
		<li> cuddCacheLookup2Zdd()
		<li> cuddConstantLookup()
		<li> cuddCacheProfile()
		<li> cuddCacheResize()
		<li> cuddCacheFlush()
		<li> cuddComputeFloorLog2()
		</ul>
	    Static procedures included in this module:
		<ul>
		</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                                                     */
/*---------------------------------------------------------------------------*/

#ifdef DD_CACHE_PROFILE
#define DD_HYSTO_BINS 8
#endif

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


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


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

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

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


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

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


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


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

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


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

  Synopsis    [Initializes the computed table.]

  Description [Initializes the computed table. It is called by
  Cudd_Init. Returns 1 in case of success; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_Init]

******************************************************************************/
int
cuddInitCache(
  DdManager * unique /* unique table */,
  unsigned int cacheSize /* initial size of the cache */,
  unsigned int maxCacheSize /* cache size beyond which no resizing occurs */)
{
    int i;
    unsigned int logSize;
#ifndef DD_CACHE_PROFILE
    DdNodePtr *mem;
    ptruint offset;
#endif

    /* Round cacheSize to largest power of 2 not greater than the requested
    ** initial cache size. */
    logSize = cuddComputeFloorLog2(ddMax(cacheSize,unique->slots/2));
    cacheSize = 1 << logSize;
    unique->acache = ALLOC(DdCache,cacheSize+1);
    if (unique->acache == NULL) {
	unique->errorCode = CUDD_MEMORY_OUT;
	return(0);
    }
    /* If the size of the cache entry is a power of 2, we want to
    ** enforce alignment to that power of two. This happens when
    ** DD_CACHE_PROFILE is not defined. */
#ifdef DD_CACHE_PROFILE
    unique->cache = unique->acache;
    unique->memused += (cacheSize) * sizeof(DdCache);
#else
    mem = (DdNodePtr *) unique->acache;
    offset = (ptruint) mem & (sizeof(DdCache) - 1);
    mem += (sizeof(DdCache) - offset) / sizeof(DdNodePtr);
    unique->cache = (DdCache *) mem;
    assert(((ptruint) unique->cache & (sizeof(DdCache) - 1)) == 0);
    unique->memused += (cacheSize+1) * sizeof(DdCache);
#endif
    unique->cacheSlots = cacheSize;
    unique->cacheShift = sizeof(int) * 8 - logSize;
    unique->maxCacheHard = maxCacheSize;
    /* If cacheSlack is non-negative, we can resize. */
    unique->cacheSlack = (int) ddMin(maxCacheSize,
	DD_MAX_CACHE_TO_SLOTS_RATIO*unique->slots) -
	2 * (int) cacheSize;
    Cudd_SetMinHit(unique,DD_MIN_HIT);
    /* Initialize to avoid division by 0 and immediate resizing. */
    unique->cacheMisses = (double) (int) (cacheSize * unique->minHit + 1);
    unique->cacheHits = 0;
    unique->totCachehits = 0;
    /* The sum of cacheMisses and totCacheMisses is always correct,
    ** even though cacheMisses is larger than it should for the reasons
    ** explained above. */
    unique->totCacheMisses = -unique->cacheMisses;
    unique->cachecollisions = 0;
    unique->cacheinserts = 0;
    unique->cacheLastInserts = 0;
    unique->cachedeletions = 0;

    /* Initialize the cache */
    for (i = 0; (unsigned) i < cacheSize; i++) {
	unique->cache[i].h = 0; /* unused slots */
	unique->cache[i].data = NULL; /* invalid entry */
#ifdef DD_CACHE_PROFILE
	unique->cache[i].count = 0;
#endif
    }

    return(1);

} /* end of cuddInitCache */


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

  Synopsis    [Inserts a result in the cache.]

  Description []

  SideEffects [None]

  SeeAlso     [cuddCacheInsert2 cuddCacheInsert1]

******************************************************************************/
void
cuddCacheInsert(
  DdManager * table,
  ptruint op,
  DdNode * f,
  DdNode * g,
  DdNode * h,
  DdNode * data)
{
    int posn;
    register DdCache *entry;
    ptruint uf, ug, uh;

    uf = (ptruint) f | (op & 0xe);
    ug = (ptruint) g | (op >> 4);
    uh = (ptruint) h;

    posn = ddCHash2(uh,uf,ug,table->cacheShift);
    entry = &table->cache[posn];

    table->cachecollisions += entry->data != NULL;
    table->cacheinserts++;

    entry->f    = (DdNode *) uf;
    entry->g    = (DdNode *) ug;
    entry->h    = uh;
    entry->data = data;
#ifdef DD_CACHE_PROFILE
    entry->count++;
#endif

} /* end of cuddCacheInsert */


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

  Synopsis    [Inserts a result in the cache for a function with two
  operands.]

  Description []

  SideEffects [None]

  SeeAlso     [cuddCacheInsert cuddCacheInsert1]

******************************************************************************/
void
cuddCacheInsert2(
  DdManager * table,
  DdNode * (*op)(DdManager *, DdNode *, DdNode *),
  DdNode * f,
  DdNode * g,
  DdNode * data)
{
    int posn;
    register DdCache *entry;

    posn = ddCHash2(op,f,g,table->cacheShift);
    entry = &table->cache[posn];

    if (entry->data != NULL) {
        table->cachecollisions++;
    }
    table->cacheinserts++;

    entry->f = f;
    entry->g = g;
    entry->h = (ptruint) op;
    entry->data = data;
#ifdef DD_CACHE_PROFILE
    entry->count++;
#endif

} /* end of cuddCacheInsert2 */


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

  Synopsis    [Inserts a result in the cache for a function with two
  operands.]

  Description []

  SideEffects [None]

  SeeAlso     [cuddCacheInsert cuddCacheInsert2]

******************************************************************************/
void
cuddCacheInsert1(
  DdManager * table,
  DdNode * (*op)(DdManager *, DdNode *),
  DdNode * f,
  DdNode * data)
{
    int posn;
    register DdCache *entry;

    posn = ddCHash2(op,f,f,table->cacheShift);
    entry = &table->cache[posn];

    if (entry->data != NULL) {
        table->cachecollisions++;
    }
    table->cacheinserts++;

    entry->f = f;
    entry->g = f;
    entry->h = (ptruint) op;
    entry->data = data;
#ifdef DD_CACHE_PROFILE
    entry->count++;
#endif

} /* end of cuddCacheInsert1 */


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

  Synopsis    [Looks up in the cache for the result of op applied to f,
  g, and h.]

  Description [Returns the result if found; it returns NULL if no
  result is found.]

  SideEffects [None]

  SeeAlso     [cuddCacheLookup2 cuddCacheLookup1]

******************************************************************************/
DdNode *
cuddCacheLookup(
  DdManager * table,
  ptruint op,
  DdNode * f,
  DdNode * g,
  DdNode * h)
{
    int posn;
    DdCache *en,*cache;
    DdNode *data;
    ptruint uf, ug, uh;

    uf = (ptruint) f | (op & 0xe);
    ug = (ptruint) g | (op >> 4);
    uh = (ptruint) h;

    cache = table->cache;
#ifdef DD_DEBUG
    if (cache == NULL) {
        return(NULL);
    }
#endif

    posn = ddCHash2(uh,uf,ug,table->cacheShift);
    en = &cache[posn];
    if (en->data != NULL && en->f==(DdNodePtr)uf && en->g==(DdNodePtr)ug &&
	en->h==uh) {
	data = Cudd_Regular(en->data);
	table->cacheHits++;
	if (data->ref == 0) {
	    cuddReclaim(table,data);
	}
	return(en->data);
    }

    /* Cache miss: decide whether to resize. */
    table->cacheMisses++;

    if (table->cacheSlack >= 0 &&
	table->cacheHits > table->cacheMisses * table->minHit) {
	cuddCacheResize(table);
    }

    return(NULL);

} /* end of cuddCacheLookup */


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

  Synopsis    [Looks up in the cache for the result of op applied to f,
  g, and h.]

  Description [Returns the result if found; it returns NULL if no
  result is found.]

  SideEffects [None]

  SeeAlso     [cuddCacheLookup2Zdd cuddCacheLookup1Zdd]

******************************************************************************/
DdNode *
cuddCacheLookupZdd(
  DdManager * table,
  ptruint op,
  DdNode * f,
  DdNode * g,
  DdNode * h)
{
    int posn;
    DdCache *en,*cache;
    DdNode *data;
    ptruint uf, ug, uh;

    uf = (ptruint) f | (op & 0xe);
    ug = (ptruint) g | (op >> 4);
    uh = (ptruint) h;

    cache = table->cache;
#ifdef DD_DEBUG
    if (cache == NULL) {
        return(NULL);
    }
#endif

    posn = ddCHash2(uh,uf,ug,table->cacheShift);
    en = &cache[posn];
    if (en->data != NULL && en->f==(DdNodePtr)uf && en->g==(DdNodePtr)ug &&
	en->h==uh) {
	data = Cudd_Regular(en->data);
	table->cacheHits++;
	if (data->ref == 0) {
	    cuddReclaimZdd(table,data);
	}
	return(en->data);
    }

    /* Cache miss: decide whether to resize. */
    table->cacheMisses++;

    if (table->cacheSlack >= 0 &&
	table->cacheHits > table->cacheMisses * table->minHit) {
	cuddCacheResize(table);
    }

    return(NULL);

} /* end of cuddCacheLookupZdd */


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

  Synopsis    [Looks up in the cache for the result of op applied to f
  and g.]

  Description [Returns the result if found; it returns NULL if no
  result is found.]

  SideEffects [None]

  SeeAlso     [cuddCacheLookup cuddCacheLookup1]

******************************************************************************/
DdNode *
cuddCacheLookup2(
  DdManager * table,
  DdNode * (*op)(DdManager *, DdNode *, DdNode *),
  DdNode * f,
  DdNode * g)
{
    int posn;
    DdCache *en,*cache;
    DdNode *data;

    cache = table->cache;
#ifdef DD_DEBUG
    if (cache == NULL) {
        return(NULL);
    }
#endif

    posn = ddCHash2(op,f,g,table->cacheShift);
    en = &cache[posn];
    if (en->data != NULL && en->f==f && en->g==g && en->h==(ptruint)op) {
	data = Cudd_Regular(en->data);
	table->cacheHits++;
	if (data->ref == 0) {
	    cuddReclaim(table,data);
	}
	return(en->data);
    }

    /* Cache miss: decide whether to resize. */
    table->cacheMisses++;

    if (table->cacheSlack >= 0 &&
	table->cacheHits > table->cacheMisses * table->minHit) {
	cuddCacheResize(table);
    }

    return(NULL);

} /* end of cuddCacheLookup2 */


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

  Synopsis [Looks up in the cache for the result of op applied to f.]

  Description [Returns the result if found; it returns NULL if no
  result is found.]

  SideEffects [None]

  SeeAlso     [cuddCacheLookup cuddCacheLookup2]

******************************************************************************/
DdNode *
cuddCacheLookup1(
  DdManager * table,
  DdNode * (*op)(DdManager *, DdNode *),
  DdNode * f)
{
    int posn;
    DdCache *en,*cache;
    DdNode *data;

    cache = table->cache;
#ifdef DD_DEBUG
    if (cache == NULL) {
        return(NULL);
    }
#endif

    posn = ddCHash2(op,f,f,table->cacheShift);
    en = &cache[posn];