#include "ordInt.h"

Include dependency graph for ordRoots.c:

Functions
lsList	Ord_NetworkOrderRoots (Ntk_Network_t *network, Ord_RootMethod rootMethod, lsList partialOrder, boolean verbose)
lsList	OrdNetworkOrderRootsByDepth (Ntk_Network_t *network, boolean verbose)
void	OrdNodeAddToList (lsList nodeList, st_table nodeTable, Ntk_Node_t node)
Variables
static char rcsid[]	UNUSED = "$Id: ordRoots.c,v 1.7 2002/08/27 08:43:16 fabio Exp $"

Function Documentation

lsList Ord_NetworkOrderRoots	(	Ntk_Network_t *	network,
		Ord_RootMethod	rootMethod,
		lsList	partialOrder,
		boolean	verbose
	)

AutomaticStart AutomaticEnd Function********************************************************************

Synopsis [Orders the roots of a network.]

Description [Orders the combinational outputs of a network. The data inputs of latches always precede the other combinational outputs. This gives priority to finding the best ordering for the variables in the next state functions.

The different root ordering methods are documented in the static_order command. If rootMethod is Ord_RootsByDefault_c, then one of the ordering methods is called by default, depending on the number of latches in the network.

An arbitrary subset of roots can be specified in partialOrder. No check is made to determine if the nodes in partialOrder are contained within the set specified by orderType. If partialOrder is non-NULL, then a total order on the roots is computed according to rootMethod (as described above), and then the computed order is merged into the partialOrder.]

SideEffects []

SeeAlso [OrdNetworkOrderRootsByDepth OrdNetworkOrderRootsByPerm]

Definition at line 107 of file ordRoots.c.

{
  lsList rootOrderList;
  
  switch (rootMethod) {
    case Ord_RootsByDepth_c:
      rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose); 
      break;
    case Ord_RootsByPerm_c:
      rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
      break;
    case Ord_RootsByDefault_c:
      /*
       * RootByPerm method is cubic in the number of latches, so use it by
       * default only if the number of latches is not too large (30 is somewhat
       * arbitrary).
       */
      if (Ntk_NetworkReadNumLatches(network) < 30) {
        rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
      }
      else {
        rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose);
      }
      break;
    default:
      fail("unrecognized root order method");
  }

  /*
   * If a partial order is supplied, merge (left, arbitrarily) the computed
   * order into the supplied order, to get a total ordering on all of the
   * roots.
   */
  if (partialOrder != (lsList) NULL) {
    lsList partialOrderCopy = lsCopy(partialOrder,
                                     (lsGeneric (*) (lsGeneric)) NULL);

    Ord_ListMergeList(partialOrderCopy, rootOrderList, Ord_ListMergeLeft_c);
    (void) lsDestroy(rootOrderList, (void (*) (lsGeneric)) NULL);
    return partialOrderCopy;
  }
  else {
    return rootOrderList;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

lsList OrdNetworkOrderRootsByDepth	(	Ntk_Network_t *	network,
		boolean	verbose
	)

Function********************************************************************

Synopsis [Computes a total ordering on the combinational outputs of a network.]

Description [Computes a total ordering on the combinational outputs of a network. First, the depth of each combinational output is calculated. The depth of a node is the longest path (going backwards) to a combinational input or constant. Then, the algorithm creates two lists: 1) data inputs to latches, and 2) all remaining combinational outputs. Next, each list is sorted in order of decreasing depth. Finally, the second list is appended to the first.]

SideEffects []

SeeAlso [Ord_NetworkOrderRoots OrdNetworkComputeNodeDepths]

Definition at line 181 of file ordRoots.c.

{
  lsGen       gen;
  Ntk_Node_t *node;
  st_table   *processedTable = st_init_table(st_ptrcmp, st_ptrhash);
  lsList dataInputs = lsCreate();
  lsList otherCombOuts = lsCreate();
  lsList combOutputs = Ntk_NetworkReadCombOutputs(network);

  /*
   * A node can drive more than one latch data input, latch initial input,
   * or primary output. Use a hash table to ensure that no node appears twice
   * across the two lists.
   */
  Ntk_NetworkForEachCombOutput(network, gen, node) {
    if (Ntk_NodeTestIsLatchDataInput(node)) {
      OrdNodeAddToList(dataInputs, processedTable, node);
    }
    else {
      OrdNodeAddToList(otherCombOuts, processedTable, node);
    }
  }
  st_free_table(processedTable);

  /* Compute depth of all combinational outputs. */
  OrdNetworkComputeNodeDepths(network, combOutputs);

  /* Sort each list independently. */
  lsSort(dataInputs, OrdNodesFromListCompareDepth);
  lsSort(otherCombOuts, OrdNodesFromListCompareDepth);

  Ord_ListAppendList(dataInputs, otherCombOuts);
  (void) lsDestroy(otherCombOuts, (void (*) (lsGeneric)) NULL);
  
  return dataInputs;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void OrdNodeAddToList	(	lsList	nodeList,
		st_table *	nodeTable,
		Ntk_Node_t *	node
	)

Function********************************************************************

Synopsis [Inserts a node into a list, unless it already appears in the list.]

SideEffects []

Definition at line 228 of file ordRoots.c.

{
  if (!st_is_member(nodeTable, (char *) node)) {
    st_insert(nodeTable, (char *) node, NIL(char));
    (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH);
  }
}

Here is the caller graph for this function:

Variable Documentation

char rcsid [] UNUSED = "$Id: ordRoots.c,v 1.7 2002/08/27 08:43:16 fabio Exp $" [static]

CFile***********************************************************************

FileName [ordRoots.c]

PackageName [ord]

Synopsis [Routines to order the roots of the network.]

Description [Routines to order the roots of the network. The nodes of the network are explored in DFS order from the roots, in the root order computed. To add a new method, create a new value for the Ord_RootMethod enumerated type, and add a call to the new procedure from Ord_NetworkOrderRoots.]

Author [Tom Shiple]

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

Definition at line 40 of file ordRoots.c.

src/ord/ordRoots.c File Reference

Functions

Variables

Function Documentation

Variable Documentation