#include "ntmaigInt.h"#include "baig.h"
Include dependency graph for ntmaig.c:
Go to the source code of this file.
Functions | |
| static MvfAig_Function_t * | NodeBuildMvfAigRecursively (Ntk_Node_t *node, st_table *leaves, st_table *nodeToMvfTable, mAig_Manager_t *manager) |
| static MvfAig_Function_t * | NodeBuildInputMvfAig (mAig_Manager_t *manager, Ntk_Node_t *node) |
| static MvfAig_Function_t * | NodeBuildPseudoInputMvfAigNew (mAig_Manager_t *manager, Ntk_Node_t *node) |
| static MvfAig_Function_t * | NodeBuildConstantMvfAig (Ntk_Node_t *node, int constantValue, mAig_Manager_t *manager) |
| static MvfAig_Function_t * | NodeBuildInternalMvfAig (Ntk_Node_t *node, st_table *leaves, st_table *nodeToMvfAigTable, mAig_Manager_t *manager) |
| static MvfAig_Function_t * | NodeReadMvfAig (Ntk_Node_t *node, st_table *nodeToMvfAigTable) |
| static void | NodeSetMvfAig (Ntk_Node_t *node, st_table *nodeToMvfAigTable, MvfAig_Function_t *MvfAig) |
| static void | RegionInitializeReferenceCounts (array_t *roots, st_table *leaves) |
| static void | NodeDecrementRefCount (Ntk_Node_t *node, st_table *nodeToMvfTable) |
| array_t * | ntmaig_NetworkBuildMvfAigs (Ntk_Network_t *network, array_t *roots, st_table *leaves) |
| void | ntmAig_MvfAigTableFreeCallback (void *data) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: ntmaig.c,v 1.15 2005/04/28 08:54:35 bli Exp $" |
Function Documentation
| static MvfAig_Function_t * NodeBuildConstantMvfAig | ( | Ntk_Node_t * | node, |
| int | constantValue, | ||
| mAig_Manager_t * | manager | ||
| ) | [static] |
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]Function********************************************************************
Synopsis [Builds MvfAig for a node with no inputs, and only one row in its table.]
Description [Builds MvfAig for a constant. If constantValue is ntmaig_UNUSED, then constantValue should be a legal index in the domain of the variable of node. In this case, regardless of the type of the node, an MvfAig is built where the component indexed by constantValue is one (i.e. the tautology) and all other components are zero.
If constantValue is not ntmaig_UNUSED, then node should be a constant, combinational node. In this case, an MvfAig is built with a single component (indexed by the value of node) is one, and all other components are zero.]
SideEffects [] [Done]
Definition at line 376 of file ntmaig.c.
{
int value = 0; /* initialized to stop lint complaining */
Var_Variable_t *variable = Ntk_NodeReadVariable(node);
int numVarValues = Var_VariableReadNumValues(variable);
MvfAig_Function_t *MvfAig = MvfAig_FunctionAlloc(numVarValues);
if (constantValue != ntmaig_UNUSED) {
/* Use the given value. */
assert((constantValue >= 0) && (constantValue < numVarValues));
value = constantValue;
}
else {
int outputIndex = Ntk_NodeReadOutputIndex(node);
Tbl_Table_t *table = Ntk_NodeReadTable(node);
assert(Ntk_NodeTestIsConstant(node));
value = Tbl_TableReadConstValue(table, outputIndex);
assert(value != -1);
}
MvfAig_FunctionAddMintermsToComponent(manager, MvfAig, value, bAig_One);
return MvfAig;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static MvfAig_Function_t * NodeBuildInputMvfAig | ( | mAig_Manager_t * | manager, |
| Ntk_Node_t * | node | ||
| ) | [static] |
Function********************************************************************
Synopsis [Builds MvfAig for a node that is treated as a free input.]
SideEffects [] [Done]
Definition at line 255 of file ntmaig.c.
{
int mAigId = Ntk_NodeReadMAigId(node);
assert(mAigId != NTK_UNASSIGNED_MAIG_ID);
return MvfAig_FunctionCreateFromVariable(manager, mAigId);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static MvfAig_Function_t * NodeBuildInternalMvfAig | ( | Ntk_Node_t * | node, |
| st_table * | leaves, | ||
| st_table * | nodeToMvfAigTable, | ||
| mAig_Manager_t * | manager | ||
| ) | [static] |
Function********************************************************************
Synopsis [Builds MvfAig for an internal node in terms of its fanin's MvfAigs.]
Description [Builds MvfAig for an internal node in terms of its fanin's MvfAigs. An internal node is a node that is in the transitive fanin of a root, but is not a leaf.]
SideEffects [] [Done]
Definition at line 417 of file ntmaig.c.
{
int i;
MvfAig_Function_t *resultMvfAig;
Ntk_Node_t *faninNode;
array_t *faninMvfAigs = array_alloc(MvfAig_Function_t *, Ntk_NodeReadNumFanins(node));
int outputIndex = Ntk_NodeReadOutputIndex(node);
Tbl_Table_t *table = Ntk_NodeReadTable(node);
Ntk_NodeForEachFanin(node, i, faninNode) {
MvfAig_Function_t *tmpMvfAig = NodeBuildMvfAigRecursively(faninNode, leaves,
nodeToMvfAigTable, manager);
array_insert(MvfAig_Function_t *, faninMvfAigs, i, tmpMvfAig);
}
resultMvfAig = Tbl_TableBuildMvfAigFromFanins(table, outputIndex, faninMvfAigs, manager);
Ntk_NodeForEachFanin(node, i, faninNode) {
NodeDecrementRefCount(faninNode, nodeToMvfAigTable);
}
/* Don't free the MvfAigs themselves, but just free the array. */
array_free(faninMvfAigs);
return resultMvfAig;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static MvfAig_Function_t * NodeBuildMvfAigRecursively | ( | Ntk_Node_t * | node, |
| st_table * | leaves, | ||
| st_table * | nodeToMvfTable, | ||
| mAig_Manager_t * | manager | ||
| ) | [static] |
AutomaticStart
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]
Definition at line 188 of file ntmaig.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static MvfAig_Function_t * NodeBuildPseudoInputMvfAigNew | ( | mAig_Manager_t * | manager, |
| Ntk_Node_t * | node | ||
| ) | [static] |
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]
Definition at line 285 of file ntmaig.c.
{
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<MvfAig->num; i++) {
mAig = array_fetch(mAigEdge_t, MvfAig, i);
if(mAig == tmpAig) {
needProcess = 1;
}
else {
lIndex = i;
}
}
if(needProcess) {
for(i=0; i<lIndex; i++) {
mAig = array_fetch(mAigEdge_t, MvfAig, i);
tmpAig = mAig_Or(manager, tmpAig, mAig);
}
array_insert(mAigEdge_t, MvfAig, lIndex, mAig_Not(tmpAig));
}
return MvfAig;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void NodeDecrementRefCount | ( | Ntk_Node_t * | node, |
| st_table * | nodeToMvfTable | ||
| ) | [static] |
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 []
Definition at line 540 of file ntmaig.c.
{
long refCount = (long) Ntk_NodeReadUndef(node);
assert(refCount != 0);
refCount--;
/*
Want to keep the entry of this node, so we may get the MvfAig of this node
whenever we need it. The pointer to the nodeToMvfTable is stored in the network
information.
*/
/*
if (refCount == 0) {
st_delete(nodeToMvfTable, (char **) &node, (char **) &mvf);
MvfAig_FunctionFree(mvf);
}
*/
Ntk_NodeSetUndef(node, (void *) refCount);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static MvfAig_Function_t * NodeReadMvfAig | ( | Ntk_Node_t * | node, |
| st_table * | nodeToMvfAigTable | ||
| ) | [static] |
Function********************************************************************
Synopsis [Returns MvfAig corresponding to a node; returns NIL if node not in table.]
SideEffects [] [Done]
Definition at line 454 of file ntmaig.c.
{
MvfAig_Function_t *result = NIL(MvfAig_Function_t);
st_lookup(nodeToMvfAigTable, node, &result);
return result;
}
Here is the caller graph for this function:
| static void NodeSetMvfAig | ( | Ntk_Node_t * | node, |
| st_table * | nodeToMvfAigTable, | ||
| MvfAig_Function_t * | MvfAig | ||
| ) | [static] |
| void ntmAig_MvfAigTableFreeCallback | ( | void * | data | ) |
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]
Definition at line 147 of file ntmaig.c.
{
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 */
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* ntmaig_NetworkBuildMvfAigs | ( | Ntk_Network_t * | network, |
| array_t * | roots, | ||
| st_table * | leaves | ||
| ) |
AutomaticEnd Function********************************************************************
Synopsis [Builds multi-valued functions for roots, in terms of leaves.]
Description [Takes an array of root nodes and a table of leaf nodes, and builds the multi-valued functions (MvfAigs) for the roots in terms of the leaves. This function returns an array of MvfAig_Function_t*, in one-to-one correspondence with the roots array. It is assumed that every path, from a root backwards to a combinational input, passes through a node in the leaves table, and that there are no combinational cycles within the region defined by the roots and leaves. Also, it is assumed that every node in the leaves table already has an mAig Id.
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 []
Definition at line 80 of file ntmaig.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void RegionInitializeReferenceCounts | ( | array_t * | roots, |
| st_table * | leaves | ||
| ) | [static] |
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.]
Definition at line 497 of file ntmaig.c.
{
int i;
Ntk_Node_t *node;
st_generator *stGen;
st_table *regionNodes = Ntk_RegionFindNodes(roots, leaves);
st_foreach_item(regionNodes, stGen, &node, NIL(char *)) {
Ntk_Node_t *fanoutNode;
long refCount = 0;
Ntk_NodeForEachFanout(node, i, fanoutNode) {
if (st_is_member(regionNodes, fanoutNode)
&& !st_is_member(leaves, 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, (char *) MAXINT);
}
st_free_table(regionNodes);
}
Here is the call graph for this function:
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: ntmaig.c,v 1.15 2005/04/28 08:54:35 bli Exp $" [static] |
CFile***********************************************************************
FileName [ntmaig.c]
PackageName [ntmaig]
Synopsis [Routines to build mAigs from a network.]
Author [Mohammad Awedh]
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.]
