src/ntm/ntm.c

Go to the documentation of this file.

#include "ntmInt.h"

static char rcsid[] UNUSED = "$Id: ntm.c,v 1.11 2009/04/11 01:45:44 fabio Exp $";

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

static Mvf_Function_t * NodeBuildMvfRecursively(Ntk_Node_t * node, st_table * leaves, st_table * nodeToMvfTable, mdd_manager *mddMgr, mdd_t *careSet);
static Mvf_Function_t * NodeBuildInputMvf(Ntk_Node_t * node, mdd_manager *mddMgr);
#if 0
static Mvf_Function_t * NodeBuildPseudoInputMvf(Ntk_Node_t * node, mdd_manager * mddMgr);
#endif
static Mvf_Function_t * NodeBuildPseudoInputMvfNew(Ntk_Node_t * node, mdd_manager * mddMgr);
static Mvf_Function_t * NodeBuildConstantMvf(Ntk_Node_t * node, int constantValue, mdd_manager *mddMgr);
static Mvf_Function_t * NodeBuildInternalMvf(Ntk_Node_t * node, st_table * leaves, st_table * nodeToMvfTable, mdd_manager *mddMgr, mdd_t *careSet);
static Mvf_Function_t * NodeReadMvf(Ntk_Node_t * node, st_table * nodeToMvfTable);
static void NodeSetMvf(Ntk_Node_t * node, st_table * nodeToMvfTable, Mvf_Function_t * mvf);
static int CommandNtmTest(Hrc_Manager_t ** hmgr, int argc, char ** argv);
static void MvfSanityCheck(array_t *roots, array_t *mvfs);
static void RegionInitializeReferenceCounts(array_t *roots, st_table *leaves);
static void NodeDecrementRefCount(Ntk_Node_t *node, st_table *nodeToMvfTable);
static boolean TableTestIsContainedInArray(st_table *table1, array_t *nodeArrary);

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

void
Ntm_Init(void)
{
  Cmd_CommandAdd("_ntm_test", CommandNtmTest, /* doesn't changes_network */ 0);
}


void
Ntm_End(void)
{
}


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


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;

}


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


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<mvf->num; i++) {
    vMdd = array_fetch(mdd_t *, mvf, i);
    if(mdd_equal(vMdd, rMdd)) {
      needProcess = 1;
    }
    else {
      lIndex = i;
    }
  }
  if(needProcess) {
    for(i=0; i<lIndex; i++) {
      vMdd = array_fetch(mdd_t *, mvf, i);
      tMdd = mdd_or(vMdd, rMdd, 1, 1);
      mdd_free(rMdd);
      rMdd = tMdd;
    }
    vMdd = array_fetch(mdd_t *, mvf, lIndex);
    mdd_free(vMdd);
    tMdd = mdd_not(rMdd);
    mdd_free(rMdd);
    array_insert(mdd_t *, mvf, lIndex, tMdd);
  }
  else {
    mdd_free(rMdd);
  }
  return mvf;
}

#if 0
static Mvf_Function_t *
NodeBuildPseudoInputMvf(
  Ntk_Node_t * node,
  mdd_manager * mddMgr)
{
  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);

  return mvf;
}
#endif


static Mvf_Function_t *
NodeBuildConstantMvf(
  Ntk_Node_t * node,
  int constantValue,
  mdd_manager *mddMgr)
{
  int             value        = 0; /* initialized to stop lint complaining */
  mdd_t          *oneMdd       = mdd_one(mddMgr);
  Var_Variable_t *variable     = Ntk_NodeReadVariable(node);
  int             numVarValues = Var_VariableReadNumValues(variable);
  Mvf_Function_t *mvf          = Mvf_FunctionAlloc(mddMgr, numVarValues);


  if (constantValue != NTM_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);
  }

  Mvf_FunctionAddMintermsToComponent(mvf, value, oneMdd);
  mdd_free(oneMdd);
  return mvf;
}


static Mvf_Function_t *
NodeBuildInternalMvf(
  Ntk_Node_t * node,
  st_table * leaves,
  st_table * nodeToMvfTable,
  mdd_manager *mddMgr,
  mdd_t *careSet)
{
  int             i;
  Mvf_Function_t *resultMvf;
  Ntk_Node_t     *faninNode;
  array_t        *faninMvfs   = array_alloc(Mvf_Function_t *, Ntk_NodeReadNumFanins(node));
  int             outputIndex = Ntk_NodeReadOutputIndex(node);
  Tbl_Table_t    *table       = Ntk_NodeReadTable(node);


  Ntk_NodeForEachFanin(node, i, faninNode) {
    Mvf_Function_t *tmpMvf = NodeBuildMvfRecursively(faninNode, leaves,
                                                     nodeToMvfTable, mddMgr,
                                                     careSet);
    array_insert(Mvf_Function_t *, faninMvfs, i, tmpMvf);
  }
  resultMvf = Tbl_TableBuildMvfFromFanins(table, outputIndex, faninMvfs, mddMgr);

  /* Mc_CheckValdityOfMvf(Ntk_NodeReadNetwork(node), mddMgr, node, resultMvf); */

  Ntk_NodeForEachFanin(node, i, faninNode) {
    NodeDecrementRefCount(faninNode, nodeToMvfTable);
  }

  /* Don't free the MVFs themselves, but just free the array. */
  array_free(faninMvfs);

  return resultMvf;
}


static Mvf_Function_t *
NodeReadMvf(
  Ntk_Node_t * node,
  st_table * nodeToMvfTable)
{
  Mvf_Function_t *result = NIL(Mvf_Function_t);
  st_lookup(nodeToMvfTable, node, &result);

  return result;
}


static void
NodeSetMvf(
  Ntk_Node_t * node,
  st_table * nodeToMvfTable,
  Mvf_Function_t * mvf)
{
  st_insert(nodeToMvfTable, (char *) node, (char *) mvf);
}


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


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


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

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

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