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 ntmaig_UNUSED, then the MvfAig 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 MvfAig built for x is simply the constant MvfAig representing This feature can be used to evaluate the MvfAigs of the roots on a minterm, or partial minterm, over the leaves.
nodeToMvfAigTable is a table mapping nodes to MvfAig_Function_t's (for nodes for
which MvfAig_Function's have already been built); Call NodeBuildMvfAigRecursively
on the roots. Free MvfAig's at internal nodes ASAP, so no excessive storage.]
SideEffects []
******************************************************************************/
array_t *
ntmaig_NetworkBuildMvfAigs(
Ntk_Network_t * network,
array_t * roots,
st_table * leaves)
{
int i;
MvfAig_Function_t *MvfAig;
st_table *nodeToMvfAigTable; /* mapes each node with its mvfAig */
int numRoots = array_n(roots);
array_t *result = array_alloc(MvfAig_Function_t *, numRoots);
mAig_Manager_t *manager = Ntk_NetworkReadMAigManager(network);
MvfAig_Function_t *tmpMvf;
/*
* Before initializing the reference counts, verify that the leaves form a
* support set for the roots.
*/
if (!Ntk_NetworkTestLeavesCoverSupportOfRoots(network, roots, leaves)) {
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 MvfAig and store a duplicate copy of it in the
* result array. The nodeToMvfAigTable is used to keep track of intermediate
* computations. Intermediate MvfAigs are freed as soon as possible by using
* the reference count mechanism.
*/
nodeToMvfAigTable = (st_table *) Ntk_NetworkReadApplInfo(network, MVFAIG_NETWORK_APPL_KEY);
if (nodeToMvfAigTable == NIL(st_table)){
nodeToMvfAigTable = st_init_table(st_ptrcmp, st_ptrhash);
/* Register the MvfAig Table in the network*/
Ntk_NetworkAddApplInfo(network, MVFAIG_NETWORK_APPL_KEY,
(Ntk_ApplInfoFreeFn) ntmAig_MvfAigTableFreeCallback,
(void *) nodeToMvfAigTable);
}
for (i = 0; i < numRoots; i++) {
Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
tmpMvf = NodeBuildMvfAigRecursively(root, leaves,
nodeToMvfAigTable, manager);
MvfAig = MvfAig_FunctionDuplicate(tmpMvf);
array_insert(MvfAig_Function_t *, result, i, MvfAig);
}
return result;
}
/**Function********************************************************************
Synopsis [Call-back function to free a MvfAig Table.]
Description [This function will be stored in the network together with the
pointer to the MvfAig Table. Whenever the network deletes the MvfAig
information, this function is called and it will free the table and
the information attached to it.]
SideEffects []
SeeAlso [Ntk_NetworkAddApplInfo]
******************************************************************************/
void
ntmAig_MvfAigTableFreeCallback(
void *data)
{
st_generator *stGen;
MvfAig_Function_t *MvfAig;
Ntk_Node_t *node;
st_table *nodeToMvfAigTable = (st_table*) data;
st_foreach_item(nodeToMvfAigTable, stGen, &node, &MvfAig) {
MvfAig_FunctionFree(MvfAig);
}
st_free_table(nodeToMvfAigTable);
} /* End of ntmAig_MvfAigTableFreeCallback */
/*---------------------------------------------------------------------------*/
/* Definition of internal functions */
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
/* Definition of static functions */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************
Synopsis [Builds MvfAig for a node, recursively in terms of fanins.]
Description [Recursively builds MvfAig_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 [NodeBuildInputMvfAig,NodeBuildPseudoInputMvfAig,NodeBuildInternalMvfAig]
[Done]
******************************************************************************/
static MvfAig_Function_t *
NodeBuildMvfAigRecursively(
Ntk_Node_t * node,
st_table * leaves,
st_table * nodeToMvfTable,
mAig_Manager_t *manager)
{
MvfAig_Function_t *MvfAig = NodeReadMvfAig(node, nodeToMvfTable);
/* If the MvfAig for this node has already been computed, then just return it. */
if (MvfAig != NIL(MvfAig_Function_t)) {
return MvfAig;
}
if (Ntk_NodeTestIsConstant(node)) {
/* Doesn't matter if constant is a leaf or not. */
MvfAig = NodeBuildConstantMvfAig(node, ntmaig_UNUSED, manager);
}
else {
int constValue;
if (st_lookup_int(leaves, node, &constValue)) {
if (constValue == ntmaig_UNUSED) {
/* Node is a leaf. */
if ((Ntk_NodeTestIsPrimaryInput(node)) ||
(Ntk_NodeTestIsLatch(node)) ||
(Ntk_NodeTestIsCombinational(node))) {
/* Node can assume any value. */
MvfAig = NodeBuildInputMvfAig(manager, node);
}
else if (Ntk_NodeTestIsPseudoInput(node)) {
/* Node may assume only a subset of possible values. */
MvfAig = NodeBuildPseudoInputMvfAigNew(manager, node);
}
else {
fail("Encountered unknown type in MvfAig recursion\n");
}
}
else {
/* treat the leaf node as being a constant taking the value constValue */
MvfAig = NodeBuildConstantMvfAig(node, constValue, manager);
}
}
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 {
MvfAig = NodeBuildInternalMvfAig(node, leaves, nodeToMvfTable, manager);
}
}
}
NodeSetMvfAig(node, nodeToMvfTable, MvfAig);
return MvfAig;
}
/**Function********************************************************************
Synopsis [Builds MvfAig for a node that is treated as a free input.]
SideEffects []
[Done]
******************************************************************************/
static MvfAig_Function_t *
NodeBuildInputMvfAig(
mAig_Manager_t *manager,
Ntk_Node_t * node)
{
int mAigId = Ntk_NodeReadMAigId(node);
assert(mAigId != NTK_UNASSIGNED_MAIG_ID);
return MvfAig_FunctionCreateFromVariable(manager, mAigId);
}
/**Function********************************************************************
Synopsis [Builds MvfAig for a node that is a pseudo input.]
Description [Builds MvfAig 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 MvfAig 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 MvfAig. A pseudo
input MvfAig 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_TableBuildMvfAigForNonDetConstant]
[Done]
******************************************************************************/
static MvfAig_Function_t *
NodeBuildPseudoInputMvfAigNew(
mAig_Manager_t *manager,
Ntk_Node_t * node)
{
int lIndex=0, needProcess, i;
mAigEdge_t mAig, tmpAig;
MvfAig_Function_t *MvfAig;
int columnIndex = Ntk_NodeReadOutputIndex(node);
Tbl_Table_t *table = Ntk_NodeReadTable(node);
int mAigId = Ntk_NodeReadMAigId(node);
assert(mAigId != NTK_UNASSIGNED_MAIG_ID);
MvfAig = Tbl_TableBuildNonDetConstantMvfAig(table, columnIndex,
mAigId,
manager);
needProcess = 0;
tmpAig = mAig_Zero;
for(i=0; i