src/spfd/spfdOpt.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 int CompareConvexFanoutCountAndDepth(const void *obj1, const void *obj2);
static int CompareConvexSwitchedCapAndDepth(const void *obj1, const void *obj2);

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


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
int
SpfdNetworkOptimize(
  Ntk_Network_t *network,
  char *simFile,
  int percent,
  int frequency,
  int regionDepth)
{
  SpfdApplData_t *applData;
  Ntk_Node_t *node,*maxNode;
  int stop,iter,status;
  float randomValue;
  array_t *nodeArray;
  lsGen gen;
  st_generator *stGen;
  char *dummy;
  boolean replRem;
  array_t *inputArray,*patternArray,*intPatternArray;
  char *optName;
  
  /* To keep the compiler happy */
  inputArray = patternArray = intPatternArray = NIL(array_t);

  /* Check if both wire removal and replacement are to be done */
  optName = Cmd_FlagReadByName("spfd_repl_rem");
  if (optName && (strcmp(optName,"yes") == 0)) {
    replRem = TRUE;
  } else {
    replRem = FALSE;
  }

  /* First initialize the simulation package. This will also levelize
     the nodes in the network. The level info is stored in local data
     structure of 'truesim' package'. This is needed even if we do not
     perform vector simulation. */
  Truesim_InitializeSimulation(network,NIL(char),0,-1,0,NIL(st_table));
  if (spfdPerfSim) { /* Perform simulation? */
    /* Array of primary input nodes */
    inputArray = array_alloc(Ntk_Node_t *,0);
    /* Array of simulation vectors */
    patternArray = array_alloc(char *,0);
    status = Truesim_ReadSimulationVectors(network,simFile,
                                           inputArray,patternArray);
    /* Error while reading simulation vectors */
    if (!status) {
      array_free(inputArray);
      array_free(patternArray);
      (void) fprintf(vis_stdout, "** spfd error: Error reading simulation"
                     " vector file. \n");
      return 0;
    }
    Truesim_ZeroDelayPatternSimulate(network,inputArray,patternArray);

    /* Select a random start for the set of internal simulation
       vectors. We simulate only a portion of vectors (during
       optimization iterations) to get a coarse estimate of circuit
       node switching activities. */
    randomValue = ((double)util_random()/(double)(MODULUS1 - 2));
    if (randomValue > (double) (1.0 - ((double)percent)/((double)100)))
      randomValue = (1.0 - ((double)percent)/((double)100))/2.0;
    /* Partial set of simulation vectors */
    intPatternArray = SpfdFetchInternalPatternArray(patternArray,percent,
                                                    randomValue);
  }
  
  /* Initialize the package application data structure */
  applData = SpfdInitializeApplData(network);
  iter = 1;

  do {
    if (spfdVerbose > 2) {
      (void) fprintf(vis_stdout, "** spfd info: Iteration %d\n",iter);
    }
    nodeArray = array_alloc(Ntk_Node_t *,0);

    /* Collect circuit nodes, later needed to be sorted. Only the
       internal nodes will be sorted.*/
    switch (spfdMethod) {
    case REDUCE_FANIN_WIRES:
    case OPTIMIZE_MAX_NODE:
      Ntk_NetworkForEachNode(network,gen,node) {
        if (!Ntk_NodeTestIsPrimaryOutput(node) &&
            !Ntk_NodeTestIsPrimaryInput(node) &&
            !SpfdNodeReadLocked(applData,node)) 
          array_insert_last(Ntk_Node_t *,nodeArray,node);
      }
      break;
    case OPTIMIZE_FANIN_NODES:
      Ntk_NetworkForEachNode(network,gen,node) {
        if (!Ntk_NodeTestIsPrimaryInput(node) &&
            !SpfdNodeReadLocked(applData,node)) 
          array_insert_last(Ntk_Node_t *,nodeArray,node);
      }
      break;
    case REDUCE_FANOUT_WIRES:
      Ntk_NetworkForEachNode(network,gen,node) {
        if (!SpfdNodeReadLocked(applData,node)) 
          array_insert_last(Ntk_Node_t *,nodeArray,node);
      }
      break;
    }
    
    /* Find the node with max. fanout/switched cap., or a random node */
    maxNode = SpfdFindNode(network,nodeArray);
    if (!maxNode)
      stop = 1;
    else 
      stop = 0;
    array_free(nodeArray);
    
    /* Optimize. */
    if (!stop) {
      switch (spfdMethod) {
      case REDUCE_FANIN_WIRES:
        SpfdOptimizeFaninWires(network,maxNode,regionDepth,replRem);
        break;
      case OPTIMIZE_MAX_NODE:
        SpfdOptimizeNode(network,maxNode,regionDepth);
        break;
      case OPTIMIZE_FANIN_NODES:
        SpfdOptimizeFaninNodes(network,maxNode,regionDepth);
        break;
      case REDUCE_FANOUT_WIRES:
        SpfdOptimizeFanoutWires(network,maxNode,regionDepth,replRem);
        break;
      }
      /* If the network has changed (structurally), update the depth
         information to reflect the change in the network.*/
      if (spfdNtkChanged) {
        Truesim_NetworkUpdateNodeTopologicalDepth(network);
        spfdNtkChanged = FALSE;
      }
      if (spfdPerfSim && (iter % frequency == 0)) {
        Truesim_ZeroDelayPatternSimulate(network,inputArray,intPatternArray);
      }
    }
    iter++;
  } while (!stop);
  
  if (spfdPerfSim) {
    /* End simulation; free memory */
    Truesim_QuitSimulation(network);
    array_free(inputArray);
    array_free(patternArray);
  }
  
  /* Print the number of wires removed and delete the sinkTable. */
  fprintf(vis_stdout,"** spfd info: # of wires removed = %d\n",
          spfdNumWiresRem - spfdWiresAdded);
  fprintf(vis_stdout,"** spfd info: # of nodes removed = %d\n",
          st_count(applData->nodesRemoved));

  /* Free the memory for each node */
  st_foreach_item(applData->nodesRemoved,stGen,&node,&dummy) {
    if (node) Ntk_NodeFree(node);
  }
  
  return 1;
  
} /* End of SpfdNetworkOptimize */

#if 0

void
SpfdProcessFanoutWires(
  Ntk_Network_t *network,
  Ntk_Node_t *maxNode,
  int regionDepth,
  boolean replRem)
{
  SpfdApplData_t *applData;
  array_t *fanoutArray,*replArray;
  st_table *wiresRemoved,*sinkTable;
  st_generator *stGen;
  Ntk_Node_t *ntkNode,*tempNode,*replNode;
  int i,num;

  /* Package application data structure */
  applData = Ntk_NetworkReadApplInfo(network,SPFD_NETWORK_APPL_KEY);

  fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode));
  for (i = array_n(fanoutArray) - 1; i >=0; i--) {
    ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i);
    
    /* Skip POs */
    if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
      continue;

    /* Could be removed during an earlier iteration */
    if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,NIL(char *))) {
      array_t *regionArray;
  
      /* regionArray is an array of nodes sorted according to their depth. */
      regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);

      /* Analyze region's BDD requirements */
      SpfdComputeRequiredGlobalBdds(network,applData);

      /* Analyze auxilarry BDD ID requirements */
      SpfdAllocateOrReuseAuxVariables(network,applData);

      /* Order the fanin of internal and boundary nodes */
      if (spfdPerfSim) {
        SpfdOrderFaninOfRegionNodes(network,applData,
                                    SpfdSwitchedCapAndDepthCompare);
      } else {
        SpfdOrderFaninOfRegionNodes(network,applData,
                                    SpfdFanoutCountAndDepthCompare);
      }
    
      /* Set the spfds for nodes in the region. The spfds are reduced to a
         single pair and the localAlt is set to one of the components of the
         single pair SPFD. */
      SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);

      /* Now check if the spfd of wire maxNode --> ntkNode is
         empty. Remove the spfd of ntkNode as it was not deleted in
         SpfdRegionComputeSinglePairSpfd */
      /* Compute array of potential candidates for replacement */
      if (replRem)
        replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth);
      else
        replArray = NIL(array_t);
      replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData,
                                                         maxNode,ntkNode,
                                                         replArray);
      /* No longer needed. */
      SpfdNodeDeleteSpfd(applData,ntkNode);
      if (replArray)
        array_free(replArray);
      
      /* Check to see if wires have been found to be
         redundant/replaceable. If no wires are to be
         removed/replaced, then decide whether or not to reprogram. */
      if (st_count(applData->currWireTable) == 0 &&
          st_count(applData->currReplaceTable) == 0 &&
          !spfdReprogNoWire) {
        /* In this case just clean up currBddReq, localAlt
           and globalAlt. */
        st_table *currBddReq;
        st_generator *stGen;
        Ntk_Node_t *regNode;
        bdd_node *bdd1;
        bdd_manager *ddManager;
        int j;

        ddManager = applData->ddManager;
        currBddReq = applData->currBddReq;
        
        /* Clean up currBddReq */
        st_foreach_item(currBddReq,stGen,(char **)&regNode,(char **)&bdd1) {
          bdd_recursive_deref(ddManager,bdd1);
        }
        st_free_table(currBddReq);
        applData->currBddReq = NIL(st_table);

        /* Clean up localAlt and globalAlt of region nodes */
        arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
          SpfdNodeDeleteGlobalAlternative(applData,regNode);
          SpfdNodeDeleteLocalAlt(applData,regNode);
        }
      } else {
        /* Now reprogram the nodes in the region. */
        SpfdReprogramRegionNodes(network,applData,regionArray);
      }

      /* In this subroutine we have only a single wire
         replaced. Delete just that data */
      if (replNode) {
        SpfdNodeDeleteGlobalAlternative(applData,replNode);
        SpfdNodeSetAuxId(applData,replNode,-1);
        st_delete(applData->currReplaceTable,(char **)&ntkNode,
                  (char **)&sinkTable);
        st_free_table(sinkTable);
        
        /* A small caveat: sometimes a wire added can be later
           removed. Check if the replNode --> ntkNode still exists. If
           not set replNode to NULL. */
        wiresRemoved = applData->wiresRemoved;
        if (st_lookup(wiresRemoved,(char *)replNode,(char **)&sinkTable) &&
            st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) {
          /* Reduce the number of wires added and delete
             replNode->ntkNode from wiresRemoved table */
          spfdWiresAdded--;
          st_delete(sinkTable,(char **)&ntkNode,NIL(char *));
          if (st_count(sinkTable) < 1) {
            st_delete(wiresRemoved,(char **)&replNode,(char **)&sinkTable);
            st_free_table(sinkTable);
          }
          replNode = NIL(Ntk_Node_t);
        }
      }
      
      /* Clean up auxIds and piAltVars*/
      SpfdCleanUpAuxIds(applData);
      
      /* Free stuff used only for the current iteration */
      if (applData->currXCube) {
        bdd_recursive_deref(applData->ddManager,applData->currXCube);
        applData->currXCube = NIL(bdd_node);
      }
      if (applData->currRegionNodes) {
        st_free_table(applData->currRegionNodes);
        applData->currRegionNodes = NIL(st_table);
      }
      if (applData->currInUseVars) {
        st_free_table(applData->currInUseVars);
        applData->currInUseVars = NIL(st_table);
      }

      num = st_count(applData->currWireTable);
      assert(num == 0);

      num = st_count(applData->currReplaceTable);
      assert(num == 0);
      
      /* Update the total number of wires removed */
      wiresRemoved = applData->wiresRemoved;
      if (st_count(wiresRemoved) > 0) {
        st_foreach_item(wiresRemoved,stGen,(char **)&tempNode,
                        (char **)&sinkTable){
          spfdNumWiresRem += st_count(sinkTable);
        }
        
        /* free the wiresRemoved contents */
        st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
      }
      
      /* Free regionArray (cluster) */
      array_free(regionArray);
    }
  }
  array_free(fanoutArray);
  
  /* Lock the node */
  SpfdNodeSetLocked(applData,maxNode,TRUE);
  
} /* End of SpfdProcessFanoutWires */
#endif

Ntk_Node_t *
SpfdCheckIfWireIsRedundantOrReplaceable(
  Ntk_Network_t *network,
  SpfdApplData_t *applData,
  Ntk_Node_t *from,
  Ntk_Node_t *to,
  array_t *replaceArray)
{
  bdd_manager *ddManager = applData->ddManager;
  bdd_node *result,*ddTemp,*ddTemp2,*var,*varAux;
  bdd_node *toSpfd,*wireSpfd,*logicZero;
  int i,index;
  Ntk_Node_t *fanin,*tempNode,*replNode;
  st_table *wireTable = applData->currWireTable;
  st_table *wiresRemoved = applData->wiresRemoved;
  st_table *sinkTable;

  /* Possible replacement node */
  replNode = NIL(Ntk_Node_t);
  logicZero = bdd_read_logic_zero(ddManager);

  /* Check if this wire has already been removed. */
  if (!(st_lookup(wiresRemoved,(char *)from,&sinkTable) &&
      st_lookup(sinkTable,(char *)to,&tempNode))) {
  
    bdd_ref(result = bdd_read_one(ddManager));

    /* Compute the characteristic function of pairs of minterms cannot
       be distinguished any fanin of 'to'. Let f_i be the ith fanin of
       'to'. We compute result = \prod f_i == f'_i, where f_i != from */
    Ntk_NodeForEachFanin(to,i,fanin) {
      var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin));
      index = SpfdNodeReadAuxId(applData,fanin);
      varAux = bdd_bdd_ith_var(ddManager,index);
      
      if (fanin != from) {
        bdd_ref(ddTemp = bdd_bdd_xnor(ddManager,var,varAux)); /* XNOR */
        bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp));
        bdd_recursive_deref(ddManager,result);
        bdd_recursive_deref(ddManager,ddTemp);
        result = ddTemp2;
      }
    }
    /* Finally put in f_i == f_i', where f_i = from) */
    var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(from));
    index = SpfdNodeReadAuxId(applData,from);
    varAux = bdd_bdd_ith_var(ddManager,index);
    bdd_ref(ddTemp = bdd_bdd_xor(ddManager,var,varAux));
    bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp));
    bdd_recursive_deref(ddManager,result);
    bdd_recursive_deref(ddManager,ddTemp);
    result = ddTemp2;

    /* Compute AND of result and the SPFD of 'to'. */
    toSpfd = SpfdNodeReadSpfd(applData,to);
    if (toSpfd == NIL(bdd_node)) {
      (void) fprintf(vis_stderr,
                     "** spfd error: Spfd expected but not found.\n");
      exit(0);
    }
    bdd_ref(wireSpfd = bdd_bdd_and(ddManager,toSpfd,result));
    bdd_recursive_deref(ddManager,result);

    if (wireSpfd == logicZero) { /* Can the wire be removed? */
      if (spfdVerbose > 1)
        (void) fprintf(vis_stdout,
                       "** spfd info: Target wire %s --> %s has empty spfd.\n",
                       Ntk_NodeReadName(from),Ntk_NodeReadName(to));

      /* Insert the wire into wireTable */
      if (st_lookup(wireTable,(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(wireTable,(char *)from,(char *)sinkTable);
      }
      bdd_recursive_deref(ddManager,wireSpfd);
    } else if (replaceArray != NIL(array_t)) {
      /* Try for replacement. Exit after finding the first one. Here the
         assumption is that the nodes are sorted according to some
         criterion. */
      replNode = SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(network,replaceArray,
                                                           from,to,wireSpfd);
      bdd_recursive_deref(ddManager,wireSpfd);
    } else {
      bdd_recursive_deref(ddManager,wireSpfd);
    }
  }
  
  return replNode;
  
} /* End of SpfdCheckIfWireIsRedundantOrReplaceable */


Ntk_Node_t *
SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(
  Ntk_Network_t *network,
  array_t *replaceArray,
  Ntk_Node_t *from,
  Ntk_Node_t *to,
  bdd_node *wireSpfd)
{
  SpfdApplData_t *applData;
  bdd_manager *ddManager;
  st_table *leavesTable,*inUseVars,*replaceTable;
  st_table *sinkTable,*currBddReq;
  bdd_t *mddOne;
  lsGen gen;
  Ntk_Node_t *fanin,*node,*replNode;
  Ntk_Node_t *foundNode;
  array_t *nodeMvfs,*nodeBdds;
  bdd_node *bdd1,*xCube,*yVar;
  bdd_node **tempVars,**firstCompose,**secondCompose;
  bdd_node *step1,*step2,*step3,*step4,*step5;
  bdd_node *logicZero;
  int i,j,size,replId,id,auxId;
  
  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);
  ddManager = applData->ddManager;
  inUseVars = applData->currInUseVars;
  replaceTable = applData->currReplaceTable;
  currBddReq = applData->currBddReq;
  
  mddOne = bdd_one(ddManager);
  logicZero = bdd_read_logic_zero(ddManager);
  
  /* Collect the leaf nodes of the network. */
  leavesTable = st_init_table(st_ptrcmp, st_ptrhash);
  Ntk_NetworkForEachCombInput(network,gen,node) {
    st_insert(leavesTable,(char *)node,(char *) -1);
  }

  /* Compute the global MVFs of the nodes in replaceArray */
  nodeMvfs = Ntm_NetworkBuildMvfs(network,replaceArray,leavesTable,mddOne);
  bdd_free(mddOne);
  st_free_table(leavesTable);

  /* Collect node global Bdds */
  nodeBdds = array_alloc(bdd_node *,0);
  arrayForEachItem(Ntk_Node_t *,replaceArray,i,node) {
    Mvf_Function_t *mvf;
    mvf = array_fetch(Mvf_Function_t *,nodeMvfs,i);
    bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1));
    bdd_ref(bdd1);
    array_insert_last(bdd_node *,nodeBdds,bdd1);
  }
  Mvf_FunctionArrayFree(nodeMvfs);

  /* Now check one at a time if global function satisfies wireSpfd */
  foundNode = NIL(Ntk_Node_t);
  xCube = applData->currXCube;
  arrayForEachItem(Ntk_Node_t *,nodeBdds,i,bdd1) {
    int idAllocated;

    idAllocated = 0;
    replNode = array_fetch(Ntk_Node_t *,replaceArray,i);
    replId = Ntk_NodeReadMddId(replNode);
    /* Check if replId is already in use. This is possible is outside
       the cluster. */
    if (st_lookup(inUseVars,(char *)(long)replId,NIL(char *))) {
      /* Allocate yVar and yAuxVar for replNode */
      tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1);
      yVar = tempVars[0];
      idAllocated = 1;
      FREE(tempVars);
    } else { /* replId not in use */
      yVar = bdd_bdd_ith_var(ddManager,replId);
    }

    /* Now perform the following steps, using two compositions. */
    /* 1. step1 = yVar == bdd1
       2. step2 = wireSpfd(Y,Y') --> wireSpfd(x,Y')
       3. step3 = \exists_x step1 * step2
       4. step4 = step3(yVar,Y') --> step3(yVar,x)
       5. step5 = \exists_x step1 * step4

       If step5 == logicZero, then replNode is a candidate */

    /* Prepare compose arrays for the above steps */
    size = bdd_num_vars(ddManager);
    firstCompose = ALLOC(bdd_node *,size);
    secondCompose = ALLOC(bdd_node *,size);
    for (j = 0; j < size; j++) {
      firstCompose[j] = bdd_bdd_ith_var(ddManager,j);
      secondCompose[j] = bdd_bdd_ith_var(ddManager,j);
    }

    Ntk_NodeForEachFanin(to,j,fanin) {
      id = Ntk_NodeReadMddId(fanin);
      auxId = SpfdNodeReadAuxId(applData,fanin);
      st_lookup(currBddReq,(char *)fanin,(char **)&firstCompose[id]);
      secondCompose[auxId] = firstCompose[id];
    }

    bdd_ref(step1 = bdd_bdd_xnor(ddManager,yVar,bdd1));
    bdd_ref(step2 = bdd_bdd_vector_compose(ddManager,wireSpfd,firstCompose));
    FREE(firstCompose);
    bdd_ref(step3 = bdd_bdd_and_abstract(ddManager,step1,step2,xCube));
    bdd_recursive_deref(ddManager,step2);
    bdd_ref(step4 = bdd_bdd_vector_compose(ddManager,step3,secondCompose));
    bdd_recursive_deref(ddManager,step3);
    FREE(secondCompose);
    bdd_ref(step5 = bdd_bdd_and_abstract(ddManager,step1,step4,xCube));
    bdd_recursive_deref(ddManager,step4);
    bdd_recursive_deref(ddManager,step1);

    /* Now if step5 is zero, then return replNode as the candidate. I will use
       the globalAlt field of the node to store the global BDD. This way I
       don't have to recompute the global BDD later.  */
    if (step5 == logicZero) {
      bdd_recursive_deref(ddManager,step5);
      bdd_ref(bdd1);
      SpfdNodeSetGlobalAlternative(applData,replNode,bdd1);

      /* Allocate an auxId for this node. It will be needed during
         reprogramming. */
      if (idAllocated) {
        auxId = bdd_node_read_index(yVar);
      } else {
        tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1);
        auxId = bdd_node_read_index(tempVars[0]);
        FREE(tempVars);
      }
      SpfdNodeSetAuxId(applData,replNode,auxId);
      st_insert(inUseVars,(char *)(long)replId,(char *)-1);
      st_insert(inUseVars,(char *)(long)auxId,(char *)-1);
      
      /* Insert information in replaceTable */
      if (st_lookup(replaceTable,(char *)to,&sinkTable)) {
        st_insert(sinkTable,(char *)from,(char *)replNode);
      } else {
        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
        st_insert(sinkTable,(char *)from,(char *)replNode);
        st_insert(replaceTable,(char *)to,(char *)sinkTable);
      }
      foundNode = replNode;
      break;
    } else {
      bdd_recursive_deref(ddManager,step5);
      /* release the id */
      if (idAllocated) {
        id = bdd_node_read_index(yVar);
        st_delete(inUseVars, &id, NIL(char *));
      }
    }
  }

  /* Free the nodeBdds */
  arrayForEachItem(bdd_node *,nodeBdds,i,bdd1) {
    bdd_recursive_deref(ddManager,bdd1);
  }
  array_free(nodeBdds);

  return foundNode;
} /* End of SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd */


void
SpfdOptimizeFaninWires(
  Ntk_Network_t *network,
  Ntk_Node_t *maxNode,
  int regionDepth,
  boolean replRem)
{
  SpfdApplData_t *applData;
  array_t *faninArray;
  Ntk_Node_t *ntkNode,*fanout;
  char *dummy;
  int i,j;

  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);
  
  /* replace/remove the fanin wire of maxNode one at a time. The fanin
     node with higher switched capacitance will be optimized first. */
  faninArray = array_dup(Ntk_NodeReadFanins(maxNode));
  if (spfdPerfSim)
    array_sort(faninArray,CompareConvexSwitchedCapAndDepth);
  else
    array_sort(faninArray,CompareConvexFanoutCountAndDepth);

  for (i = array_n(faninArray) - 1; i >=0; i--) {
    boolean skip;
    ntkNode = array_fetch(Ntk_Node_t *,faninArray,i);
    if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) {
      skip = TRUE;
      /* Check if the current fanin node is still in the support of
         maxNode. */
      Ntk_NodeForEachFanout(ntkNode,j,fanout) {
        if (fanout == maxNode) {
          skip = FALSE;
          break;
        }
      }
    } else {
      skip = TRUE;
    }
    if (!skip)
      SpfdOptimizeWire(network,ntkNode,maxNode,regionDepth,replRem);
  }
  array_free(faninArray);

  /* Lock the node */
  SpfdNodeSetLocked(applData,maxNode,TRUE);
  
  return ;
  
} /* End of SpfdOptimizeFaninWires */


void
SpfdOptimizeFanoutWires(
  Ntk_Network_t *network,
  Ntk_Node_t *maxNode,
  int regionDepth,
  boolean replRem)
{
  SpfdApplData_t *applData;
  array_t *fanoutArray;
  Ntk_Node_t *ntkNode,*fanout;
  int i,j;
  
  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);

  /* replace/remove the fanout wires of maxNode one at a time. The fanout
     node with higher switched capacitance will be optimized first. */
  fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode));
  if (spfdPerfSim)
    array_sort(fanoutArray,CompareConvexSwitchedCapAndDepth);
  else
    array_sort(fanoutArray,CompareConvexFanoutCountAndDepth);


  for (i = array_n(fanoutArray) - 1; i >=0; i--) {
    boolean skip;
    ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i);
    skip = TRUE;
    /* Check if the maxNode is still in the support of fanout. */
    Ntk_NodeForEachFanout(maxNode,j,fanout) {
      if (fanout == ntkNode) {
        skip = FALSE;
        break;
      }
    }
    if (!skip)    
      SpfdOptimizeWire(network,maxNode,ntkNode,regionDepth,replRem);
  }
  array_free(fanoutArray);

  /* Lock the node */
  SpfdNodeSetLocked(applData,maxNode,TRUE);
  
  return ;
  
} /* End of SpfdOptimizeFanoutWires */


void
SpfdOptimizeFaninNodes(
  Ntk_Network_t *network,
  Ntk_Node_t *maxNode,
  int regionDepth)
{
  SpfdApplData_t *applData;
  array_t *faninArray;
  Ntk_Node_t *ntkNode;
  char *dummy;
  int i;

  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);

  /* Optimize fanin nodes one at a time. The fanin node with higher
     switched capacitance will be optimized first. */
  faninArray = array_dup(Ntk_NodeReadFanins(maxNode));
  if (spfdPerfSim)
    array_sort(faninArray,CompareConvexSwitchedCapAndDepth);
  else
    array_sort(faninArray,CompareConvexFanoutCountAndDepth);

  for (i = array_n(faninArray) - 1; i >=0; i--) {
    boolean skip = FALSE;
    ntkNode = array_fetch(Ntk_Node_t *,faninArray,i);
    if (st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) {
      skip = TRUE;
    }
    if (!skip)
      SpfdOptimizeNode(network,ntkNode,regionDepth);
  }
  array_free(faninArray);

  /* Lock the node */
  SpfdNodeSetLocked(applData,maxNode,TRUE);
  
  return ;
  
} /* End of SpfdOptimizeFaninNodes */


void
SpfdOptimizeWire(
  Ntk_Network_t *network,
  Ntk_Node_t *maxNode,
  Ntk_Node_t *ntkNode,
  int regionDepth,
  boolean replRem)
{
  SpfdApplData_t *applData;
  array_t *replArray;
  st_table *wiresRemoved,*sinkTable;
  st_generator *stGen;
  Ntk_Node_t *tempNode,*replNode;
  array_t *regionArray;
  int num;

  /* Package application data structure */
  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);

  /* Skip POs */
  if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
    return;
  
  /* regionArray is an array of nodes sorted according to their depth. */
  regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);

  /* Analyze region's BDD requirements */
  SpfdComputeRequiredGlobalBdds(network,applData);
  
  /* Analyze auxilarry BDD ID requirements */
  SpfdAllocateOrReuseAuxVariables(network,applData);
  
  /* Order the fanin of internal and boundary nodes */
  if (spfdPerfSim) {
    SpfdOrderFaninOfRegionNodes(network,applData,
                                SpfdSwitchedCapAndDepthCompare);
  } else {
    SpfdOrderFaninOfRegionNodes(network,applData,
                                SpfdFanoutCountAndDepthCompare);
  }
    
  /* Set the spfds for nodes in the region. The spfds are reduced to a
     single pair and the localAlt is set to one of the components of the
     single pair SPFD. */
  SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
  
  /* Now check if the spfd of wire maxNode --> ntkNode is
     empty. Remove the spfd of ntkNode as it was not deleted in
     SpfdRegionComputeSinglePairSpfd */
  /* Compute array of potential candidates for replacement */
  if (replRem)
    replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth);
  else
    replArray = NIL(array_t);
  replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData,
                                                     maxNode,ntkNode,
                                                     replArray);
  /* SPFD of ntkNode is no longer needed. */
  SpfdNodeDeleteSpfd(applData,ntkNode);
  if (replArray)
    array_free(replArray);
      
  /* Check to see if wires have been found to be
     redundant/replaceable. If no wires are to be
     removed/replaced, then decide whether or not to reprogram. */
  if (st_count(applData->currWireTable) == 0 &&
      st_count(applData->currReplaceTable) == 0 &&
      !spfdReprogNoWire) {
    /* In this case just clean up currBddReq, localAlt
       and globalAlt. */
    st_table *currBddReq;
    st_generator *stGen;
    Ntk_Node_t *regNode;
    bdd_node *bdd1;
    bdd_manager *ddManager;
    int j;
    
    ddManager = applData->ddManager;
    currBddReq = applData->currBddReq;
    
    /* Clean up currBddReq */
    st_foreach_item(currBddReq,stGen,&regNode,&bdd1) {
      bdd_recursive_deref(ddManager,bdd1);
    }
    st_free_table(currBddReq);
    applData->currBddReq = NIL(st_table);
    
    /* Clean up localAlt and globalAlt of region nodes */
    arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
      SpfdNodeDeleteGlobalAlternative(applData,regNode);
      SpfdNodeDeleteLocalAlt(applData,regNode);
    }
  } else {
    /* Now reprogram the nodes in the region. */
    SpfdReprogramRegionNodes(network,applData,regionArray);
  }
  
  /* In this subroutine we have only a single wire
     replaced. Delete just that data */
  if (replNode) {
    SpfdNodeDeleteGlobalAlternative(applData,replNode);
    SpfdNodeSetAuxId(applData,replNode,-1);
    st_delete(applData->currReplaceTable,&ntkNode,
              &sinkTable);
    st_free_table(sinkTable);
    
    /* A small caveat: sometimes a wire added can be later
       removed. Check if the replNode --> ntkNode still exists. If
       not set replNode to NULL. */
    wiresRemoved = applData->wiresRemoved;
    if (st_lookup(wiresRemoved,(char *)replNode,&sinkTable) &&
        st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) {
      /* Reduce the number of wires added and delete
         replNode->ntkNode from wiresRemoved table */
      spfdWiresAdded--;
      st_delete(sinkTable,&ntkNode,NIL(char *));
      if (st_count(sinkTable) < 1) {
        st_delete(wiresRemoved,&replNode,&sinkTable);
        st_free_table(sinkTable);
      }
      replNode = NIL(Ntk_Node_t);
    }
  }
      
  /* Clean up auxIds and piAltVars*/
  SpfdCleanUpAuxIds(applData);
  
  /* Free stuff used only for the current wire */
  if (applData->currXCube) {
    bdd_recursive_deref(applData->ddManager,applData->currXCube);
    applData->currXCube = NIL(bdd_node);
  }
  if (applData->currRegionNodes) {
    st_free_table(applData->currRegionNodes);
    applData->currRegionNodes = NIL(st_table);
  }
  if (applData->currInUseVars) {
    st_free_table(applData->currInUseVars);
    applData->currInUseVars = NIL(st_table);
  }
  
  num = st_count(applData->currWireTable);
  assert(num == 0);
  
  num = st_count(applData->currReplaceTable);
  assert(num == 0);
  
  /* Update the total number of wires removed. */
  wiresRemoved = applData->wiresRemoved;
  if (st_count(wiresRemoved) > 0) {
    st_foreach_item(wiresRemoved,stGen,&tempNode,
                    &sinkTable){
      spfdNumWiresRem += st_count(sinkTable);
    }
    
    /* free the wiresRemoved contents */
    st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
  }
  
  /* Free regionArray (cluster) */
  array_free(regionArray);
  
  return ;
  
} /* End of SpfdOptimizeWire */


void
SpfdOptimizeNode(
  Ntk_Network_t *network,
  Ntk_Node_t *ntkNode,
  int regionDepth)
{
  SpfdApplData_t *applData;
  st_table *wiresRemoved,*sinkTable;
  st_generator *stGen;
  Ntk_Node_t *tempNode;
  array_t *regionArray;
  int num;

  /* Package application data structure */
  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);

  /* Skip POs */
  if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
    return;
  
  /* regionArray is an array of nodes sorted according to their depth. */
  regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);

  /* Analyze region's BDD requirements */
  SpfdComputeRequiredGlobalBdds(network,applData);
  
  /* Analyze auxilarry BDD ID requirements */
  SpfdAllocateOrReuseAuxVariables(network,applData);
  
  /* Order the fanin of internal and boundary nodes */
  if (spfdPerfSim) {
    SpfdOrderFaninOfRegionNodes(network,applData,
                                SpfdSwitchedCapAndDepthCompare);
  } else {
    SpfdOrderFaninOfRegionNodes(network,applData,
                                SpfdFanoutCountAndDepthCompare);
  }
    
  /* Set the spfds for nodes in the region. The spfds are reduced to a
     single pair and the localAlt is set to one of the components of the
     single pair SPFD. */
  SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
  
  /* Remove the spfd of ntkNode as it was not deleted in
     SpfdRegionComputeSinglePairSpfd */

  /* SPFD of ntkNode is no longer needed. */
  SpfdNodeDeleteSpfd(applData,ntkNode);
      
  /* Check to see if wires have been found to be
     redundant/replaceable. If no wires are to be
     removed/replaced, then decide whether or not to reprogram. */
  if (st_count(applData->currWireTable) == 0 &&
      !spfdReprogNoWire) {
    /* In this case just clean up currBddReq, localAlt and
       globalAlt. */
    st_table *currBddReq;
    st_generator *stGen;
    Ntk_Node_t *regNode;
    bdd_node *bdd1;
    bdd_manager *ddManager;
    int j;
    
    ddManager = applData->ddManager;
    currBddReq = applData->currBddReq;
    
    /* Clean up currBddReq */
    st_foreach_item(currBddReq,stGen,&regNode,&bdd1) {
      bdd_recursive_deref(ddManager,bdd1);
    }
    st_free_table(currBddReq);
    applData->currBddReq = NIL(st_table);
    
    /* Clean up localAlt and globalAlt of region nodes */
    arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
      SpfdNodeDeleteGlobalAlternative(applData,regNode);
      SpfdNodeDeleteLocalAlt(applData,regNode);
    }
  } else {
    /* Now reprogram the nodes in the region. */
    SpfdReprogramRegionNodes(network,applData,regionArray);
  }
  
  /* Clean up auxIds and piAltVars*/
  SpfdCleanUpAuxIds(applData);
  
  /* Free stuff used only for the current wire */
  if (applData->currXCube) {
    bdd_recursive_deref(applData->ddManager,applData->currXCube);
    applData->currXCube = NIL(bdd_node);
  }
  if (applData->currRegionNodes) {
    st_free_table(applData->currRegionNodes);
    applData->currRegionNodes = NIL(st_table);
  }
  if (applData->currInUseVars) {
    st_free_table(applData->currInUseVars);
    applData->currInUseVars = NIL(st_table);
  }
  
  num = st_count(applData->currWireTable);
  assert(num == 0);
  
  num = st_count(applData->currReplaceTable);
  assert(num == 0);
  
  /* Update the total number of wires removed */
  wiresRemoved = applData->wiresRemoved;
  if (st_count(wiresRemoved) > 0) {
    st_foreach_item(wiresRemoved,stGen,&tempNode,
                    &sinkTable){
      spfdNumWiresRem += st_count(sinkTable);
    }
    
    /* free the wiresRemoved contents */
    st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
  }
  
  /* Free regionArray (cluster) */
  array_free(regionArray);
  
  /* Lock the node */
  SpfdNodeSetLocked(applData,ntkNode,TRUE);

  return ;
  
} /* End of SpfdOptimizeNode */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/
static int
CompareConvexFanoutCountAndDepth(
  const void *obj1,
  const void *obj2)
{
  Ntk_Node_t *node1,*node2;
  Ntk_Network_t *network;
  float weight1,weight2;
  float load1,load2;
  int depth1,depth2;
  
  node1 = *(Ntk_Node_t **)obj1;
  node2 = *(Ntk_Node_t **)obj2;
  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
  network = Ntk_NodeReadNetwork(node1);

  if (Ntk_NodeTestIsPrimaryOutput(node1) ||
      Ntk_NodeTestIsPrimaryInput(node1)) {
    weight1 = -1.0;
  } else {
    load1 = Ntk_NodeReadNumFanouts(node1);
    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
    weight1 = spfdAlpha * load1 + (1.0-spfdAlpha)*depth1;
  }

  if (Ntk_NodeTestIsPrimaryOutput(node2) ||
      Ntk_NodeTestIsPrimaryInput(node2)) {
    weight2 = -1.0;
  } else {
    load2 = Ntk_NodeReadNumFanouts(node2);
    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
    weight2 = spfdAlpha * load2 + (1.0-spfdAlpha)*depth2;
  }
  
  if (weight1 > weight2)
    return -1;
  else if (weight1 == weight2)
    return 0;
  else
    return 1;

} /* End of CompareConvexFanoutCountAndDepth */


static int
CompareConvexSwitchedCapAndDepth(
  const void *obj1,
  const void *obj2)
{
  Ntk_Node_t *node1,*node2;
  Ntk_Network_t *network;
  float weight1,weight2;
  float switch1,switch2;
  float load1,load2;
  int depth1,depth2;
  
  node1 = *(Ntk_Node_t **)obj1;
  node2 = *(Ntk_Node_t **)obj2;
  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
  network = Ntk_NodeReadNetwork(node1);

  if (Ntk_NodeTestIsPrimaryOutput(node1) ||
      Ntk_NodeTestIsPrimaryInput(node1)) {
    weight1 = -1.0;
  } else {
    switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
    load1 = Truesim_NetworkReadNodeLoad(network,node1);
    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
    weight1 = spfdAlpha * load1 * switch1 + (1.0-spfdAlpha)*depth1;
  }

  if (Ntk_NodeTestIsPrimaryOutput(node2) ||
      Ntk_NodeTestIsPrimaryInput(node2)) {
    weight2 = -1.0;
  } else {
    switch2 = Truesim_NetworkReadNodeSwitchingProb(network,node2);
    load2 = Truesim_NetworkReadNodeLoad(network,node2);
    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
    weight2 = spfdAlpha * load2 * switch2 + (1.0-spfdAlpha)*depth2;
  }
  
  if (weight1 > weight2)
    return -1;
  else if (weight1 == weight2)
    return 0;
  else
    return 1;

} /* End of CompareConvexSwitchedCapAndDepth */