src/ntk/ntkGraph.c

Go to the documentation of this file.

#include "ntkInt.h"

static char rcsid[] UNUSED = "$Id: ntkGraph.c,v 1.11 2005/04/16 04:24:15 fabio Exp $";

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

typedef enum {
  dfsWhite_c,   /* unvisited node */
  dfsGrey_c,    /* node on "stack" */
  dfsBlack_c    /* node completely visited */
} DfsColor;


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

static void RegionFindNodesRecursively(Ntk_Node_t *node, st_table *leaves, st_table *result);
static boolean NodeTestCannotReachCycle(Ntk_Node_t * node);
static boolean NodeTestCoveredByLeaves(Ntk_Node_t *node, st_table *leaves, st_table *visited);
static DfsColor NodeReadColor(Ntk_Node_t * node);
static void NodeSetColor(Ntk_Node_t * node, DfsColor color);
static void NodeSetTfoLatchList(Ntk_Node_t * node, lsList tfoLatchList);
static lsList NodeReadTfoLatchList(Ntk_Node_t * node);
static void NodeFreeTfoLatchList(Ntk_Node_t * node);
static void ListAppendList(lsList list1, lsList list2);
static lsList NodeComputeTfoLatchList(Ntk_Node_t * node);
static void NodeRecursivelyComputeTransitiveFaninNodes(Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches);
static void NodeComputeTopologicalOrderRecursively(Ntk_Node_t *node, st_table *leafNodesTable, lsList topologicalNodeList);
static void NodeComputeTransitiveFaninNodes(Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches);

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

array_t *
Ntk_NodeComputeTransitiveFanoutNodes(
  array_t * nodeArray,
  int  depth)
{
  fail("not yet implemented");
  return(NIL(array_t));
}

array_t *
Ntk_NodeComputeTransitiveFanInputNodes(
  array_t * nodeArray,
  int  depth)
{
  fail("not yet implemented");
  return(NIL(array_t));
}

array_t *
Ntk_NodeComputeTransitiveFaninNodes(
  Ntk_Network_t *network,
  array_t * nodeArray,
  boolean stopAtLatches,
  boolean combInputsOnly)
{
  int i;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );

  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
    NodeComputeTransitiveFaninNodes(node, resultTable, stopAtLatches );
  }
  
  st_foreach_item( resultTable, stGen, &node, NULL ){
    if ( !combInputsOnly || Ntk_NodeTestIsCombInput(node) ) 
      array_insert_last( Ntk_Node_t *, resultArray, node );
  }
  st_free_table( resultTable );
  
  return resultArray;
}

array_t *
Ntk_NodeComputeCombinationalSupport(
  Ntk_Network_t *network,
  array_t * nodeArray,
  boolean stopAtLatches )
{
  lsGen gen;
  int i;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );

  Ntk_NetworkForEachNode( network, gen, node ) {
        NodeSetColor( node, dfsWhite_c );
  }

  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
        NodeRecursivelyComputeTransitiveFaninNodes( node, resultTable, stopAtLatches );
  }

  st_foreach_item( resultTable, stGen, &node, NULL ){
        array_insert_last( Ntk_Node_t *, resultArray, node );
  }
  st_free_table( resultTable );

  return resultArray;
}


st_table *
Ntk_RegionFindNodes(
  array_t *roots, 
  st_table *leaves)
{
  int i;
  st_table *result = st_init_table(st_ptrcmp, st_ptrhash);
  for (i = 0; i < array_n(roots); i++) {
    Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
    RegionFindNodesRecursively(root, leaves, result);
  }
  return result;
}

st_table *
Ntk_NetworkComputeLatchDependencies(
  Ntk_Network_t * network)
{
  lsGen       gen;
  Ntk_Node_t *node;
  Ntk_Node_t *latch;
  st_table   *latchDependencies = st_init_table(st_ptrcmp, st_ptrhash);

  /*
   * Initialize the TFO latch list of each node to NULL.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetTfoLatchList(node, (lsList) NULL);
  }

  /*
   * For each latch, compute the set of latches in its TFO (including possibly
   * itself).  Accumulate this set of latches into a list, and when the list
   * is complete, store the latch and list as the key and value in the hash
   * table.
   */
  Ntk_NetworkForEachLatch(network, gen, latch) {
    int         i;
    Ntk_Node_t *fanout;
    lsList      tfoLatchList = lsCreate();  /* allocate a fresh list */

    /*
     * Get the latches in the TFO of each fanout of latch, and accumulate into
     * a list. Note that we can't call NodeComputeTfoLatchList on latch
     * itself, because latches serve as the terminal case of the recursion.
     */
    Ntk_NodeForEachFanout(latch, i, fanout) {
      lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);

      ListAppendList(tfoLatchList, fanoutTfoLatchList);
    }

    st_insert(latchDependencies, (char *) latch, (char *) tfoLatchList);
    
  }

  /*
   * Free the tfoLatchList stored at the nodes.  Only nodes in the transitive
   * fanout of latches will have a non-NULL list, but we just call free
   * tfoLatchList function on each node.  Note that the lists being returned
   * in the hash table are distinct from those stored at nodes.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeFreeTfoLatchList(node);
  }

  return (latchDependencies);
}


boolean
Ntk_NetworkTestIsAcyclic(
  Ntk_Network_t * network)
{
  lsGen       gen;
  Ntk_Node_t *node;
  boolean     status = 1; /* In case network has no vertices. */

  /* The meaning of the colors is:
   *   white: node has not been visited yet
   *   grey:  node is on the "stack"
   *   black: node, and all its descendents, have been visited
   */

  /*
   * Initialize the color of each node to white.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetColor(node, dfsWhite_c);
  }
  
  /*
   * Recursively visit each unvisited node.  The order in which we visit the
   * nodes is immaterial.  
   */  
  Ntk_NetworkForEachNode(network, gen, node) {
    if (NodeReadColor(node) == dfsWhite_c) {
      status = NodeTestCannotReachCycle(node);
      if (status == 0) {
        /* A cycle has been found. */
        break;
      }
    }
  }

  /*
   * Colors will be left in the undef field of the nodes, but we don't care.
   */
  return (status);
}


boolean
Ntk_NetworkTestLeavesCoverSupportOfRoots(
  Ntk_Network_t *network,
  array_t       *roots,
  st_table      *leaves)
{
  int         i;
  Ntk_Node_t *root;
  st_table   *visited = st_init_table(st_ptrcmp, st_ptrhash);
  
  /* Perform DFS from the roots.  Return FALSE upon the first failure. */
  arrayForEachItem(Ntk_Node_t *, roots, i, root) {
    boolean status = NodeTestCoveredByLeaves(root, leaves, visited);
    
    if(!status) {
      error_append(Ntk_NodeReadName(root));
      error_append(".\n");
      st_free_table(visited);
      return FALSE; 
    }
  }
  st_free_table(visited);
  return TRUE;
}


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
lsList
Ntk_NetworkComputeTopologicalOrder(Ntk_Network_t *network, array_t
                                  *rootNodesArray, st_table
                                  *leafNodesTable) 
{
  int i;
  lsList topologicalNodeList = lsCreate();
  Ntk_Node_t *node;
  lsGen gen;
  
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetColor(node, dfsWhite_c);
  }

  for (i=0; i<array_n(rootNodesArray); i++){
    node = array_fetch(Ntk_Node_t *, rootNodesArray, i);
    NodeComputeTopologicalOrderRecursively(node, leafNodesTable,
                                           topologicalNodeList);
  }
  return topologicalNodeList;
}


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

static void
RegionFindNodesRecursively(
  Ntk_Node_t *node, 
  st_table *leaves,
  st_table *result)
{
  int i;
  Ntk_Node_t *fanin;

  if (st_is_member(result, (char *) node)) {
    /* already visited this node */
    return;
  }
  else {
    /*
     * Add to table before recursing, to avoid infinite loops in presence of
     * combinational cycles.
     */
    st_insert(result, (char *) node, NIL(char));
  }
  
  
  if (!st_is_member(leaves, (char *) node) && !Ntk_NodeTestIsConstant(node)) {
    /* not a leaf; recurse */
    Ntk_NodeForEachFanin(node, i, fanin) {
      RegionFindNodesRecursively(fanin, leaves, result);
    }
  }

  return;
}

static boolean
NodeTestCannotReachCycle(
  Ntk_Node_t * node)
{
  Ntk_Node_t *fanout;
  int i;

  /*
   * Set the color of node to grey to indicate that it is on the "stack".
   */
  NodeSetColor(node, dfsGrey_c);

  Ntk_NodeForEachFanout(node, i, fanout) {
    /*
     * Traverse fanout if it is *not* a latch; latches break combinational cycles.
     */
    if (Ntk_NodeTestIsLatch(fanout) == 0) {
      DfsColor fanoutColor = NodeReadColor(fanout);

      /* 
       * If fanout is white, it has not been visited yet, so visit it, and 
       * break the search if it can reach a cycle.  Else if fanout is grey, it 
       * means that fanout is also on the stack, so a cycle has been found; 
       * thus break.  Else, the fanout is black, and there is nothing to do.
       */
      if (fanoutColor == dfsWhite_c) {
        if (NodeTestCannotReachCycle(fanout) == 0) {
          return (0);
        }
      }
      else if (fanoutColor == dfsGrey_c) {
        error_append("(");
        error_append(Ntk_NodeReadName(node));
        error_append(", ");
        error_append(Ntk_NodeReadName(fanout));
        error_append(")");
        return (0);
      } 
    }
  }

  /*
   * Set the color of node to black to indicate that it has been visited.
   */
  NodeSetColor(node, dfsBlack_c);
  
  /*
   * No cycles found from node.
   */
  return (1);
}


static boolean
NodeTestCoveredByLeaves(
  Ntk_Node_t *node,
  st_table   *leaves,
  st_table   *visited)
{
  int         i;
  Ntk_Node_t *fanin;

  /*
   * If node has already been visited, just return.  Else, mark it as
   * visited. Note that it is important to mark it as visited BEFORE recursing,
   * in case combinational cycles are present.
   */
  if (st_is_member(visited, (char *) node)) {
    return TRUE;
  }
  else {
    st_insert(visited, (char *) node, NIL(char));
  }

  if (st_is_member(leaves, (char *) node)) {
    /*
     * Positive termination of recursion: if node is a leaf, then everything
     * is fine.
     */ 
    return TRUE;
  }
  else {
    /* Node is not a leaf. */
    if (Ntk_NodeTestIsCombInput(node)) {
      /*
       * Negative termination of recursion: a combinational input was reached
       * without seeing a leaf.
       */ 
      error_append("Node ");
      error_append(Ntk_NodeReadName(node));
      error_append(" found in the support of node ");
      return FALSE;
    }
    else {
      /*
       * Node is not a leaf nor a combinational input.  Recurse over fanins.
       * Return FALSE if any fanins fail the test.
       */
      Ntk_NodeForEachFanin(node, i, fanin) {
        boolean status = NodeTestCoveredByLeaves(fanin, leaves, visited);
        if (!status) {
          return FALSE;
        }
      }
      /*
       * If the loop terminates without the function returning, then each
       * fanin has already been visited and no dfsWhite_c-labelled comb input
       * can be reached from the fanins. Therefore, return TRUE.
       */
      return TRUE;
    }
  }
  
}


static DfsColor
NodeReadColor(
  Ntk_Node_t * node)
{
  return ((DfsColor) (long) Ntk_NodeReadUndef(node));
}


static void
NodeSetColor(
  Ntk_Node_t * node,
  DfsColor  color)
{
  Ntk_NodeSetUndef(node, (void *) (long) color);
}


static void
NodeSetTfoLatchList(
  Ntk_Node_t * node,
  lsList  tfoLatchList)
{
  Ntk_NodeSetUndef(node, (void *) tfoLatchList);
}


static lsList
NodeReadTfoLatchList(
  Ntk_Node_t * node)
{
  return ((lsList) Ntk_NodeReadUndef(node));
}


static void
NodeFreeTfoLatchList(
  Ntk_Node_t * node)
{
  lsList tfoLatchList = NodeReadTfoLatchList(node);

  if (tfoLatchList != (lsList) NULL) {
    (void) lsDestroy(tfoLatchList, (void (*) (lsGeneric)) NULL);
    Ntk_NodeSetUndef(node, (void *) NULL);
  }
}

static void
ListAppendList(
  lsList  list1,
  lsList  list2)
{
  lsGen      gen;
  lsGeneric  data;
  st_table  *table1 = st_init_table(st_ptrcmp, st_ptrhash);
  
  /*
   * Load a hash table mapping each item in list1 to NULL.
   */
  gen = lsStart(list1);
  while (lsNext(gen, &data, LS_NH) == LS_OK) {
    st_insert(table1, (char *) data, (char *) NULL);
  }
  (void) lsFinish(gen);

  /*
   * For each item in list2, if it's not already present in list1, then add it
   * to the end of list1.
   */
  lsForEachItem(list2, gen, data) {
    if (st_is_member(table1, (char *) data) == 0) {
      lsNewEnd(list1, data, LS_NH);
    }
  }
  st_free_table(table1);
}


static lsList
NodeComputeTfoLatchList(
  Ntk_Node_t * node)
{
  lsList tfoLatchList = NodeReadTfoLatchList(node);

  /*
   * If node already has a non-NULL tfoLatchList, then just return it (this
   * can happen if the node was already visited via one of its other
   * fanins). Otherwise, create an empty list and fill it appropriately.
   */
  if (tfoLatchList != (lsList) NULL) {
    return (tfoLatchList);
  }
  else {
    tfoLatchList = lsCreate();

    if (Ntk_NodeTestIsLatch(node)) {
      /*
       * Special case; terminal condition.
       */
      lsNewEnd(tfoLatchList, (lsGeneric) node, LS_NH);
    }
    else {
      int         i;
      Ntk_Node_t *fanout;
      
      /*
       * Get the latches in the TFO of each fanout of node, and accumulate into
       * a list.
       */
      Ntk_NodeForEachFanout(node, i, fanout) {
        lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);

        ListAppendList(tfoLatchList, fanoutTfoLatchList);
      }
    }

    /*
     * Store the list with the node, then return the list.
     */
    NodeSetTfoLatchList(node, tfoLatchList);
    return (tfoLatchList);    
  }
}



static void
NodeRecursivelyComputeTransitiveFaninNodes( 
  Ntk_Node_t *node, 
  st_table *resultTable,
  boolean stopAtLatches) 
{
  int i;
  Ntk_Node_t * fanin;

  /* test if we have already started processing this node */
  if ( NodeReadColor( node ) == dfsBlack_c ) {
        return;
  }
  NodeSetColor( node, dfsBlack_c );

  if ( Ntk_NodeTestIsCombInput( node ) ) {
        st_insert( resultTable, (char *) node, (char *) 0 );
  }

  if ( Ntk_NodeTestIsInput(node) || ((stopAtLatches == TRUE)&&(Ntk_NodeTestIsLatch(node))) ) {
        return;
  }

  Ntk_NodeForEachFanin( node, i, fanin ) {
        NodeRecursivelyComputeTransitiveFaninNodes( fanin, resultTable, stopAtLatches );
  }
}



static void
NodeComputeTopologicalOrderRecursively(Ntk_Node_t *node, st_table
                                       *leafNodesTable, lsList
                                       topologicalNodeList) 
{
  int i;
  Ntk_Node_t *fanin;
  
  if (NodeReadColor(node) == dfsBlack_c){
    /* Has already been put in the list. */
    return;
  }
  if (NodeReadColor(node) == dfsGrey_c){
    /* Indicates that this node is currently being processed (possibly a
       combinational loop). */
    return;
  }
  if (st_is_member(leafNodesTable, (char *)node)== 0){
    NodeSetColor(node, dfsGrey_c);
    Ntk_NodeForEachFanin(node, i, fanin){
      NodeComputeTopologicalOrderRecursively(fanin, leafNodesTable,
                                             topologicalNodeList);
    }
  }
  NodeSetColor(node, dfsBlack_c);
  lsNewEnd(topologicalNodeList, (lsGeneric)node, LS_NH);
  return;
}

static void
NodeComputeTransitiveFaninNodes( 
  Ntk_Node_t *node, 
  st_table *resultTable,
  boolean stopAtLatches) 
{
  int i;
  Ntk_Node_t * fanin;
  
  /* test if we have already started processing this node */
  if (st_is_member(resultTable, node))
    return;

  st_insert(resultTable, node, (char *)(long)2);

  if (Ntk_NodeTestIsInput(node) || (stopAtLatches && Ntk_NodeTestIsLatch(node)))
    return;

  Ntk_NodeForEachFanin(node, i, fanin) {
    NodeComputeTransitiveFaninNodes(fanin, resultTable, stopAtLatches);
  }
}