src/spfd/spfdReg.c

Go to the documentation of this file.

#include "spfdInt.h"

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

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


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


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


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


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


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


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
array_t *
SpfdNodeComputeFanoutRegion(
  SpfdApplData_t *applData,
  Ntk_Node_t *startNode,
  int regionDepth)
{
  Ntk_Node_t *fanout,*ntkNode;
  st_table *reached;
  st_generator *stGen;
  array_t *regionArray,*from,*new_;
  int bound,i,j,k;

  reached = st_init_table(st_ptrcmp,st_ptrhash);
  if (Ntk_NodeTestIsPrimaryOutput(startNode)) {
    st_insert(reached,(char *)startNode,(char *)1);
  } else {
    /* Sort the fanout array of startNode according to depth */
    from = array_dup(Ntk_NodeReadFanouts(startNode));
    array_sort(from,SpfdDepthCompare);
    /* Put fanoutArray into reached */
    arrayForEachItem(Ntk_Node_t *,from,i,fanout) {
      if (!Ntk_NodeTestIsPrimaryOutput(fanout)) {
        bound = 0;
      } else {
        bound = 1;
      }
      st_insert(reached,(char *)fanout,(char *)(long)bound);
    }

    /* Proceed for depth regionDepth */
    for (i = 0; i < regionDepth; i++) {
      new_ = array_alloc(Ntk_Node_t *,0);
      arrayForEachItem(Ntk_Node_t *,from,j,ntkNode) {
        st_lookup(reached,(char *)ntkNode,&bound);
        if (!bound) {
          Ntk_NodeForEachFanout(ntkNode,k,fanout) {
            if (!st_lookup(reached,(char *)fanout,&bound)) {
              if (Ntk_NodeTestIsPrimaryOutput(fanout) ||
                  Ntk_NodeReadNumFanouts(fanout) < 1 || /* Just to be safe */
                  i == regionDepth - 1) {
                bound = 1;
              } else {
                bound = 0;
              }
              st_insert(reached,(char *)fanout,(char *)(long)bound);
              array_insert_last(Ntk_Node_t *,new_,fanout);
            }
          }
        }
      }
      array_free(from);
      from = new_;
      array_sort(from,SpfdDepthCompare);
    }
    array_free(from);
  
    /* Finally make the startNode an internal node */
    st_insert(reached,(char *)startNode,(char *)0);
  }  

  /* Put the nodes in reached according to their depth */
  regionArray = array_alloc(Ntk_Node_t *,0);
  st_foreach_item_int(reached,stGen,&fanout,&bound) {
    array_insert_last(Ntk_Node_t *,regionArray,fanout);
  }
  array_sort(regionArray,SpfdDepthCompare);

  if (applData->currRegionNodes) {
    (void) fprintf(vis_stdout,
                   "** spfd warning: Possible memory leak.\n");
  }
  applData->currRegionNodes = reached;
  
  return regionArray;
  
} /* End of SpfdNodeComputeFanoutRegion */


array_t *
SpfdNodeComputeTFIUntilDepth(
  Ntk_Node_t *startNode,
  int regionDepth)
{
  Ntk_Node_t *fanin,*ntkNode;
  st_table *reached,*faninTable;
  st_generator *stGen;
  array_t *regionArray,*from,*new_;
  char *dummy;
  int i,j,k;

  /* Make sure that startNode is not a PI to start with. */

  if (Ntk_NodeTestIsPrimaryInput(startNode))
    return NIL(array_t);

  reached = st_init_table(st_ptrcmp,st_ptrhash);
  faninTable = st_init_table(st_ptrcmp,st_ptrhash);
  
  /* Put the fanin array of startNode in faninTable */
  from = array_dup(Ntk_NodeReadFanins(startNode));
  arrayForEachItem(Ntk_Node_t *,from,i,ntkNode) {
    st_insert(faninTable,(char *)ntkNode,(char *)1);
  }

  /* Proceed for depth regionDepth */
  for (i = 0; i < regionDepth; i++) {
    new_ = array_alloc(Ntk_Node_t *,0);
    arrayForEachItem(Ntk_Node_t *,from,j,ntkNode) {
      Ntk_NodeForEachFanin(ntkNode,k,fanin) {
        if (!st_lookup(reached,(char *)fanin,&dummy) &&
            !st_lookup(faninTable,(char *)fanin,&dummy)) {
          st_insert(reached,(char *)fanin,(char *)1);
          array_insert_last(Ntk_Node_t *,new_,fanin);
        }
      }
    }
    array_free(from);
    from = new_;
  }
  array_free(from);
  st_free_table(faninTable);
  
  /* Put the nodes in reached according to their depth */
  regionArray = array_alloc(Ntk_Node_t *,0);
  st_foreach_item(reached,stGen,&ntkNode,&dummy) {
    array_insert_last(Ntk_Node_t *,regionArray,ntkNode);
  }
  array_sort(regionArray,SpfdDepthCompare);

  st_free_table(reached);
  return regionArray;
  
} /* End of SpfdNodeComputeTFIUntilDepth */


void
SpfdNodesInTFO(
  Ntk_Network_t *network,
  Ntk_Node_t *node,
  st_table *tfoNodes)
{
  int i;
  Ntk_Node_t *fanout;
  
  st_insert(tfoNodes,(char *)node,(char *)0);
  Ntk_NodeForEachFanout(node,i,fanout) {
    SpfdNodesInTFO(network,fanout,tfoNodes);
  }

  return;
} /* End of SpfdNodesInTFO */


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