source: vis_dev/vis-2.3/src/spfd/spfdOpt.c @ 84

/**CFile***********************************************************************

  FileName    [spfdOpt.c]

  PackageName [spfd]

  Synopsis [Routines that implement spfd_pilo.]

  Description [Routines that implement spfd_pilo.]

  SeeAlso     [spfdCmd.c spfdReg.c spfdProg.c]

  Author      [Balakrishna Kumthekar]

  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.]

******************************************************************************/

#include "spfdInt.h"

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


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


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


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


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


/**AutomaticStart*************************************************************/

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

static int CompareConvexFanoutCountAndDepth(const void *obj1, const void *obj2);
static int CompareConvexSwitchedCapAndDepth(const void *obj1, const void *obj2);

/**AutomaticEnd***************************************************************/


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


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************

  Synopsis [Optimize the network by performing wire/node removal, wire
  replacement and LUT reprogramming to reduce the number of wires and
  nodes and the overall switching activity of the circuit.]

  Description [Optimize the network by performing wire/node removal,
  wire replacement and LUT reprogramming to reduce the number of wires
  and nodes and the overall switching activity of the circuit. The
  algorithm iteratively selects a node, 'maxNode', (based on the
  heuristic selected) and examines all the fanout/fanin wires to determine
  if any one them can be removed or replaced by another wire. For each
  wire selected, fanout cluster if computed up to a depth
  'regionDepth'. SPFD are computed only for these cluster nodes. Any
  wire, internal to the cluster, that has an empty SPFD is
  removed. Cluster nodes are then reprogrammed by choosing an
  alternative implementation derived from the node SPFD.

  After the cluster nodes are optimized, 'maxNode' is locked and is not
  optimized in future iterations. The algorithm ends when there are no
  more nodes to be optimized.

  The argument 'simFile' (if not NULL) specifies the vectors used to
  simulate the circuit in order to compute circuit node switching
  activity. Vector simulations are performed every 'frequency'
  iterations. 'regionDepth' specifies the depth of the cluster from
  the 'maxNode'.]
  
  SideEffects [None]

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

  Synopsis [Optimize the cluster of nodes in the fanout of each fanout
  wire of maxNode. The cluster is formed of those nodes that are
  within 'regionDepth' of the fanout wire. Both wire removal and
  replacement are performed if 'replRem' is true.]

  SideEffects        [None]

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

/**Function********************************************************************

  Synopsis [Checks if the SPFD for 'from' --> 'to' is empty. If yes,
  the wire is removed. If not, nodes in 'replaceArray' are examined to
  check for replacability. If a node is found, that node is returned.]

  SideEffects        [None]

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


/**Function********************************************************************

  Synopsis [Checks if the global functions implemented by nodes in
  'replaceArray' satisfy the SPFD, 'wireSpfd' of 'from' --> 'to'.]

  SideEffects        [None]

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


/**Function********************************************************************

  Synopsis           [Try to remove/replace the fanin wires of maxNode.]

  SideEffects        [None]

  SeeAlso            [SpfdOptimizeFanoutWires]

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


/**Function********************************************************************

  Synopsis           [Try to remove/replace the fanout wires of maxNode.]

  SideEffects        [None]

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


/**Function********************************************************************

  Synopsis           [Optimize all the fanin nodes of maxNode.]

  SideEffects        [None]

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


/**Function********************************************************************

  Synopsis [Optimize the cluster of nodes in the fanout the wire
  maxNode --> ntkNode. The cluster is formed of those nodes that are
  within 'regionDepth' of this wire. Both wire removal and replacement
  are performed if 'replRem' is true.]

  SideEffects        [None]

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


/**Function********************************************************************

  Synopsis [Optimize the ntkNode. This is done by computing its SPFD
  derived from the output cluster. The cluster is formed of those
  nodes that are within 'regionDepth' in the fanout of ntkNode. Both
  wire removal and replacement are performed if 'replRem' is true.]

  SideEffects        [None]

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

  Synopsis [Compare the convex combination of fanout count and the 
  node's topological depth.]

  SideEffects        [None]

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


/**Function********************************************************************

  Synopsis [Compare the convex combination of switched capacitance and
  topological depth of two nodes.]

  SideEffects        [None]

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