cuddreorder.c

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

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

  FileName    [cuddReorder.c]

  PackageName [cudd]

  Synopsis    [Functions for dynamic variable reordering.]

  Description [External procedures included in this file:
		<ul>
		<li> Cudd_ReduceHeap()
		<li> Cudd_ShuffleHeap()
		</ul>
	Internal procedures included in this module:
		<ul>
		<li> cuddDynamicAllocNode()
		<li> cuddSifting()
		<li> cuddSwapping()
		<li> cuddNextHigh()
		<li> cuddNextLow()
		<li> cuddSwapInPlace()
		<li> cuddBddAlignToZdd()
		</ul>
	Static procedures included in this module:
		<ul>
		<li> ddUniqueCompare()
		<li> ddSwapAny()
		<li> ddSiftingAux()
		<li> ddSiftingUp()
		<li> ddSiftingDown()
		<li> ddSiftingBackward()
		<li> ddReorderPreprocess()
		<li> ddReorderPostprocess()
		<li> ddShuffle()
		<li> ddSiftUp()
		<li> bddFixTree()
		</ul>]

  Author      [Shipra Panda, Bernard Plessier, 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_SUBTABLE_SPARSITY 8
#define DD_SHRINK_FACTOR 2

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

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

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

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

static	int	*entry;

int	ddTotalNumberSwapping;
#ifdef DD_STATS
int	ddTotalNISwaps;
#endif

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

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

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

static int ddUniqueCompare ARGS((int *ptrX, int *ptrY));
static Move * ddSwapAny ARGS((DdManager *table, int x, int y));
static int ddSiftingAux ARGS((DdManager *table, int x, int xLow, int xHigh));
static Move * ddSiftingUp ARGS((DdManager *table, int y, int xLow));
static Move * ddSiftingDown ARGS((DdManager *table, int x, int xHigh));
static int ddSiftingBackward ARGS((DdManager *table, int size, Move *moves));
static int ddReorderPreprocess ARGS((DdManager *table));
static int ddReorderPostprocess ARGS((DdManager *table));
static int ddShuffle ARGS((DdManager *table, int *permutation));
static int ddSiftUp ARGS((DdManager *table, int x, int xLow));
static void bddFixTree ARGS((DdManager *table, MtrNode *treenode));
static int ddUpdateMtrTree ARGS((DdManager *table, MtrNode *treenode, int *perm, int *invperm));
static int ddCheckPermuation ARGS((DdManager *table, MtrNode *treenode, int *perm, int *invperm));

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


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


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

  Synopsis    [Main dynamic reordering routine.]

  Description [Main dynamic reordering routine.
  Calls one of the possible reordering procedures:
  <ul>
  <li>Swapping
  <li>Sifting
  <li>Symmetric Sifting
  <li>Group Sifting
  <li>Window Permutation
  <li>Simulated Annealing
  <li>Genetic Algorithm
  <li>Dynamic Programming (exact)
  </ul>

  For sifting, symmetric sifting, group sifting, and window
  permutation it is possible to request reordering to convergence.<p>

  The core of all methods is the reordering procedure
  cuddSwapInPlace() which swaps two adjacent variables and is based
  on Rudell's paper.
  Returns 1 in case of success; 0 otherwise. In the case of symmetric
  sifting (with and without convergence) returns 1 plus the number of
  symmetric variables, in case of success.]

  SideEffects [Changes the variable order for all diagrams and clears
  the cache.]

******************************************************************************/
int
Cudd_ReduceHeap(
  DdManager * table /* DD manager */,
  Cudd_ReorderingType heuristic /* method used for reordering */,
  int  minsize /* bound below which no reordering occurs */)
{
    DdHook *hook;
    int	result;
    unsigned int nextDyn;
#ifdef DD_STATS
    unsigned int initialSize;
    unsigned int finalSize;
#endif
    long localTime;

    /* Don't reorder if there are too many dead nodes. */
    if (table->keys - table->dead < (unsigned) minsize)
	return(1);

    if (heuristic == CUDD_REORDER_SAME) {
	heuristic = table->autoMethod;
    }
    if (heuristic == CUDD_REORDER_NONE) {
	return(1);
    }

    /* This call to Cudd_ReduceHeap does initiate reordering. Therefore
    ** we count it.
    */
    table->reorderings++;

    localTime = util_cpu_time();

    /* Run the hook functions. */
    hook = table->preReorderingHook;
    while (hook != NULL) {
	int res = (hook->f)(table, "BDD", (void *)heuristic);
	if (res == 0) return(0);
	hook = hook->next;
    }

    if (!ddReorderPreprocess(table)) return(0);
    ddTotalNumberSwapping = 0;
    
    if (table->keys > table->peakLiveNodes) {
	table->peakLiveNodes = table->keys;
    }
#ifdef DD_STATS
    initialSize = table->keys - table->isolated;
    ddTotalNISwaps = 0;

    switch(heuristic) {
    case CUDD_REORDER_RANDOM:
    case CUDD_REORDER_RANDOM_PIVOT:
	(void) fprintf(table->out,"#:I_RANDOM  ");
	break;
    case CUDD_REORDER_SIFT:
    case CUDD_REORDER_SIFT_CONVERGE:
    case CUDD_REORDER_SYMM_SIFT:
    case CUDD_REORDER_SYMM_SIFT_CONV:
    case CUDD_REORDER_GROUP_SIFT:
    case CUDD_REORDER_GROUP_SIFT_CONV:
	(void) fprintf(table->out,"#:I_SIFTING ");
	break;
    case CUDD_REORDER_WINDOW2:
    case CUDD_REORDER_WINDOW3:
    case CUDD_REORDER_WINDOW4:
    case CUDD_REORDER_WINDOW2_CONV:
    case CUDD_REORDER_WINDOW3_CONV:
    case CUDD_REORDER_WINDOW4_CONV:
	(void) fprintf(table->out,"#:I_WINDOW  ");
	break;
    case CUDD_REORDER_ANNEALING:
	(void) fprintf(table->out,"#:I_ANNEAL  ");
	break;
    case CUDD_REORDER_GENETIC:
	(void) fprintf(table->out,"#:I_GENETIC ");
	break;
    case CUDD_REORDER_LINEAR:
    case CUDD_REORDER_LINEAR_CONVERGE:
	(void) fprintf(table->out,"#:I_LINSIFT ");
	break;
    case CUDD_REORDER_EXACT:
	(void) fprintf(table->out,"#:I_EXACT   ");
	break;
    default:
	return(0);
    }
    (void) fprintf(table->out,"%8d: initial size",initialSize); 
#endif

    /* See if we should use alternate threshold for maximum growth. */
    if (table->reordCycle && table->reorderings % table->reordCycle == 0) {
	double saveGrowth = table->maxGrowth;
	table->maxGrowth = table->maxGrowthAlt;
	result = cuddTreeSifting(table,heuristic);
	table->maxGrowth = saveGrowth;
    } else {
	result = cuddTreeSifting(table,heuristic);
    }

#ifdef DD_STATS
    (void) fprintf(table->out,"\n");
    finalSize = table->keys - table->isolated;
    (void) fprintf(table->out,"#:F_REORDER %8d: final size\n",finalSize); 
    (void) fprintf(table->out,"#:T_REORDER %8g: total time (sec)\n",
		   ((double)(util_cpu_time() - localTime)/1000.0)); 
    (void) fprintf(table->out,"#:N_REORDER %8d: total swaps\n",
		   ddTotalNumberSwapping);
    (void) fprintf(table->out,"#:M_REORDER %8d: NI swaps\n",ddTotalNISwaps);
#endif

    if (result == 0)
	return(0);

    if (!ddReorderPostprocess(table))
	return(0);

    if (table->realign) {
	if (!cuddZddAlignToBdd(table))
	    return(0);
    }

    nextDyn = (table->keys - table->constants.keys + 1) *
	      DD_DYN_RATIO + table->constants.keys;
    if (table->reorderings < 20 || nextDyn > table->nextDyn)
	table->nextDyn = nextDyn;
    else
	table->nextDyn += 20;
    table->reordered = 1;

    /* Run hook functions. */
    hook = table->postReorderingHook;
    while (hook != NULL) {
	int res = (hook->f)(table, "BDD", (void *)localTime);
	if (res == 0) return(0);
	hook = hook->next;
    }
    /* Update cumulative reordering time. */
    table->reordTime += util_cpu_time() - localTime;

    return(result);

} /* end of Cudd_ReduceHeap */


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

  Synopsis    [Reorders variables according to given permutation.]

  Description [Reorders variables according to given permutation.
  The i-th entry of the permutation array contains the index of the variable
  that should be brought to the i-th level.  The size of the array should be
  equal or greater to the number of variables currently in use.
  Returns 1 in case of success; 0 otherwise.]

  SideEffects [Changes the variable order for all diagrams and clears
  the cache.]

  SeeAlso [Cudd_ReduceHeap]

******************************************************************************/
int
Cudd_ShuffleHeap(
  DdManager * table /* DD manager */,
  int * permutation /* required variable permutation */)
{

    int	result;
    int i;
    int identity = 1;
    int *perm;

    /* Don't waste time in case of identity permutation. */
    for (i = 0; i < table->size; i++) {
	if (permutation[i] != table->invperm[i]) {
	    identity = 0;
	    break;
	}
    }
    if (identity == 1) {
	return(1);
    }
    if (!ddReorderPreprocess(table)) return(0);
    if (table->keys > table->peakLiveNodes) {
	table->peakLiveNodes = table->keys;
    }

    perm = ALLOC(int, table->size);
    for (i = 0; i < table->size; i++)
	perm[permutation[i]] = i;
    if (!ddCheckPermuation(table,table->tree,perm,permutation)) {
	FREE(perm);
	return(0);
    }
    if (!ddUpdateMtrTree(table,table->tree,perm,permutation)) {
	FREE(perm);
	return(0);
    }
    FREE(perm);

    result = ddShuffle(table,permutation);

    if (!ddReorderPostprocess(table)) return(0);

    return(result);

} /* end of Cudd_ShuffleHeap */


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


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

  Synopsis    [Dynamically allocates a Node.]

  Description [Dynamically allocates a Node. This procedure is similar
  to cuddAllocNode in Cudd_Table.c, but it does not attempt garbage
  collection, because during reordering there are no dead nodes.
  Returns a pointer to a new node if successful; NULL is memory is
  full.]

  SideEffects [None]

  SeeAlso     [cuddAllocNode]

******************************************************************************/
DdNode *
cuddDynamicAllocNode(
  DdManager * table)
{
    int     i;
    DdNodePtr *mem;
    DdNode *list, *node;
    extern void (*MMoutOfMemory)(long);
    void (*saveHandler)(long);

    if (table->nextFree == NULL) {        /* free list is empty */
	/* Try to allocate a new block. */
	saveHandler = MMoutOfMemory;
	MMoutOfMemory = Cudd_OutOfMem;
	mem = (DdNodePtr *) ALLOC(DdNode, DD_MEM_CHUNK + 1);
	MMoutOfMemory = saveHandler;
	if (mem == NULL && table->stash != NULL) {
	    FREE(table->stash);
	    table->stash = NULL;
	    /* Inhibit resizing of tables. */
	    table->maxCacheHard = table->cacheSlots - 1;
	    table->cacheSlack = -(table->cacheSlots + 1);
	    for (i = 0; i < table->size; i++) {
		table->subtables[i].maxKeys <<= 2;
	    }
	    mem = (DdNodePtr *) ALLOC(DdNode,DD_MEM_CHUNK + 1);
	}
	if (mem == NULL) {
	    /* Out of luck. Call the default handler to do
	    ** whatever it specifies for a failed malloc.  If this
	    ** handler returns, then set error code, print
	    ** warning, and return. */
	    (*MMoutOfMemory)(sizeof(DdNode)*(DD_MEM_CHUNK + 1));
	    table->errorCode = CUDD_MEMORY_OUT;
#ifdef DD_VERBOSE
	    (void) fprintf(table->err,
			   "cuddDynamicAllocNode: out of memory");
	    (void) fprintf(table->err,"Memory in use = %ld\n",
			   table->memused);
#endif
	    return(NULL);
	} else {	/* successful allocation; slice memory */
	    unsigned long offset;
	    table->memused += (DD_MEM_CHUNK + 1) * sizeof(DdNode);
	    mem[0] = (DdNode *) table->memoryList;
	    table->memoryList = mem;

	    /* Here we rely on the fact that the size of a DdNode is a
	    ** power of 2 and a multiple of the size of a pointer.
	    ** If we align one node, all the others will be aligned
	    ** as well. */
	    offset = (unsigned long) mem & (sizeof(DdNode) - 1);
	    mem += (sizeof(DdNode) - offset) / sizeof(DdNodePtr);
#ifdef DD_DEBUG
	    assert(((unsigned long) mem & (sizeof(DdNode) - 1)) == 0);
#endif
	    list = (DdNode *) mem;

	    i = 1;
	    do {
		list[i - 1].next = &list[i];
	    } while (++i < DD_MEM_CHUNK);

	    list[DD_MEM_CHUNK - 1].next = NULL;

	    table->nextFree = &list[0];
	}
    } /* if free list empty */

    node = table->nextFree;
    table->nextFree = node->next;
    return (node);

} /* end of cuddDynamicAllocNode */


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

  Synopsis    [Implementation of Rudell's sifting algorithm.]

  Description [Implementation of Rudell's sifting algorithm.
  Assumes that no dead nodes are present.
    <ol>
    <li> Order all the variables according to the number of entries
    in each unique table.
    <li> Sift the variable up and down, remembering each time the
    total size of the DD heap.
    <li> Select the best permutation.
    <li> Repeat 3 and 4 for all variables.
    </ol>
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

******************************************************************************/
int
cuddSifting(
  DdManager * table,
  int  lower,
  int  upper)
{
    int	i;
    int	*var;
    int	size;
    int	x;
    int	result;
#ifdef DD_STATS
    int	previousSize;
#endif

    size = table->size;

    /* Find order in which to sift variables. */
    var = NULL;
    entry = ALLOC(int,size);
    if (entry == NULL) {
	table->errorCode = CUDD_MEMORY_OUT;
	goto cuddSiftingOutOfMem;
    }
    var = ALLOC(int,size);
    if (var == NULL) {
	table->errorCode = CUDD_MEMORY_OUT;
	goto cuddSiftingOutOfMem;
    }

    for (i = 0; i < size; i++) {
	x = table->perm[i];
	entry[i] = table->subtables[x].keys;
	var[i] = i;
    }

    qsort((void *)var,size,sizeof(int),(int (*)(const void *, const void *))ddUniqueCompare);

    /* Now sift. */
    for (i = 0; i < ddMin(table->siftMaxVar,size); i++) {
	if (ddTotalNumberSwapping >= table->siftMaxSwap)
	    break;
	x = table->perm[var[i]];
	
	if (x < lower || x > upper || table->subtables[x].bindVar == 1) 
	    continue;
#ifdef DD_STATS
	previousSize = table->keys - table->isolated;
#endif
	result = ddSiftingAux(table, x, lower, upper);
	if (!result) goto cuddSiftingOutOfMem;
#ifdef DD_STATS
	if (table->keys < (unsigned) previousSize + table->isolated) {
	    (void) fprintf(table->out,"-");
	} else if (table->keys > (unsigned) previousSize + table->isolated) {