src/spfd/spfdProg.c

Go to the documentation of this file.

#include "spfdInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


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

static Tbl_Table_t * BuildNewTable(Ntk_Network_t *network, Ntk_Node_t *ntkNode, mdd_t *mddFunc);
static void TableAddCube(Tbl_Table_t *table, array_t *faninIdArray, array_t *cube, int value);

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


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
void
SpfdReprogramRegionNodes(
  Ntk_Network_t *network,
  SpfdApplData_t *applData,
  array_t *regionArray)
{
  st_table *nodeCountTable,*sinkTable;
  st_table *regionNodes = applData->currRegionNodes;
  st_table *currBddReq = applData->currBddReq;
  st_table *wireTable = applData->currWireTable;
  st_table *replaceTable = applData->currReplaceTable;
  bdd_manager *ddManager = applData->ddManager;
  Ntk_Node_t *fanout,*regNode,*fanin,*newFanin;
  bdd_node *bdd1,*localAlt,*globalAlt;
  bdd_node *ddTemp,*relNew,*relOld,*encRel;
  bdd_node *xCube;
  char *dummy;
  st_generator *stGen;
  int bound,i,j,k,piSwap;
  int *count;
  array_t *faninBdds,*faninNodes,*nodeArray;

  /* Cube of primary inputs. */
  xCube = applData->currXCube;
  /* Analyze the region to find out how many times the
     alternative/global function of an individual region node will be
     used. This count will be used to remove those functions when no
     longer needed, hence avoid memory peaks. */
  nodeCountTable = st_init_table(st_ptrcmp,st_ptrhash);
  st_foreach_item(currBddReq,stGen,&regNode,&bdd1) {
    count = ALLOC(int,1);
    *count = 0;
    Ntk_NodeForEachFanout(regNode,k,fanout) {
      if (st_lookup(regionNodes,(char *)fanout,&dummy))
        (*count)++;
    }
    /* The global function implemented by regNode is used count number
       of times */
    assert(*count);
    st_insert(nodeCountTable,(char *)regNode,(char *)count);
  }

  /* Reprogram region nodes */
  arrayForEachItem(Ntk_Node_t *,regionArray,i,regNode) {
    int numFanin;
    boolean reenc,replaced;
    bdd_node **orgVars,**auxVars,*orgCube;

    /* Skip, if it is a PI. */
    if (Ntk_NodeTestIsPrimaryInput(regNode))
      continue;
    
    /* Determine if the localAlt really needs to be re-encoded. This
       is true if any of the fanin nodes have been reprogrammed. If
       any fanin node of 'regNode' has a non NULL globalAlt, then it
       means that fanin node has been reprogrammed. */
    faninBdds = array_alloc(bdd_node *,0);
    faninNodes = array_alloc(Ntk_Node_t *,0);
    reenc = FALSE;
    replaced = FALSE;
    if (SpfdNodeReadLocalAlt(applData,regNode) !=
        bdd_read_logic_zero(ddManager)) {
      Ntk_NodeForEachFanin(regNode,j,fanin) {

        /* If a particular wire is redundant/replaced, make the sink node
           independent of that node. */
        if (!(st_lookup(wireTable,(char *)fanin,&sinkTable) &&
              st_lookup(sinkTable,(char *)regNode,&dummy))) {
          /* If not removed, is it replaced? */
          if (!(st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
                st_lookup(sinkTable,(char *)fanin,&newFanin))) {
            globalAlt = SpfdNodeReadGlobalAlternative(applData,fanin);
            if (globalAlt) { /* Reprogrammed? */
              array_insert_last(bdd_node *,faninBdds,globalAlt);
              array_insert_last(Ntk_Node_t *,faninNodes,fanin);
              reenc = TRUE;
            } else { /* No. So use the original global function */
              st_lookup(currBddReq,(char *)fanin,&ddTemp);
              array_insert_last(bdd_node *,faninBdds,ddTemp);
              array_insert_last(Ntk_Node_t *,faninNodes,fanin);
            }
          } else {
            /* The wire fanin --> regNode has been replaced by newFanin -->
               regNode */
            globalAlt = SpfdNodeReadGlobalAlternative(applData,newFanin);
            assert(globalAlt);
            array_insert_last(bdd_node *,faninBdds,globalAlt);
            array_insert_last(Ntk_Node_t *,faninNodes,newFanin);
            reenc = TRUE;
            replaced = TRUE;
          }
        } else {
          reenc = TRUE;
        }
      }
    }
      
    if (reenc) { /* Reencode the localAlt */
      /* Compute the encoding relation */
      relNew = SpfdComputeNodeArrayRelation(applData,NIL(st_table),
                                              faninBdds,faninNodes,
                                              FALSE,&piSwap);
      array_free(faninBdds);
      array_free(faninNodes);
      relOld = SpfdComputeNodeArrayRelation(applData,currBddReq,NIL(array_t),
                                              Ntk_NodeReadFanins(regNode),
                                              TRUE,&piSwap);
      bdd_ref(encRel = bdd_bdd_and_abstract(ddManager,relNew,relOld,xCube));
      bdd_recursive_deref(ddManager,relNew);
      bdd_recursive_deref(ddManager,relOld);

      if (piSwap) { /* If we have used alternate PI ids */
        ddTemp = SpfdSwapPiAndAltPi(applData,encRel);
        bdd_recursive_deref(ddManager,encRel);
        encRel = ddTemp;
      }
      /* Now encRel is in terms of Y, Y'. Y variables are the node's
         mdd ids. Y' are the auxIds of regNode's fanin nodes. One of
         these fanin nodes could be a new node replacing an old node. */
      /* Prepare variables for swapping and abstraction */
      numFanin = Ntk_NodeReadNumFanins(regNode);
      orgVars = ALLOC(bdd_node *,numFanin);
      auxVars = ALLOC(bdd_node *,numFanin);
      Ntk_NodeForEachFanin(regNode,k,fanin) {
        orgVars[k] = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin));
        auxVars[k] = bdd_bdd_ith_var(ddManager,
                                     SpfdNodeReadAuxId(applData,fanin));
      }
      bdd_ref(orgCube = bdd_bdd_compute_cube(ddManager,orgVars,
                                             NIL(int),numFanin));

      /* Re-encode the localAlt function. ddTemp is in terms of Y' */
      localAlt = SpfdNodeReadLocalAlt(applData,regNode);
      bdd_ref(ddTemp = bdd_bdd_and_abstract(ddManager,localAlt,encRel,orgCube));
      SpfdNodeDeleteLocalAlt(applData,regNode);
      bdd_recursive_deref(ddManager,encRel);
      bdd_recursive_deref(ddManager,orgCube);

      /* Check if the wire is replaced. Pay attention to auxVars and
         orgVars. */
      /* Small caveat: Only here it is possible that the orgVar of
         newFanin is already being used as auxId by one of the nodes
         in the region. The situation can be as below: */
      /* 12 -> 19, 15->24, 133->15, 18->23. During swapping, 133 will
         be replace by 15. This will create a problem because 15->24
         has not been done yet! A consolation is that the intersection
         between the 'from' set and the 'two' set is only ONE. */
      /* To avoid this problem, we do two step swap to be sure. */
      if (replaced) {
        bdd_node **secOrgVars,**secAuxVars;
        int auxId,orgId,index;
        
        FREE(orgVars);
        FREE(auxVars);
        orgVars = ALLOC(bdd_node *,numFanin-1);
        auxVars = ALLOC(bdd_node *,numFanin-1);
        secOrgVars = ALLOC(bdd_node *,1);
        secAuxVars = ALLOC(bdd_node *,1);
        index = 0;
        Ntk_NodeForEachFanin(regNode,k,fanin) {
          if (st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
              st_lookup(sinkTable,(char *)fanin,&newFanin)) {
            orgId = Ntk_NodeReadMddId(newFanin);
            auxId = SpfdNodeReadAuxId(applData,newFanin);
            secOrgVars[0] = bdd_bdd_ith_var(ddManager,orgId);
            secAuxVars[0] = bdd_bdd_ith_var(ddManager,auxId);
          } else {
            orgId = Ntk_NodeReadMddId(fanin);
            auxId = SpfdNodeReadAuxId(applData,fanin);
            orgVars[index] = bdd_bdd_ith_var(ddManager,orgId);
            auxVars[index] = bdd_bdd_ith_var(ddManager,auxId);
            index++;
          }
        }
        bdd_ref(localAlt = bdd_bdd_swap_variables(ddManager,ddTemp,auxVars,
                                                  orgVars,index));
        bdd_recursive_deref(ddManager,ddTemp);
        bdd_ref(ddTemp = bdd_bdd_swap_variables(ddManager,localAlt,
                                                secAuxVars,secOrgVars,1));
        bdd_recursive_deref(ddManager,localAlt);
        localAlt = ddTemp;
        FREE(secOrgVars);
        FREE(secAuxVars);
      } else {
        bdd_ref(localAlt = bdd_bdd_swap_variables(ddManager,ddTemp,auxVars,
                                                  orgVars,numFanin));
        bdd_recursive_deref(ddManager,ddTemp);
      }
      FREE(orgVars);
      FREE(auxVars);

      SpfdNodeSetLocalAlt(applData,regNode,localAlt);
    } else {
      array_free(faninBdds);
      array_free(faninNodes);
    }

    /* Compute the global function (only if it is needed, i.e, it is
       present in the nodeCountTable) implemented by the alternate
       function, localAlt, chosen from the SPFD. */
    localAlt = SpfdNodeReadLocalAlt(applData,regNode);
    if (st_lookup(nodeCountTable,(char *)regNode,&count) &&
        !Ntk_NodeTestIsPrimaryInput(regNode) &&
        !Ntk_NodeTestIsPrimaryOutput(regNode)) {
      int size,id;
      bdd_node **composeBdds;
      
      size = bdd_num_vars(ddManager);;
      composeBdds = ALLOC(bdd_node *,size);
      for (k = 0; k < size; k++) {
        composeBdds[k] = bdd_bdd_ith_var(ddManager,k);
      }

      /* Here I don't have to worry about checking if a wire is redundant. The
         localAlt of the node already is independent of source node of that
         wire and so composing with the source node does not matter. But I do
         need to check for wire replacement. */
      Ntk_NodeForEachFanin(regNode,k,fanin) {
        if (st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
            st_lookup(sinkTable,(char *)fanin,&newFanin)) {
          id = Ntk_NodeReadMddId(newFanin);
          globalAlt = SpfdNodeReadGlobalAlternative(applData,newFanin);
          composeBdds[id] = globalAlt;
        } else {
          id = Ntk_NodeReadMddId(fanin);
          globalAlt = SpfdNodeReadGlobalAlternative(applData,fanin);
          if (globalAlt) {
            composeBdds[id] = globalAlt;
          } else {
            st_lookup(currBddReq,(char *)fanin,(char **)&composeBdds[id]);
          }       
        }
      }
      localAlt = SpfdNodeReadLocalAlt(applData,regNode);
      bdd_ref(globalAlt = bdd_bdd_vector_compose(ddManager,localAlt,
                                                 composeBdds));
      SpfdNodeSetGlobalAlternative(applData,regNode,globalAlt);
      FREE(composeBdds);
    }

    /* Delete the global BDDs of fanin nodes if unnecessary */
    Ntk_NodeForEachFanin(regNode,k,fanin) {
      int *count;
      if (st_lookup(nodeCountTable,(char *)fanin,&count)) {
        (*count)--;
        if (*count == 0) {
          st_delete(currBddReq,&fanin,&bdd1);
          bdd_recursive_deref(ddManager,bdd1);
          SpfdNodeDeleteGlobalAlternative(applData,fanin);
          st_delete(nodeCountTable,&fanin,&count);
          FREE(count);
        }
      }
    }

    /* Finally, delete the redundant wires */
    nodeArray = array_dup(Ntk_NodeReadFanins(regNode));
    arrayForEachItem(Ntk_Node_t *,nodeArray,j,fanin) {
      /* If a particular wire is redundant, make the sink node independent of
         the source node. */
      if (st_lookup(wireTable,(char *)fanin,&sinkTable) &&
          st_lookup(sinkTable,(char *)regNode,&dummy)) {
        /* remove the wire from the wireTable */
        st_delete(sinkTable,&regNode,&dummy);
        if (st_count(sinkTable) == 0) {
          st_delete(wireTable,&fanin,&sinkTable);
          st_free_table(sinkTable);
        }
        SpfdNetworkRemoveWire(network,fanin,regNode);
      } else if (st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
                 st_lookup(sinkTable,(char *)fanin,&newFanin)) {
        /* In this case I do not clean replaceTable as was done for
           wireTable. The table is needed later. */
        /* Add the new wire first and then remove the old wire. This
           way the source node of the new wire will not be deleted if
           it initially had a fanout of 1 and was in the TFI of the
           old wire. newsource --> fanin --> regNode. If 'fanin' has
           only one fanout then its entire TFI will be deleted, hence,
           possibly deleteing newsource from the network. */
        SpfdNetworkAddWire(network,newFanin,regNode);
        SpfdNetworkRemoveWire(network,fanin,regNode);
      }
    }
    array_free(nodeArray);
    
    /* Reprogram the node's table data structure. */
    localAlt = SpfdNodeReadLocalAlt(applData,regNode);
    SpfdReprogramNode(network,applData,regNode);
    SpfdNodeDeleteLocalAlt(applData,regNode);
  }

  /* nodeCountTable need not be empty at this time as some wire may be 
     removed and the count is not reduced appropriately in nodeCountTable. 
     So, delete them explicitly. Defensive programming. */
  st_foreach_item(nodeCountTable,stGen,&regNode,&count) {
    st_delete(currBddReq,&regNode,&bdd1);
    bdd_recursive_deref(ddManager,bdd1);
    SpfdNodeDeleteGlobalAlternative(applData,regNode);
    FREE(count);
  }
  st_free_table(nodeCountTable);
  
  /* Just reusing variable bound */
  bound = st_count(currBddReq);
  assert(bound == 0);
  st_free_table(applData->currBddReq);
  applData->currBddReq = NIL(st_table);
  
  return;
} /* End of SpfdReprogramRegionNodes */


void
SpfdReprogramNode(
  Ntk_Network_t *network,
  SpfdApplData_t *applData,
  Ntk_Node_t *regNode)
{
  bdd_node *localAlt;
  bdd_node *bdd1,*bdd0;
  bdd_manager *ddManager = applData->ddManager;
  graph_t *partition = (graph_t *) Ntk_NetworkReadApplInfo(
    network,PART_NETWORK_APPL_KEY);
  Tbl_Table_t *table;
  vertex_t *vertexPtr;
  Mvf_Function_t *mvf;
  mdd_t *tempMdd;
    
  /* Extract old local function from the partition */
  vertexPtr = Part_PartitionFindVertexByMddId(partition,
                                              Ntk_NodeReadMddId(regNode));
  mvf = Part_VertexReadFunction(vertexPtr);
  /* First delete the old mvf */
  Mvf_FunctionFree(mvf);
  
  /* Steps to reprogram the node.  1. Delete the old table associated with
   * this node. The table can be deleted because in BLIF format tables have
   * only a single output unlike BLIF-MV.  2. Create a new table and set it
   * in the node.  3. Update the new local function in the partition */
  table = Ntk_NodeReadTable(regNode);
  Tbl_TableFree(table);
      
  bdd_ref(localAlt = SpfdNodeReadLocalAlt(applData,regNode));

  /* If pattern simulation is performed, update node's static
     probability and transition probability */
  if (spfdPerfSim) {
    float prob;
    prob = Truesim_BddNodeComputeProbability(network,localAlt);
    Truesim_NetworkSetNodeStaticProb(network,regNode,prob);
    Truesim_NetworkSetNodeSwitchingProb(network,regNode,2*prob*(1-prob));
  }
  
  /* Create the new table */
  tempMdd = bdd_construct_bdd_t(ddManager,localAlt);
  table = BuildNewTable(network,regNode,tempMdd);
  Ntk_NodeSetTable(regNode,table);
  mdd_free(tempMdd);
      
  /* Compute the node's new MVF and set it in the partition. */
  mvf = array_alloc(bdd_t *,2);
  bdd_ref(bdd1 = SpfdNodeReadLocalAlt(applData,regNode));
  bdd_ref(bdd0 = bdd_not_bdd_node(bdd1));
  array_insert(bdd_t *,mvf,0,bdd_construct_bdd_t(ddManager,bdd0));
  array_insert(bdd_t *,mvf,1,bdd_construct_bdd_t(ddManager,bdd1));
  Part_VertexSetFunction(vertexPtr,mvf);

  return;
} /* End of SpfdReprogramNode */


void
SpfdNetworkRemoveWire(
  Ntk_Network_t *network,
  Ntk_Node_t *from,
  Ntk_Node_t *to)
{
  SpfdApplData_t *applData;
  st_table *wiresRemoved;
  st_table *sinkTable;
  array_t *oldFanouts,*oldFanins;
  array_t *newFanouts,*newFanins;
  int i;
  Ntk_Node_t *ntkNode;

  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);
  wiresRemoved = applData->wiresRemoved;
  
  assert(network == Ntk_NodeReadNetwork(from));
  assert(network == Ntk_NodeReadNetwork(to));

  oldFanouts = Ntk_NodeReadFanouts(from);
  oldFanins = Ntk_NodeReadFanins(to);

  newFanouts = array_alloc(Ntk_Node_t *,0);
  newFanins = array_alloc(Ntk_Node_t *,0);

  /* Remove 'from' from the fanins of 'to' */
  if (spfdVerbose > 1)
    (void) fprintf(vis_stdout,"** spfd info: Wire ");
  arrayForEachItem(Ntk_Node_t *,oldFanins,i,ntkNode) {
    if (ntkNode != from) {
      array_insert_last(Ntk_Node_t *,newFanins,ntkNode);
    } else {
      if (spfdVerbose > 1)
        (void) fprintf(vis_stdout,"%s --> ",Ntk_NodeReadName(from));
    }
  }
  /* Remove 'to' from the fanouts of 'from' */
  arrayForEachItem(Ntk_Node_t *,oldFanouts,i,ntkNode) {
    if (ntkNode != to) {
      array_insert_last(Ntk_Node_t *,newFanouts,ntkNode);
    } else {
      if (spfdVerbose > 1)
        (void) fprintf(vis_stdout,"%s removed.\n",Ntk_NodeReadName(to));
    }
  }
  
  /* Insert this wire in the wiresRemoved table */
  if (st_lookup(wiresRemoved,(char *)from,&sinkTable)) {
    st_insert(sinkTable,(char *)to,(char *)to);
  } else {
    sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
    st_insert(sinkTable,(char *)to,(char *)to);
    st_insert(wiresRemoved,(char *)from,(char *)sinkTable);
  }
  
  /* Set the new arrays */
  Ntk_NodeSetFanins(to,newFanins);
  Ntk_NodeSetFanouts(from,newFanouts);

  /* The fanin cone is redundant if 'from' had only a single fanout and it is
     not a primary output. */
  if (array_n(newFanouts) == 0 &&
      !Ntk_NodeTestIsPrimaryOutput(from)) {
    array_t *faninArray;
    boolean check;
    faninArray = array_dup(Ntk_NodeReadFanins(from));
    arrayForEachItem(Ntk_Node_t *,faninArray,i,ntkNode) {
      SpfdNetworkRemoveWire(network,ntkNode,from);
      /* Register the wire removed */
      if (st_lookup(wiresRemoved,(char *)ntkNode,&sinkTable)) {
        st_insert(sinkTable,(char *)from,(char *)from);
      } else {
        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
        st_insert(sinkTable,(char *)from,(char *)from);
        st_insert(wiresRemoved,(char *)ntkNode,(char *)sinkTable);
      }
    }
    array_free(faninArray);
    check = Ntk_NodeRemoveFromNetwork(network,from,0,1,0);
    assert(check);
    if (spfdVerbose > 1)
      (void) fprintf(vis_stdout,"** spfd info: Node %s removed.\n",
                     Ntk_NodeReadName(from));    
    st_insert(applData->nodesRemoved,(char *)from,(char *)0);
  }

  spfdNtkChanged = TRUE;
  
  return;
  
} /* End of SpfdNetworkRemoveWire */


void
SpfdNetworkAddWire(
  Ntk_Network_t *network,
  Ntk_Node_t *from,
  Ntk_Node_t *to)
{
  array_t *oldFanouts,*oldFanins;

  assert(network == Ntk_NodeReadNetwork(from));
  assert(network == Ntk_NodeReadNetwork(to));

  oldFanouts = Ntk_NodeReadFanouts(from);
  oldFanins = Ntk_NodeReadFanins(to);

  array_insert_last(Ntk_Node_t *,oldFanouts,to);
  array_insert_last(Ntk_Node_t *,oldFanins,from);

  if (spfdVerbose > 1)
    (void) fprintf(vis_stdout,"** spfd info: Wire %s --> %s added\n",
                   Ntk_NodeReadName(from),Ntk_NodeReadName(to));
  spfdWiresAdded++;
  
  spfdNtkChanged = TRUE;
  
  return;
  
} /* End of SpfdNetworkAddWire */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

static Tbl_Table_t *
BuildNewTable(
  Ntk_Network_t *network,
  Ntk_Node_t *ntkNode,
  mdd_t *mddFunc)
{
  bdd_manager *ddManager = Ntk_NetworkReadMddManager(network);
  SpfdApplData_t *applData;
  st_table *wiresRemoved;
  Tbl_Table_t *table;
  Tbl_Entry_t *entry;
  int i,id,index;
  Ntk_Node_t *loopNode;
  Var_Variable_t *var;
  array_t *faninIdArray,*cube,*nodeArray;
  st_table *faninTable;
  bdd_gen *ddGen;

  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);
  wiresRemoved = applData->wiresRemoved;

  /* Allocaet a Table data structure */
  table = Tbl_TableAlloc();

  /* Find the true support. */
  faninIdArray = mdd_get_support(ddManager,mddFunc);
  faninTable = st_init_table(st_numcmp,st_numhash);
  arrayForEachItem(int,faninIdArray,i,id) {
    st_insert(faninTable,(char *)(long)id,(char *)(long)id);
  }
  array_free(faninIdArray);
  
  /* Delete wires that are not in the support of ntkNode. Collect
     valid fanin ids in the same order as already present in the
     node's original Table data structure. */
  faninIdArray = array_alloc(int,0);
  nodeArray = array_dup(Ntk_NodeReadFanins(ntkNode));
  index = 0;
  arrayForEachItem(Ntk_Node_t *,nodeArray,i,loopNode) {
    id = Ntk_NodeReadMddId(loopNode);
    if (!st_lookup(faninTable,(char *)(long)id,&id)) {
      st_table *sinkTable;

      if (spfdVerbose > 2)
        (void) fprintf(vis_stdout,
                       "** spfd info: removing wire in BuildNewTable.\n");
      SpfdNetworkRemoveWire(network,loopNode,ntkNode);
      /* Insert the wire removed for the purpose of statistics */
      if (st_lookup(wiresRemoved,(char *)loopNode,&sinkTable)) {
        st_insert(sinkTable,(char *)ntkNode,(char *)ntkNode);
      } else {
        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
        st_insert(sinkTable,(char *)ntkNode,(char *)ntkNode);
        st_insert(wiresRemoved,(char *)loopNode,(char *)sinkTable);
      }
    } else {
      var = Ntk_NodeReadVariable(loopNode); 
      array_insert_last(int,faninIdArray,id);
      Tbl_TableSetVar(table,index,var,0);
      index++;
    }
  }
  array_free(nodeArray);
  st_free_table(faninTable);
  
  /* Set the output variable */
  var = Ntk_NodeReadVariable(ntkNode);
  Tbl_TableSetVar(table,0,var,1/*output flag*/);

  /* Set the defaults field to 0 */
  entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
  Tbl_EntrySetValue(entry,0,0);
  Tbl_TableDefaultSetEntry(table,entry,0/*output index */);

  /* Add rows for each cube in the function */
  /* cube is an array of int ids. The length of cube is the size of
     the manager */
  ddGen = bdd_first_cube(mddFunc,&cube);
  /* If the function is zero, just add the zero cube */
  if (bdd_gen_read_status(ddGen) == bdd_EMPTY) {
    array_t *zeroCube;
    int size;

    size = bdd_num_vars(ddManager);
    zeroCube = array_alloc(int,0);
    for (i = 0; i < size; i++) {
      array_insert_last(int,zeroCube,2);
    }
    TableAddCube(table,faninIdArray,zeroCube,0);
    array_free(zeroCube);
  } else {
    do {
      TableAddCube(table,faninIdArray,cube,1);
    } while (bdd_next_cube(ddGen,&cube));
  }  
  bdd_gen_free(ddGen);

  array_free(faninIdArray);

  return table;
} /* End of BuildNewTable */


static void
TableAddCube(
  Tbl_Table_t *table,
  array_t *faninIdArray,
  array_t *cube,
  int value)
{
  int rowIndex,colIndex,numFanins;
  int mddId,phase;
  Tbl_Entry_t *entry;

  numFanins = Tbl_TableReadNumInputs(table);

  /* Fill in the entries for the just added row */
  rowIndex = Tbl_TableAddRow(table);
  for (colIndex = 0; colIndex < numFanins; colIndex++) {
    entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
    mddId = array_fetch(int,faninIdArray,colIndex);
    phase = array_fetch(int,cube,mddId);
    if (phase == 2) {
      Tbl_EntrySetValue(entry,0,1);
    } else {
      Tbl_EntrySetValue(entry,phase,phase);
    }
    Tbl_TableSetEntry(table,entry,rowIndex,colIndex,0/*input flag*/);
  }
  /* Add an entry in the output column */
  entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
  Tbl_EntrySetValue(entry,value,value);
  Tbl_TableSetEntry(table,entry,rowIndex,0,1/*output flag*/);

} /* End of TableAddCube */