src/ntmaig/ntmaig.c

Go to the documentation of this file.

#include "ntmaigInt.h"
#include "baig.h"

static char rcsid[] UNUSED = "$Id: ntmaig.c,v 1.15 2005/04/28 08:54:35 bli Exp $";

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

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 * NodeBuildPseudoInputMvfAig(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);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

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;
}

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                                            */
/*---------------------------------------------------------------------------*/


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;

}


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);
}

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<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;
}

/*static MvfAig_Function_t *
NodeBuildPseudoInputMvfAig(
  mAig_Manager_t *manager,
  Ntk_Node_t * node)
{
  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);
  return MvfAig;
}*/


static MvfAig_Function_t *
NodeBuildConstantMvfAig(
  Ntk_Node_t * node,
  int constantValue,
  mAig_Manager_t *manager)
{
  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;
}


static MvfAig_Function_t *
NodeBuildInternalMvfAig(
  Ntk_Node_t * node,
  st_table   * leaves,
  st_table   * nodeToMvfAigTable,
  mAig_Manager_t *manager)
{
  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;
}


static MvfAig_Function_t *
NodeReadMvfAig(
  Ntk_Node_t * node,
  st_table   * nodeToMvfAigTable)
{
  MvfAig_Function_t *result = NIL(MvfAig_Function_t);
  st_lookup(nodeToMvfAigTable,  node,  &result);

  return result;
}


static void
NodeSetMvfAig(
  Ntk_Node_t * node,
  st_table   * nodeToMvfAigTable,
  MvfAig_Function_t * MvfAig)
{
  st_insert(nodeToMvfAigTable,  node,  MvfAig);
}

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, 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);
}

static void
NodeDecrementRefCount(
  Ntk_Node_t *node, 
  st_table *nodeToMvfTable)
{
  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);
}