A leaf that is a primary input, latch, or combinational node, is treated as a "free" input (i.e. can assume any value in its domain). A leaf that is a pseudo input can assume only those values for which it was specified.
The leaves table maps nodes (Ntk_Node_t*) to integers. If the value corresponding to a leaf is NTM_UNUSED, then the MVF for the leaf is built as described above. However, the value can be specified as the index of some value in the domain of the variable of the leaf. For example, if leaf node x can take values (RED, GREEN, BLUE), then the value 1 refers to GREEN. In this case, the MVF built for x is simply the constant MVF representing GREEN. This feature can be used to evaluate the MVFs of the roots on a minterm, or partial minterm, over the leaves.
This function also takes the MDD careSet as an input. If this argument is
NULL, then it is ignored. However, if it is not NULL, then all intermediate
and final MDDs constructed are minimized with respect to the careSet. Thus,
the MVFs returned by the function may take an arbitrary value outside of the
careSet. This can be useful to keep the MDDs small.]
Comment [We create a table mapping nodes to Mvf_Function_t's (for nodes for
which Mvf_Function's have already been built); Call NodeBuildMvfRecursively
on the roots. Free MVF's at internal nodes ASAP, so no excessive storage.]
SideEffects []
******************************************************************************/
array_t *
Ntm_NetworkBuildMvfs(
Ntk_Network_t * network,
array_t * roots,
st_table * leaves,
mdd_t *careSet)
{
int i;
st_generator *stGen;
Mvf_Function_t *mvf;
Ntk_Node_t *node;
st_table *nodeToMvfTable;
Mvf_Function_t *tmpMvf;
int numRoots = array_n(roots);
array_t *result = array_alloc(Mvf_Function_t *, numRoots);
mdd_manager *mddMgr = Ntk_NetworkReadMddManager(network);
/*
* Before initializing the reference counts, verify that the leaves form a
* support set for the roots.
*/
if (!Ntk_NetworkTestLeavesCoverSupportOfRoots(network, roots, leaves)) {
(void)fprintf(vis_stderr,"%s",error_string());
fflush(vis_stderr);
fail("Leaves do not cover support of roots");
}
/*
* Each node in the region defined by the roots and leaves is assigned a
* reference count equaling the number of fanouts within the region. As a
* special case, the roots are initialized to MAX_INT.
*/
RegionInitializeReferenceCounts(roots, leaves);
/*
* For each root, compute its MVF and store a duplicate copy of it in the
* result array. The nodeToMvfTable is used to keep track of intermediate
* computations. Intermediate MVFs are freed as soon as possible by using
* the reference count mechanism.
*/
nodeToMvfTable = st_init_table(st_ptrcmp, st_ptrhash);
for (i = 0; i < numRoots; i++) {
Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
tmpMvf = NodeBuildMvfRecursively(root, leaves,
nodeToMvfTable, mddMgr,
careSet);
mvf = Mvf_FunctionDuplicate(tmpMvf);
array_insert(Mvf_Function_t *, result, i, mvf);
}
/*
* Because of the use of reference counting, the only nodes left in
* nodeToMvfTable should be the roots.
*/
assert(TableTestIsContainedInArray(nodeToMvfTable, roots));
/*
* Free the remaining MVFs (corresponding to the roots) from the
* nodeToMvfTable.
*/
st_foreach_item(nodeToMvfTable, stGen, &node, &mvf) {
Mvf_FunctionFree(mvf);
}
st_free_table(nodeToMvfTable);
return result;
}
/*---------------------------------------------------------------------------*/
/* Definition of internal functions */
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
/* Definition of static functions */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************
Synopsis [Builds MVF for a node, recursively in terms of fanins.]
Description [Recursively builds Mvf_Functions_t's. Base cases - input nodes,
latch nodes, constant nodes, pseudo inputs, and leaf nodes. Fail if a
combinational input is reached that is not in leaves. In the case that the
node is combinational, and in the leaves, we treat it as an input. When
it's a pseudo input, we treat it as taking only values designated in table.]
SideEffects []
SeeAlso [NodeBuildInputMvf,NodeBuildPseudoInputMvf,NodeBuildInternalMvf]
******************************************************************************/
static Mvf_Function_t *
NodeBuildMvfRecursively(
Ntk_Node_t * node,
st_table * leaves,
st_table * nodeToMvfTable,
mdd_manager *mddMgr,
mdd_t *careSet)
{
Mvf_Function_t *mvf = NodeReadMvf(node, nodeToMvfTable);
/* If the MVF for this node has already been computed, then just return it. */
if (mvf != NIL(Mvf_Function_t)) {
return mvf;
}
if (Ntk_NodeTestIsConstant(node)) {
/* Doesn't matter if constant is a leaf or not. */
mvf = NodeBuildConstantMvf(node, NTM_UNUSED, mddMgr);
}
else {
int constValue;
if (st_lookup_int(leaves, (char *) node, &constValue)) {
if (constValue == NTM_UNUSED) {
/* Node is a leaf. */
if ((Ntk_NodeTestIsPrimaryInput(node)) ||
(Ntk_NodeTestIsLatch(node)) ||
(Ntk_NodeTestIsCombinational(node))) {
/* Node can assume any value. */
mvf = NodeBuildInputMvf(node, mddMgr);
}
else if (Ntk_NodeTestIsPseudoInput(node)) {
/* Node may assume only a subset of possible values. */
mvf = NodeBuildPseudoInputMvfNew(node, mddMgr);
}
else {
fail("Encountered unknown type in MVF recursion\n");
}
}
else {
/* treat the leaf node as being a constant taking the value constValue */
mvf = NodeBuildConstantMvf(node, constValue, mddMgr);
}
}
else {
/* Node is not a leaf. If it is a combinational input, then fail. */
if (Ntk_NodeTestIsCombInput(node)) {
fail("Encountered combinational input not in leaves table\n");
}
else {
mvf = NodeBuildInternalMvf(node, leaves, nodeToMvfTable, mddMgr,
careSet);
}
}
}
/* Minimize mvf wrt careSet, if careSet is not NULL. */
if (careSet != NIL(mdd_t)) {
Mvf_Function_t *tempMvf = mvf;
mvf = Mvf_FunctionMinimize(tempMvf, careSet);
Mvf_FunctionFree(tempMvf);
}
NodeSetMvf(node, nodeToMvfTable, mvf);
return mvf;
}
/**Function********************************************************************
Synopsis [Builds MVF for a node that is treated as a free input.]
SideEffects []
******************************************************************************/
static Mvf_Function_t *
NodeBuildInputMvf(
Ntk_Node_t * node,
mdd_manager *mddMgr)
{
int mddId = Ntk_NodeReadMddId(node);
assert(mddId != NTK_UNASSIGNED_MDD_ID);
return Mvf_FunctionCreateFromVariable(mddMgr, mddId);
}
/**Function********************************************************************
Synopsis [Builds MVF for a node that is a pseudo input.]
Description [Builds MVF for a node that is a pseudo input. This node has a
single output and no inputs. Its table has several row entries. We build an
MVF whose components correspond exactly to possible table outputs.]
SideEffects []
Comment [Although pseudo inputs, constants, and internal nodes all have
tables, a single procedure cannot be used to build their MVF. A pseudo
input MVF is built in terms of its mddId, whereas a constant or internal is
not. A constant or pseudo input doesn't have any inputs, whereas an
internal does.]
SeeAlso [Tbl_TableBuildMvfForNonDetConstant]
******************************************************************************/
static Mvf_Function_t *
NodeBuildPseudoInputMvfNew(
Ntk_Node_t * node,
mdd_manager * mddMgr)
{
mdd_t *vMdd, *tMdd, *rMdd;
int lIndex, needProcess, i;
Mvf_Function_t *mvf;
int columnIndex = Ntk_NodeReadOutputIndex(node);
Tbl_Table_t *table = Ntk_NodeReadTable(node);
int mddId = Ntk_NodeReadMddId(node);
assert(mddId != NTK_UNASSIGNED_MDD_ID);
mvf = Tbl_TableBuildNonDetConstantMvf(table, columnIndex, mddId, mddMgr);
rMdd = mdd_zero(mddMgr);
needProcess = 0;
lIndex = 0;
for(i=0; i
Command options:
]
SideEffects []
******************************************************************************/
static int
CommandNtmTest(
Hrc_Manager_t ** hmgr,
int argc,
char ** argv)
{
int c;
Ntk_Node_t *node;
lsGen gen;
array_t *result; /* array of Mvf_Function_t* */
array_t *roots;
st_table *leaves;
boolean verbose = FALSE; /* default */
Ntk_Network_t *network = Ntk_HrcManagerReadCurrentNetwork(*hmgr);
/*
* Parse the command line.
*/
util_getopt_reset();
while ((c = util_getopt(argc, argv, "vh")) != EOF) {
switch (c) {
case 'v':
verbose = 1;
break;
case 'h':
goto usage;
default:
goto usage;
}
}
if (network == NIL(Ntk_Network_t)) {
return 1;
}
if (Ord_NetworkTestAreVariablesOrdered(network, Ord_InputAndLatch_c) == FALSE) {
(void) fprintf(vis_stderr, "The MDD variables have not been ordered. ");
(void) fprintf(vis_stderr, "Use static_order.\n");
return 1;
}
roots = array_alloc(Ntk_Node_t *, 0);
Ntk_NetworkForEachCombOutput(network, gen, node) {
array_insert_last(Ntk_Node_t *, roots, node);
}
leaves = st_init_table(st_ptrcmp, st_ptrhash);
Ntk_NetworkForEachCombInput(network, gen, node) {
st_insert(leaves, (char *) node, (char *) NTM_UNUSED);
}
result = Ntm_NetworkBuildMvfs(network, roots, leaves, NIL(mdd_t));
if (verbose) {
MvfSanityCheck(roots, result);
}
array_free(roots);
st_free_table(leaves);
/*
* Free the array of MVFs.
*/
Mvf_FunctionArrayFree(result);
return 0;
usage:
(void) fprintf(vis_stderr, "usage: _ntm_test [-h] [-v]\n");
(void) fprintf(vis_stderr, " -h print the command usage\n");
(void) fprintf(vis_stderr, " -v verbose\n");
return 1; /* error exit */
}
/**Function********************************************************************
Synopsis [Checks that MDD sizes are meaningful.]
SideEffects []
******************************************************************************/
static void
MvfSanityCheck(
array_t *roots /* of Ntk_Node_t* */,
array_t *mvfs /* of Mvf_Function_t* */)
{
int i;
assert(array_n(roots) == array_n(mvfs));
for (i = 0; i < array_n(roots); i ++) {
int value;
mdd_t *valueMdd;
Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
Mvf_Function_t *mvf = array_fetch(Mvf_Function_t *, mvfs, i);
(void) fprintf(vis_stdout, "\nMDD stats for node %s:\n", Ntk_NodeReadName(root));
Mvf_FunctionForEachComponent(mvf, value, valueMdd) {
(void) fprintf(vis_stdout, "\tSize of MDD for value %d is %d\n", i,
mdd_size(valueMdd));
}
}
}
/**Function********************************************************************
Synopsis [Initializes the reference counts in a region.]
Description [Initializes the reference counts in the region defined by the
roots and leaves. This region includes the roots, and all nodes in the
transitive fanin of the roots up to and including the leaves. The reference
count for a node in the region is set to be the number of fanouts of that
node in the region (fanouts to leaf nodes and constant nodes are excluded).
Root nodes are set to MAXINT, so that even after some decrements, their ref
count won't fall to zero.]
SideEffects [Uses the undef field of node.]
******************************************************************************/
static void
RegionInitializeReferenceCounts(
array_t *roots,
st_table *leaves)
{
int i;
Ntk_Node_t *node;
st_generator *stGen;
st_table *regionNodes = Ntk_RegionFindNodes(roots, leaves);
st_foreach_item(regionNodes, stGen, &node, NULL) {
Ntk_Node_t *fanoutNode;
long refCount = 0;
Ntk_NodeForEachFanout(node, i, fanoutNode) {
if (st_is_member(regionNodes, (char *) fanoutNode)
&& !st_is_member(leaves, (char *) fanoutNode)
&& !Ntk_NodeTestIsConstant(fanoutNode)) {
refCount++;
}
}
Ntk_NodeSetUndef(node, (void *) refCount);
}
for(i = 0; i < array_n(roots); i++) {
node = array_fetch(Ntk_Node_t *, roots, i);
Ntk_NodeSetUndef(node, (void *) MAXINT);
}
st_free_table(regionNodes);
}
/**Function********************************************************************
Synopsis [Decrements the ref count of a node.]
Description [Decrements the ref count of a node. If the ref count becomes
zero, then remove node from nodeToMvfTable and free the MVF corresponding to
node.]
SideEffects []
******************************************************************************/
static void
NodeDecrementRefCount(
Ntk_Node_t *node,
st_table *nodeToMvfTable)
{
Mvf_Function_t *mvf;
long refCount = (long) Ntk_NodeReadUndef(node);
assert(refCount != 0);
refCount--;
if (refCount == 0) {
st_delete(nodeToMvfTable, &node, &mvf);
Mvf_FunctionFree(mvf);
}
Ntk_NodeSetUndef(node, (void *) refCount);
}
/**Function********************************************************************
Synopsis [Returns TRUE if table1 is contained in nodeArray; else FALSE.]
Description [Table1 is a hash table where the keys are nodes. NodeArray is
an array of nodes. This function returns TRUE if the set of key nodes in
table1 is contained in the set of nodes in nodeArray. It returns FALSE upon
finding the first key node in table1 that is not in nodeArray.]
SideEffects []
******************************************************************************/
static boolean
TableTestIsContainedInArray(
st_table *table1,
array_t *nodeArrary)
{
int i;
st_generator *stGen;
Ntk_Node_t *node;
Mvf_Function_t *mvf;
st_table *table2 = st_init_table(st_ptrcmp, st_ptrhash);
/* Create a hash table from the array. */
arrayForEachItem(Ntk_Node_t *, nodeArrary, i, node) {
st_insert(table2, (char *) node, NIL(char));
}
st_foreach_item(table1, stGen, &node, &mvf) {
if (!st_is_member(table2, node)) {
st_free_table(table2);
return FALSE;
}
}
st_free_table(table2);
return TRUE;
}