src/ord/ordNodes.c

Go to the documentation of this file.

#include "ordInt.h"

static char rcsid[] UNUSED = "$Id: ordNodes.c,v 1.12 2005/04/16 06:15:25 fabio Exp $";

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


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


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/
typedef struct OrderingStateStruct {
  st_table *nodeToOrderList;    /* Ntk_Node_t * to lsList; top. order of tfi
                                   nodes */
  st_table *from;               /* Ntk_Node_t * to Ntk_Node_t */
  lsGen last;                   /* insertion point */
  Ntk_Node_t *root;             /* current output */
} OrderingState_t;

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


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


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

static lsList NetworkOrderTFIOfRootsByMerging(Ntk_Network_t *network, lsList roots, Ord_ListMergeMethod method, st_table *nodeToHandle, int verbose);
static lsList NodeOrderRecursivelyByMerging(Ntk_Node_t * node, OrderingState_t * orderingState, Ord_ListMergeMethod method, int verbose);
static lsList NetworkOrderTFIOfRootsByAppending(Ntk_Network_t *network, lsList roots, st_table *nodeToHandle, int verbose);
static void NodeOrderRecursivelyByAppending(Ntk_Node_t * node, lsList orderList, st_table *nodeToHandle, int verbose);
static lsList NetworkOrderTFIOfRootsByInterleaving(Ntk_Network_t *network, lsList roots, st_table *nodeToHandle, int verbose);
static void NodeOrderRecursivelyByInterleaving(Ntk_Node_t * node, lsList orderList, st_table *nodeToHandle, OrderingState_t *orderingState, int verbose);
static OrderingState_t * NetworkInitializeOrderingState(Ntk_Network_t * network);
static void OrderingStateSetLast(Ntk_Node_t * node, st_table * nodeToHandle, OrderingState_t * orderingState);
static void OrderingStateFree(OrderingState_t * orderingState);
static lsList NodeReadOrderList(Ntk_Node_t * node, OrderingState_t * orderingState);
static void NodeSetOrderList(Ntk_Node_t * node, lsList orderList, OrderingState_t * orderingState);
static Ntk_Node_t * NodeReadFrom(Ntk_Node_t * node, OrderingState_t * orderingState);
static void NodeSetFrom(Ntk_Node_t * node, OrderingState_t * orderingState);

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


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

lsList
OrdNetworkOrderTFIOfRoots(
  Ntk_Network_t *network,
  lsList  roots /* of Ntk_Node_t  */,
  Ord_NodeMethod nodeOrderMethod,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  switch (nodeOrderMethod) {
    case Ord_NodesByDefault_c:
    case Ord_NodesByInterleaving_c:
      return NetworkOrderTFIOfRootsByInterleaving(network, roots,
                                                  nodeToHandle, verbose);
    case Ord_NodesByMergingLeft_c:
      return NetworkOrderTFIOfRootsByMerging(network, roots,
                                             Ord_ListMergeLeft_c,
                                             nodeToHandle, verbose);
    case Ord_NodesByMergingRight_c:
      return NetworkOrderTFIOfRootsByMerging(network, roots,
                                             Ord_ListMergeRight_c,
                                             nodeToHandle, verbose);
    case Ord_NodesByAppending_c:
      return NetworkOrderTFIOfRootsByAppending(network, roots,
                                               nodeToHandle, verbose);
    default:
      fail("unrecognized node ordering method");
      return (lsList) 0;
  }
}


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

static lsList
NetworkOrderTFIOfRootsByMerging(
  Ntk_Network_t *network,
  lsList  roots /* list of Ntk_Node_t  */,
  Ord_ListMergeMethod method,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  lsGen            gen;
  Ntk_Node_t      *root;
  OrderingState_t *orderingState;
  lsList           orderList = lsCreate(); /* return list */

  
  /*
   * Compute and store the depth of each node in the network.  (The depth of a
   * node is stored in the undef field of the node).
   */
  OrdNetworkComputeNodeDepths(network, roots);

  /*
   * Initialize the necessary state needed for recursing through the network.
   */
  orderingState = NetworkInitializeOrderingState(network);

  /*
   * For each root, recursively order all nodes in its transitive fanin, and
   * merge this ordering into the nodes already ordered.
   */
  lsForEachItem(roots, gen, root) {
    lsList rootOrderList = NodeOrderRecursivelyByMerging(root, orderingState,
                                                         method, verbose);
    Ord_ListMergeListUsingTable(orderList, rootOrderList, nodeToHandle, method);

    if (verbose > 2) {
      /* This can generate a lot of output. */
      (void) fprintf(vis_stdout, "\nOrder list after merging node %s\n",
                     Ntk_NodeReadName(root));
      OrdNodeListWrite(vis_stdout, orderList);
    }
  }
  
  /*
   * Clean up and return the ordering list.
   */
  OrderingStateFree(orderingState);
  return orderList;
}

  
static lsList
NodeOrderRecursivelyByMerging(
  Ntk_Node_t * node,
  OrderingState_t * orderingState,
  Ord_ListMergeMethod method,
  int verbose)
{
  lsList orderList;
  
  
  /*
   * If node has already been visited (i.e. its orderList is non-NULL), then
   * just return the orderList already computed.
   */
  orderList = NodeReadOrderList(node, orderingState);
  if (orderList != (lsList) NULL) {
    return orderList;
  }

  /*
   * Node has not yet been visited.  Create the orderList for node.
   */
  if (Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node)) {
    /*
     * Combinational inputs and constants terminate the recursion. If node is
     * one of these, then just create an empty list, to which we will add the
     * node.
     */
    orderList = lsCreate();
  }
  else if (Ntk_NodeReadNumFanins(node) == 1) {
    /*
     * If there is just one fanin, then just make a copy of the the fanin's
     * orderList. This case is distinguished from the general case for
     * efficiency. 
     */
    lsList faninOrderList = NodeOrderRecursivelyByMerging(Ntk_NodeReadFaninNode(node, 0),
                                                          orderingState,
                                                          method, verbose);
    orderList = lsCopy(faninOrderList, (lsGeneric (*) (lsGeneric)) NULL);
  }
  else {
    int       i;
    array_t  *sortedFanins;
    st_table *nodeToHandle;

    /*
     * Sort the fanins of node in decreasing order of depth.  See
     * OrdNetworkComputeNodeDepths.
     */
    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);

    /*
     * Start with an empty list for the orderList of the node.  Also, start
     * with an empty nodeToHandle table.  This table is only used locally, and
     * will be deleted below.
     */
    orderList = lsCreate();
    nodeToHandle  = st_init_table(st_ptrcmp, st_ptrhash);
    
    /*
     * Recursively visit the fanins in order of decreasing depth. The
     * nodeToHandle table keeps track of the nodes currently in orderList.
     */
    for (i = 0; i < array_n(sortedFanins); i++) {
      Ntk_Node_t *fanin          = array_fetch(Ntk_Node_t *, sortedFanins, i);
      lsList      faninOrderList = NodeOrderRecursivelyByMerging(fanin,
                                                                 orderingState,
                                                                 method, verbose);
      /*
       * Merge faninOrderList into the list of nodes already ordered.
       */
      Ord_ListMergeListUsingTable(orderList, faninOrderList, nodeToHandle, method);
    }
    array_free(sortedFanins);
    st_free_table(nodeToHandle);
  }

  /*
   * Regardless of the branch taken above, add node to the end of the
   * orderList, and set the node's orderList.
   */
  (void) lsNewEnd(orderList, (lsGeneric) node, LS_NH);
  NodeSetOrderList(node, orderList, orderingState);

  if (verbose > 2) {
    /* This can generate a lot of output. */
    (void) fprintf(vis_stdout, "\nOrder list for node %s\n", Ntk_NodeReadName(node));
    OrdNodeListWrite(vis_stdout, orderList);
  }
  
  return orderList;
}


static lsList
NetworkOrderTFIOfRootsByAppending(
  Ntk_Network_t *network,
  lsList  roots /* list of Ntk_Node_t  */,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  lsGen       gen;
  Ntk_Node_t *root;
  lsList      orderList = lsCreate(); /* return list */

  
  /*
   * Compute and store the depth of each node in the network.  (The depth of a
   * node is stored in the undef field of the node).
   */
  OrdNetworkComputeNodeDepths(network, roots);

  if (verbose > 1) {
    Ntk_Node_t *node;
    (void) fprintf(vis_stdout, "\nDepths of network nodes:\n");
    Ntk_NetworkForEachNode(network, gen, node) {
      (void) fprintf(vis_stdout, "%s: depth = %ld\n", Ntk_NodeReadName(node),
                     OrdNodeReadDepth(node));
    }
  }

  /*
   * For each root, recursively order all nodes in its transitive fanin.
   */
  lsForEachItem(roots, gen, root) {
    NodeOrderRecursivelyByAppending(root, orderList, nodeToHandle, verbose);
  }
  
  return orderList;
}


static void
NodeOrderRecursivelyByAppending(
  Ntk_Node_t * node,
  lsList orderList,
  st_table *nodeToHandle,
  int verbose)
{
  lsHandle handle;
  
  /*
   * If node has already been visited (i.e. its in the nodeToHandle table), then
   * just return.
   */
  if (st_is_member(nodeToHandle, (char *) node)) {
    return;
  }
  
  /*
   * Node has not yet been visited.  Recurse on the inputs, and then add node
   * to the end of the current ordering.
   */
  if (!(Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node))) {
    /*
     * Combinational inputs and constants terminate the recursion. If node is
     * not one of these, then recurse on the inputs.
     */
    int       i;
    array_t  *sortedFanins;

    /*
     * Sort the fanins of node in decreasing order of depth.  See
     * OrdNetworkComputeNodeDepths.
     */
    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);

    /*
     * Recursively visit the fanins in order of decreasing depth. The
     * nodeToHandle table keeps track of the nodes currently in orderList.
     */
    for (i = 0; i < array_n(sortedFanins); i++) {
      Ntk_Node_t *fanin = array_fetch(Ntk_Node_t *, sortedFanins, i);

      NodeOrderRecursivelyByAppending(fanin, orderList, nodeToHandle, verbose);
    }
    array_free(sortedFanins);
  }

  /*
   * Regardless of the branch taken above, add node to the end of the
   * orderList and to the nodeToHandle table.
   */
  (void) lsNewEnd(orderList, (lsGeneric) node, &handle);
  st_insert(nodeToHandle, (char *) node, (char *) handle);
}

  
static lsList
NetworkOrderTFIOfRootsByInterleaving(
  Ntk_Network_t *network,
  lsList roots /* list of Ntk_Node_t  */,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  lsGen       gen;
  Ntk_Node_t *root;
  lsList      orderList = lsCreate(); /* return list */
  OrderingState_t *orderingState;

  /*
   * Compute and store the depth of each node in the network.  (The depth of a
   * node is stored in the undef field of the node.)
   */
  OrdNetworkComputeNodeDepths(network, roots);

  /*
   * Initialize the state needed for recurring through the network.
   */
  orderingState = NetworkInitializeOrderingState(network);

  if (verbose > 1) {
    Ntk_Node_t *node;
    (void) fprintf(vis_stdout, "\nDepths of network nodes:\n");
    Ntk_NetworkForEachNode(network, gen, node) {
      (void) fprintf(vis_stdout, "%s: depth = %ld\n", Ntk_NodeReadName(node),
                     OrdNodeReadDepth(node));
    }
  }

  /*
   * For each root, recursively order all nodes in its transitive fanin.
   */
  lsForEachItem(roots, gen, root) {
    orderingState->root = root;
    orderingState->last = lsStart(orderList);
    NodeOrderRecursivelyByInterleaving(root, orderList, nodeToHandle,
                                       orderingState, verbose);
    lsFinish(orderingState->last);

    if (verbose > 2) {
      /* This can generate a lot of output. */
      (void) fprintf(vis_stdout, "\nOrder list after merging node %s\n",
                     Ntk_NodeReadName(root));
      OrdNodeListWrite(vis_stdout, orderList);
    }
  }

  /*
   * Clean up and return the ordering list.
   */
  OrderingStateFree(orderingState);
  return orderList;
}

  
static void
NodeOrderRecursivelyByInterleaving(
  Ntk_Node_t * node,
  lsList orderList,
  st_table *nodeToHandle,
  OrderingState_t *orderingState,
  int verbose)
{
  lsHandle handle;
  
  /*
   * If node has already been visited (i.e., it is in the nodeToHandle table),
   * then update the info on the output from which it was last reached,
   * and change the insertion point to this node.
   */
  if (st_is_member(nodeToHandle, (char *) node)) {
    if (NodeReadFrom(node, orderingState) != orderingState->root) {
      OrderingStateSetLast(node, nodeToHandle, orderingState);
      NodeSetFrom(node, orderingState);
    }
    return;
  }

  /*
   * Node has not yet been visited.  Recur on the inputs, and then add node
   * to the end of the current ordering.
   */
  if (!(Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node))) {
    /*
     * Combinational inputs and constants terminate the recursion. If node is
     * not one of these, then recur on the inputs.
     */
    int       i;
    array_t  *sortedFanins;

    /*
     * Sort the fanins of node in decreasing order of depth.  See
     * OrdNetworkComputeNodeDepths.
     */
    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);

    /*
     * Recursively visit the fanins in order of decreasing depth. The
     * nodeToHandle table keeps track of the nodes currently in orderList.
     */
    for (i = 0; i < array_n(sortedFanins); i++) {
      Ntk_Node_t *fanin = array_fetch(Ntk_Node_t *, sortedFanins, i);

      NodeOrderRecursivelyByInterleaving(fanin, orderList, nodeToHandle,
                                         orderingState,verbose);
    }
    array_free(sortedFanins);
  }

  /*
   * Regardless of the branch taken above, add node to orderList at the
   * insertion point and to the nodeToHandle table. Make node the new
   * insertion point.
   */
  NodeSetFrom(node, orderingState);
  (void) lsInBefore(orderingState->last, (lsGeneric) node, &handle);
  st_insert(nodeToHandle, (char *) node, (char *) handle);
  OrderingStateSetLast(node, nodeToHandle, orderingState);
}


static OrderingState_t *
NetworkInitializeOrderingState(
  Ntk_Network_t * network)
{
  OrderingState_t *orderingState = ALLOC(OrderingState_t, 1);

  /* nodeToOrderList is used by the merging method. */
  orderingState->nodeToOrderList = st_init_table(st_ptrcmp, st_ptrhash);

  /* from, last, and root used by the interleaving method. */
  orderingState->from = st_init_table(st_ptrcmp, st_ptrhash);
  orderingState->last = NULL;
  orderingState->root = NULL;

  return orderingState;
}


static void
OrderingStateSetLast(
  Ntk_Node_t * node,
  st_table * nodeToHandle,
  OrderingState_t * orderingState)
{
  lsHandle handle;
  lsGen gen;
  lsGeneric data;

  /* Dispose of the current generator. */
  lsFinish(orderingState->last);

  /* Get a handle for the current node. */
  st_lookup(nodeToHandle, node, &handle);

  /*
   * Create a new generator positioned after node and register it
   * in orderingState.
   */
  gen = lsGenHandle(handle,&data,LS_AFTER);
  orderingState->last = gen;
}

static void
OrderingStateFree(
  OrderingState_t * orderingState)
{
  st_generator *stGen;
  lsList orderList;
  Ntk_Node_t *node;
  
  st_foreach_item(orderingState->nodeToOrderList, stGen, &node, &orderList) {
    (void) lsDestroy(orderList, (void (*) (lsGeneric)) NULL);
  }
  
  st_free_table(orderingState->nodeToOrderList);
  st_free_table(orderingState->from);
  
  FREE(orderingState);
}


static lsList
NodeReadOrderList(
  Ntk_Node_t * node,
  OrderingState_t * orderingState)
{
  lsList orderList = (lsList) NULL;

  st_lookup(orderingState->nodeToOrderList, node, &orderList);
  
  return orderList;
}


static void
NodeSetOrderList(
  Ntk_Node_t * node,
  lsList orderList,
  OrderingState_t * orderingState)
{
  st_insert(orderingState->nodeToOrderList, (char *) node, (char *) orderList);
}


static Ntk_Node_t *
NodeReadFrom(
  Ntk_Node_t * node,
  OrderingState_t * orderingState)
{
  Ntk_Node_t * from = NULL;

  st_lookup(orderingState->from, node, &from);
  
  return from;
}


static void
NodeSetFrom(
  Ntk_Node_t * node,
  OrderingState_t * orderingState)
{
  st_insert(orderingState->from, (char *) node, (char *) orderingState->root);
}