cuddexact.c

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

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

  Synopsis    [Reorders variables according to a given permutation.]

  Description [Reorders variables according to a given permutation.
  The i-th permutation array contains the index of the variable that
  should be brought to the i-th level. ddShuffle assumes that no
  dead nodes are present and that the interaction matrix is properly
  initialized.  The reordering is achieved by a series of upward sifts.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
static int
ddShuffle(
  DdManager * table,
  DdHalfWord * permutation,
  int  lower,
  int  upper)
{
    DdHalfWord	index;
    int		level;
    int		position;
    int		numvars;
    int		result;
#ifdef DD_STATS
    long	localTime;
    int		initialSize;
#ifdef DD_VERBOSE
    int		finalSize;
#endif
    int		previousSize;
#endif

#ifdef DD_STATS
    localTime = util_cpu_time();
    initialSize = table->keys - table->isolated;
#endif

    numvars = table->size;

#if 0
    (void) fprintf(table->out,"%d:", ddTotalShuffles);
    for (level = 0; level < numvars; level++) {
	(void) fprintf(table->out," %d", table->invperm[level]);
    }
    (void) fprintf(table->out,"\n");
#endif

    for (level = 0; level <= upper - lower; level++) {
	index = permutation[level];
	position = table->perm[index];
#ifdef DD_STATS
	previousSize = table->keys - table->isolated;
#endif
	result = ddSiftUp(table,position,level+lower);
	if (!result) return(0);
    }

#ifdef DD_STATS
    ddTotalShuffles++;
#ifdef DD_VERBOSE
    finalSize = table->keys - table->isolated;
    if (finalSize < initialSize) {
	(void) fprintf(table->out,"-");
    } else if (finalSize > initialSize) {
	(void) fprintf(table->out,"+");
    } else {
	(void) fprintf(table->out,"=");
    }
    if ((ddTotalShuffles & 63) == 0) (void) fprintf(table->out,"\n");
    fflush(table->out);
#endif
#endif

    return(1);

} /* end of ddShuffle */


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

  Synopsis    [Moves one variable up.]

  Description [Takes a variable from position x and sifts it up to
  position xLow;  xLow should be less than or equal to x.
  Returns 1 if successful; 0 otherwise]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
ddSiftUp(
  DdManager * table,
  int  x,
  int  xLow)
{
    int        y;
    int        size;

    y = cuddNextLow(table,x);
    while (y >= xLow) {
	size = cuddSwapInPlace(table,y,x);
	if (size == 0) {
	    return(0);
	}
	x = y;
	y = cuddNextLow(table,x);
    }
    return(1);

} /* end of ddSiftUp */


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

  Synopsis    [Updates the upper bound and saves the best order seen so far.]

  Description [Updates the upper bound and saves the best order seen so far.
  Returns the current value of the upper bound.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
updateUB(
  DdManager * table,
  int  oldBound,
  DdHalfWord * bestOrder,
  int  lower,
  int  upper)
{
    int i;
    int newBound = table->keys - table->isolated;

    if (newBound < oldBound) {
#ifdef DD_STATS
	(void) fprintf(table->out,"New upper bound = %d\n", newBound);
	fflush(table->out);
#endif
	for (i = lower; i <= upper; i++)
	    bestOrder[i-lower] = (DdHalfWord) table->invperm[i];
	return(newBound);
    } else {
	return(oldBound);
    }

} /* end of updateUB */


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

  Synopsis    [Counts the number of roots.]

  Description [Counts the number of roots at the levels between lower and
  upper.  The computation is based on breadth-first search.
  A node is a root if it is not reachable from any previously visited node.
  (All the nodes at level lower are therefore considered roots.)
  The visited flag uses the LSB of the next pointer.  Returns the root
  count. The roots that are constant nodes are always ignored.]

  SideEffects [None]

  SeeAlso     [ddClearGlobal]

******************************************************************************/
static int
ddCountRoots(
  DdManager * table,
  int  lower,
  int  upper)
{
    int i,j;
    DdNode *f;
    DdNodePtr *nodelist;
    DdNode *sentinel = &(table->sentinel);
    int slots;
    int roots = 0;
    int maxlevel = lower;

    for (i = lower; i <= upper; i++) {
	nodelist = table->subtables[i].nodelist;
	slots = table->subtables[i].slots;
	for (j = 0; j < slots; j++) {
	    f = nodelist[j];
	    while (f != sentinel) {
		/* A node is a root of the DAG if it cannot be
		** reached by nodes above it. If a node was never
		** reached during the previous depth-first searches,
		** then it is a root, and we start a new depth-first
		** search from it.
		*/
		if (!Cudd_IsComplement(f->next)) {
		    if (f != table->vars[f->index]) {
			roots++;
		    }
		}
		if (!Cudd_IsConstant(cuddT(f))) {
		    cuddT(f)->next = Cudd_Complement(cuddT(f)->next);
		    if (table->perm[cuddT(f)->index] > maxlevel)
			maxlevel = table->perm[cuddT(f)->index];
		}
		if (!Cudd_IsConstant(cuddE(f))) {
		    Cudd_Regular(cuddE(f))->next =
			Cudd_Complement(Cudd_Regular(cuddE(f))->next);
		    if (table->perm[Cudd_Regular(cuddE(f))->index] > maxlevel)
			maxlevel = table->perm[Cudd_Regular(cuddE(f))->index];
		}
		f = Cudd_Regular(f->next);
	    }
	}
    }
    ddClearGlobal(table, lower, maxlevel);

    return(roots);

} /* end of ddCountRoots */


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

  Synopsis    [Scans the DD and clears the LSB of the next pointers.]

  Description [Scans the DD and clears the LSB of the next pointers.
  The LSB of the next pointers are used as markers to tell whether a
  node was reached. Once the roots are counted, these flags are
  reset.]

  SideEffects [None]

  SeeAlso     [ddCountRoots]

******************************************************************************/
static void
ddClearGlobal(
  DdManager * table,
  int  lower,
  int  maxlevel)
{
    int i,j;
    DdNode *f;
    DdNodePtr *nodelist;
    DdNode *sentinel = &(table->sentinel);
    int slots;

    for (i = lower; i <= maxlevel; i++) {
	nodelist = table->subtables[i].nodelist;
	slots = table->subtables[i].slots;
	for (j = 0; j < slots; j++) {
	    f = nodelist[j];
	    while (f != sentinel) {
		f->next = Cudd_Regular(f->next);
		f = f->next;
	    }
	}
    }

} /* end of ddClearGlobal */


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

  Synopsis    [Computes a lower bound on the size of a BDD.]

  Description [Computes a lower bound on the size of a BDD from the
  following factors:
  <ul>
  <li> size of the lower part of it;
  <li> size of the part of the upper part not subjected to reordering;
  <li> number of roots in the part of the BDD subjected to reordering;
  <li> variable in the support of the roots in the upper part of the
       BDD subjected to reordering.
  <ul/>]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
computeLB(
  DdManager * table		/* manager */,
  DdHalfWord * order		/* optimal order for the subset */,
  int  roots			/* roots between lower and upper */,
  int  cost			/* minimum cost for the subset */,
  int  lower			/* lower level to be reordered */,
  int  upper			/* upper level to be reordered */,
  int  level			/* offset for the current top bottom var */
  )
{
    int i;
    int lb = cost;
    int lb1 = 0;
    int lb2;
    int support;
    DdHalfWord ref;

    /* The levels not involved in reordering are not going to change.
    ** Add their sizes to the lower bound.
    */
    for (i = 0; i < lower; i++) {
	lb += getLevelKeys(table,i);
    }
    /* If a variable is in the support, then there is going
    ** to be at least one node labeled by that variable.
    */
    for (i = lower; i <= lower+level; i++) {
	support = table->subtables[i].keys > 1 ||
	    table->vars[order[i-lower]]->ref > 1;
	lb1 += support;
    }

    /* Estimate the number of nodes required to connect the roots to
    ** the nodes in the bottom part. */
    if (lower+level+1 < table->size) {
	if (lower+level < upper)
	    ref = table->vars[order[level+1]]->ref;
	else
	    ref = table->vars[table->invperm[upper+1]]->ref;
	lb2 = table->subtables[lower+level+1].keys -
	    (ref > (DdHalfWord) 1) - roots;
    } else {
	lb2 = 0;
    }

    lb += lb1 > lb2 ? lb1 : lb2;

    return(lb);

} /* end of computeLB */


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

  Synopsis    [Updates entry for a subset.]

  Description [Updates entry for a subset. Finds the subset, if it exists.
  If the new order for the subset has lower cost, or if the subset did not
  exist, it stores the new order and cost. Returns the number of subsets
  currently in the table.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
updateEntry(
  DdManager * table,
  DdHalfWord * order,
  int  level,
  int  cost,
  DdHalfWord ** orders,
  int * costs,
  int  subsets,
  char * mask,
  int  lower,
  int  upper)
{
    int i, j;
    int size = upper - lower + 1;

    /* Build a mask that says what variables are in this subset. */
    for (i = lower; i <= upper; i++)
	mask[table->invperm[i]] = 0;
    for (i = level; i < size; i++)
	mask[order[i]] = 1;

    /* Check each subset until a match is found or all subsets are examined. */
    for (i = 0; i < subsets; i++) {
	DdHalfWord *subset = orders[i];
	for (j = level; j < size; j++) {
	    if (mask[subset[j]] == 0)
		break;
	}
	if (j == size)		/* no mismatches: success */
	    break;
    }
    if (i == subsets || cost < costs[i]) {		/* add or replace */
	for (j = 0; j < size; j++)
	    orders[i][j] = order[j];
	costs[i] = cost;
	subsets += (i == subsets);
    }
    return(subsets);

} /* end of updateEntry */


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

  Synopsis    [Pushes a variable in the order down to position "level."]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static void
pushDown(
  DdHalfWord * order,
  int  j,
  int  level)
{
    int i;
    DdHalfWord tmp;

    tmp = order[j];
    for (i = j; i < level; i++) {
	order[i] = order[i+1];
    }
    order[level] = tmp;
    return;

} /* end of pushDown */


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

  Synopsis    [Gathers symmetry information.]

  Description [Translates the symmetry information stored in the next
  field of each subtable from level to indices. This procedure is called
  immediately after symmetric sifting, so that the next fields are correct.
  By translating this informaton in terms of indices, we make it independent
  of subsequent reorderings. The format used is that of the next fields:
  a circular list where each variable points to the next variable in the
  same symmetry group. Only the entries between lower and upper are
  considered.  The procedure returns a pointer to an array
  holding the symmetry information if successful; NULL otherwise.]

  SideEffects [None]

  SeeAlso     [checkSymmInfo]

******************************************************************************/
static DdHalfWord *
initSymmInfo(
  DdManager * table,
  int  lower,
  int  upper)
{
    int level, index, next, nextindex;
    DdHalfWord *symmInfo;

    symmInfo =  ALLOC(DdHalfWord, table->size);
    if (symmInfo == NULL) return(NULL);

    for (level = lower; level <= upper; level++) {
	index = table->invperm[level];
	next =  table->subtables[level].next;
	nextindex = table->invperm[next];
	symmInfo[index] = nextindex;
    }
    return(symmInfo);

} /* end of initSymmInfo */


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

  Synopsis    [Check symmetry condition.]

  Description [Returns 1 if a variable is the one with the highest index
  among those belonging to a symmetry group that are in the top part of
  the BDD.  The top part is given by level.]

  SideEffects [None]

  SeeAlso     [initSymmInfo]

******************************************************************************/
static int
checkSymmInfo(
  DdManager * table,
  DdHalfWord * symmInfo,
  int  index,
  int  level)
{
    int i;

    i = symmInfo[index];
    while (i != index) {
	if (index < i && table->perm[i] <= level)
	    return(0);
	i = symmInfo[i];
    }
    return(1);

} /* end of checkSymmInfo */