cuddsubsetsp.c

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

  struct AssortedInfo * info /* assorted information structure */,
  st_table * subsetNodeTable /* table storing computed results */)
{
    DdNode *N, *Nv, *Nnv;
    DdNode *ThenBranch, *ElseBranch, *childBranch;
    DdNode *child, *regChild, *regNnv, *regNv;
    NodeDist_t *nodeStatNv, *nodeStat, *nodeStatNnv;
    DdNode *neW, *topv, *regNew;
    char *entry;
    unsigned int topid;
    unsigned int childPathLength, oddLen, evenLen, NnvPathLength, NvPathLength;
    unsigned int NvBotDist, NnvBotDist;
    int tiebreakChild;
    int  processingDone, thenDone, elseDone;


#ifdef DD_DEBUG
    numCalls++;
#endif
    if (Cudd_IsConstant(node))
	return(node);

    N = Cudd_Regular(node);
    /* Find node in table. */
    if (!st_lookup(pathTable, (char *)N, (char **)&nodeStat)) {
	(void) fprintf(dd->err, "Something wrong, node must be in table \n");
	dd->errorCode = CUDD_INTERNAL_ERROR;
	return(NULL);
    }
    /* If the node in the table has been visited, then return the corresponding
    ** Dd. Since a node can become a subset of itself, its
    ** complement (that is te same node reached by a different parity) will
    ** become a superset of the original node and result in some minterms
    ** that were not in the original set. Hence two different results are
    ** maintained, corresponding to the odd and even parities.
    */

    /* If this node is reached with an odd parity, get odd parity results. */
    if (Cudd_IsComplement(node)) {
	if  (nodeStat->compResult != NULL) {
#ifdef DD_DEBUG
	    hits++;
#endif
	    return(nodeStat->compResult);
	}
    } else {
	/* if this node is reached with an even parity, get even parity
	 * results
	 */
	if (nodeStat->regResult != NULL) {
#ifdef DD_DEBUG
	    hits++;
#endif
	    return(nodeStat->regResult);
	}
    }


    /* get children */
    Nv = Cudd_T(N);
    Nnv = Cudd_E(N);

    Nv = Cudd_NotCond(Nv, Cudd_IsComplement(node));
    Nnv = Cudd_NotCond(Nnv, Cudd_IsComplement(node));

    /* no child processed */
    processingDone = 0;
    /* then child not processed */
    thenDone = 0;
    ThenBranch = NULL;
    /* else child not processed */
    elseDone = 0;
    ElseBranch = NULL;
    /* if then child constant, branch is the child */
    if (Cudd_IsConstant(Nv)) {
	/*shortest path found */
	if ((Nv == DD_ONE(dd)) && (info->findShortestPath)) {
	    info->findShortestPath = 0;
	}

	ThenBranch = Nv;
	cuddRef(ThenBranch);
	if (ThenBranch == NULL) {
	    return(NULL);
	}

	thenDone++;
	processingDone++;
	NvBotDist = MAXSHORTINT;
    } else {
	/* Derive regular child for table lookup. */
	regNv = Cudd_Regular(Nv);
	/* Get node data for shortest path length. */
	if (!st_lookup(pathTable, (char *)regNv, (char **)&nodeStatNv) ) {
	    (void) fprintf(dd->err, "Something wrong, node must be in table\n");
	    dd->errorCode = CUDD_INTERNAL_ERROR;
	    return(NULL);
	}
	/* Derive shortest path length for child. */
	if ((nodeStatNv->oddTopDist != MAXSHORTINT) &&
	    (nodeStatNv->oddBotDist != MAXSHORTINT)) {
	    oddLen = (nodeStatNv->oddTopDist + nodeStatNv->oddBotDist);
	} else {
	    oddLen = MAXSHORTINT;
	}

	if ((nodeStatNv->evenTopDist != MAXSHORTINT) &&
	    (nodeStatNv->evenBotDist != MAXSHORTINT)) {
	    evenLen = (nodeStatNv->evenTopDist +nodeStatNv->evenBotDist);
	} else {
	    evenLen = MAXSHORTINT;
	}

	NvPathLength = (oddLen <= evenLen) ? oddLen : evenLen;
	NvBotDist = (oddLen <= evenLen) ? nodeStatNv->oddBotDist:
	                                           nodeStatNv->evenBotDist;
    }
    /* if else child constant, branch is the child */
    if (Cudd_IsConstant(Nnv)) {
	/*shortest path found */
	if ((Nnv == DD_ONE(dd)) && (info->findShortestPath)) {
	    info->findShortestPath = 0;
	}

	ElseBranch = Nnv;
	cuddRef(ElseBranch);
	if (ElseBranch == NULL) {
	    return(NULL);
	}

	elseDone++;
	processingDone++;
	NnvBotDist = MAXSHORTINT;
    } else {
	/* Derive regular child for table lookup. */
	regNnv = Cudd_Regular(Nnv);
	/* Get node data for shortest path length. */
	if (!st_lookup(pathTable, (char *)regNnv, (char **)&nodeStatNnv) ) {
	    (void) fprintf(dd->err, "Something wrong, node must be in table\n");
	    dd->errorCode = CUDD_INTERNAL_ERROR;
	    return(NULL);
	}
	/* Derive shortest path length for child. */
	if ((nodeStatNnv->oddTopDist != MAXSHORTINT) &&
	    (nodeStatNnv->oddBotDist != MAXSHORTINT)) {
	    oddLen = (nodeStatNnv->oddTopDist + nodeStatNnv->oddBotDist);
	} else {
	    oddLen = MAXSHORTINT;
	}

	if ((nodeStatNnv->evenTopDist != MAXSHORTINT) &&
	    (nodeStatNnv->evenBotDist != MAXSHORTINT)) {
	    evenLen = (nodeStatNnv->evenTopDist +nodeStatNnv->evenBotDist);
	} else {
	    evenLen = MAXSHORTINT;
	}

	NnvPathLength = (oddLen <= evenLen) ? oddLen : evenLen;
	NnvBotDist = (oddLen <= evenLen) ? nodeStatNnv->oddBotDist :
	                                           nodeStatNnv->evenBotDist;
    }

    tiebreakChild = (NvBotDist <= NnvBotDist) ? 1 : 0;
    /* while both children not processed */
    while (processingDone != 2) {
	if (!processingDone) {
	    /* if no child processed */
	    /* pick the child with shortest path length and record which one
	     * picked
	     */
	    if ((NvPathLength < NnvPathLength) ||
		((NvPathLength == NnvPathLength) && (tiebreakChild == 1))) {
		child = Nv;
		regChild = regNv;
		thenDone = 1;
		childPathLength = NvPathLength;
	    } else {
		child = Nnv;
		regChild = regNnv;
		elseDone = 1;
		childPathLength = NnvPathLength;
	    } /* then path length less than else path length */
	} else {
	    /* if one child processed, process the other */
	    if (thenDone) {
		child = Nnv;
		regChild = regNnv;
		elseDone = 1;
		childPathLength = NnvPathLength;
	    } else {
		child = Nv;
		regChild = regNv;
		thenDone = 1;
		childPathLength = NvPathLength;
	    } /* end of else pick the Then child if ELSE child processed */
	} /* end of else one child has been processed */

	/* ignore (replace with constant 0) all nodes which lie on paths larger
	 * than the maximum length of the path required
	 */
	if (childPathLength > info->maxpath) {
	    /* record nodes visited */
	    childBranch = zero;
	} else {
	    if (childPathLength < info->maxpath) {
		if (info->findShortestPath) {
		    info->findShortestPath = 0;
		}
		childBranch = BuildSubsetBdd(dd, pathTable, child, info,
					     subsetNodeTable);

	    } else { /* Case: path length of node = maxpath */
		/* If the node labeled with maxpath is found in the
		** maxpathTable, use it to build the subset BDD.  */
		if (st_lookup(info->maxpathTable, (char *)regChild,
			      (char **)&entry)) {
		    /* When a node that is already been chosen is hit,
		    ** the quest for a complete path is over.  */
		    if (info->findShortestPath) {
			info->findShortestPath = 0;
		    }
		    childBranch = BuildSubsetBdd(dd, pathTable, child, info,
						 subsetNodeTable);
		} else {
		    /* If node is not found in the maxpathTable and
		    ** the threshold has been reached, then if the
		    ** path needs to be completed, continue. Else
		    ** replace the node with a zero.  */
		    if (info->thresholdReached <= 0) {
			if (info->findShortestPath) {
			    if (st_insert(info->maxpathTable, (char *)regChild,
					  (char *)NIL(char)) == ST_OUT_OF_MEM) {
				memOut = 1;
				(void) fprintf(dd->err, "OUT of memory\n");
				info->thresholdReached = 0;
				childBranch = zero;
			    } else {
				info->thresholdReached--;
				childBranch = BuildSubsetBdd(dd, pathTable,
						    child, info,subsetNodeTable);
			    }
			} else { /* not find shortest path, we dont need this
				    node */
			    childBranch = zero;
			}
		    } else { /* Threshold hasn't been reached,
			     ** need the node. */
			if (st_insert(info->maxpathTable, (char *)regChild,
				      (char *)NIL(char)) == ST_OUT_OF_MEM) {
			    memOut = 1;
			    (void) fprintf(dd->err, "OUT of memory\n");
			    info->thresholdReached = 0;
			    childBranch = zero;
			} else {
			    info->thresholdReached--;
			    if (info->thresholdReached <= 0) {
				info->findShortestPath = 1;
			    }
			    childBranch = BuildSubsetBdd(dd, pathTable,
						 child, info, subsetNodeTable);

			} /* end of st_insert successful */
		    } /* end of threshold hasnt been reached yet */
		} /* end of else node not found in maxpath table */
	    } /* end of if (path length of node = maxpath) */
	} /* end if !(childPathLength > maxpath) */
	if (childBranch == NULL) {
	    /* deref other stuff incase reordering has taken place */
	    if (ThenBranch != NULL) {
		Cudd_RecursiveDeref(dd, ThenBranch);
		ThenBranch = NULL;
	    }
	    if (ElseBranch != NULL) {
		Cudd_RecursiveDeref(dd, ElseBranch);
		ElseBranch = NULL;
	    }
	    return(NULL);
	}

	cuddRef(childBranch);

	if (child == Nv) {
	    ThenBranch = childBranch;
	} else {
	    ElseBranch = childBranch;
	}
	processingDone++;

    } /*end of while processing Nv, Nnv */  	

    info->findShortestPath = 0;
    topid = Cudd_NodeReadIndex(N);
    topv = Cudd_ReadVars(dd, topid);
    cuddRef(topv);
    neW = cuddBddIteRecur(dd, topv, ThenBranch, ElseBranch);
    if (neW != NULL) {
	cuddRef(neW);
    }
    Cudd_RecursiveDeref(dd, topv);
    Cudd_RecursiveDeref(dd, ThenBranch);
    Cudd_RecursiveDeref(dd, ElseBranch);


    /* Hard Limit of threshold has been imposed */
    if (subsetNodeTable != NIL(st_table)) {
	/* check if a new node is created */
	regNew = Cudd_Regular(neW);
	/* subset node table keeps all new nodes that have been created to keep
	 * a running count of how many nodes have been built in the subset.
	 */
	if (!st_lookup(subsetNodeTable, (char *)regNew, (char **)&entry)) {
	    if (!Cudd_IsConstant(regNew)) {
		if (st_insert(subsetNodeTable, (char *)regNew,
			      (char *)NULL) == ST_OUT_OF_MEM) {
		    (void) fprintf(dd->err, "Out of memory\n");
		    return (NULL);
		}
		if (st_count(subsetNodeTable) > info->threshold) {
		    info->thresholdReached = 0;
		}
	    }
	}
    }


    if (neW == NULL) {
	return(NULL);
    } else {
	/*store computed result in regular form*/
	if (Cudd_IsComplement(node)) {
	    nodeStat->compResult = neW;
	    cuddRef(nodeStat->compResult);
	    /* if the new node is the same as the corresponding node in the
	     * original bdd then its complement need not be computed as it
	     * cannot be larger than the node itself
	     */
	    if (neW == node) {
#ifdef DD_DEBUG
		thishit++;
#endif
		/* if a result for the node has already been computed, then
		 * it can only be smaller than teh node itself. hence store
		 * the node result in order not to break recombination
		 */
		if (nodeStat->regResult != NULL) {
		    Cudd_RecursiveDeref(dd, nodeStat->regResult);
		}
		nodeStat->regResult = Cudd_Not(neW);
		cuddRef(nodeStat->regResult);
	    }

	} else {
	    nodeStat->regResult = neW;
	    cuddRef(nodeStat->regResult);
	    if (neW == node) {
#ifdef DD_DEBUG
		thishit++;
#endif
		if (nodeStat->compResult != NULL) {
		    Cudd_RecursiveDeref(dd, nodeStat->compResult);
		}
		nodeStat->compResult = Cudd_Not(neW);
		cuddRef(nodeStat->compResult);
	    }
	} 

	cuddDeref(neW);
	return(neW);
    } /* end of else i.e. Subset != NULL */
} /* end of BuildSubsetBdd */


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

  Synopsis     [Procedure to free te result dds stored in the NodeDist pages.]

  Description [None]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static enum st_retval
stPathTableDdFree(
  char * key,
  char * value,
  char * arg)
{
    NodeDist_t *nodeStat;
    DdManager *dd;

    nodeStat = (NodeDist_t *)value;
    dd = (DdManager *)arg;
    if (nodeStat->regResult != NULL) {
	Cudd_RecursiveDeref(dd, nodeStat->regResult);
    }
    if (nodeStat->compResult != NULL) {
	Cudd_RecursiveDeref(dd, nodeStat->compResult);
    }
    return(ST_CONTINUE);

} /* end of stPathTableFree */