The different node ordering methods are documented in the static_order command. If nodeMethod is Ord_NodesByDefault_c, then one of the ordering methods is called by default.
nodeToHandle should be an empty table created using st_init_table(st_ptrcmp, st_ptrhash). For every node in the returned list, there is an entry in nodeToHandle mapping the node to the node's handle in the returned list.] SideEffects [nodeToHandle table is modified] SeeAlso [Ord_NetworkOrderRoots] ******************************************************************************/ 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 */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Orders the nodes of a network by the merging method.] Description [Orders the nodes of a network by the merging method. The parameters are the same as in OrdNetworkOrderTFIOfRoots.
This function implements an algorithm alluded to in Section 3.2 of Fujii et al., "Interleaving Based Variable Ordering Methods for OBDDs", ICCAD 1993, p. 38. The ordering returned is a topological ordering. The algorithm works as follows. For every node, a topological ordering on the tfi nodes is created and stored at the node. This is done recursively. For leaves of the recursion, a trivial list of length 1 is created. For the general case, the order lists at the fanins are merged together, and then the node itself is appended to the end of the list. The merging is done from the highest priority fanin to the lowest priority, where a "merge right" or "merge right" is performed, depending on the value of method. Nodes with greater depth have higher priority.
TODO: This function is consuming more memory than is necessary. Specifically, a node list is computed and stored at each network node. Currently, this list is not freed until the very end of the node ordering computation. Instead, a reference count could be precomputed for each node, and when this falls to zero, the list can be immediately freed.] SideEffects [nodeToHandle table is modified] SeeAlso [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByMerging OrdNetworkComputeNodeDepths] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Orders the fanins of a node, and then orders the node itself.] Description [Orders the fanins of a node, and then orders the node itself. The fanins of a node are visited in order of decreasing depth, and their orderings are merged. The node appears in the order just after its fanins, yielding a topological order. If node has already been visited, then simply return the order previously found.] SideEffects [] SeeAlso [OrdNetworkComputeNodeDepths NetworkOrderTFIOfRootsByMerging] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Orders the nodes of a network by the appending method.] Description [Orders the nodes of a network by the appending method. The parameters are the same as in OrdNetworkOrderTFIOfRoots.
This function implements the algorithm of Malik, et al. "Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment," ICCAD, 1988. The ordering returned is a topological ordering. The algorithm works as follows. For every root, a topological ordering on the tfi nodes not yet ordered is generated by DFS. The ordered obtained starting from a root is appended to the order already found.] SideEffects [nodeToHandle table is modified] SeeAlso [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByAppending] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Orders the fanins of a node, and then orders the node itself.] Description [Orders the fanins of a node, and then orders the node itself. The fanins of a node are visited in order of decreasing depth. The node appears in the order just after its fanins, yielding a topological order. If node has already been visited, then simply return the order previously found.] Comment [The nodeToHandle table serves as the visited table for the DFS.] SideEffects [nodeToHandle table is modified] SeeAlso [NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths] ******************************************************************************/ 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); } /**Function******************************************************************** Synopsis [Orders the nodes of a network by the interleaving method.] Description [Orders the nodes of a network by the interleaving method. The parameters are the same as in OrdNetworkOrderTFIOfRoots.
This function implements Algorithm 2 of Fujii, et al. "Inteleaving Based Variable Ordering Methods for Ordered Binary Decision Diagrams," ICCAD, 1993. The ordering returned is a topological ordering. The algorithm is a modified DFS that keeps track of an insertion point so that variables in the tfi of the second and successive outputs be properly interleaved with the variables already ordered.] SideEffects [nodeToHandle table is modified] SeeAlso [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByInterleaving] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Orders the fanins of a node, and then orders the node itself.] Description [Orders the fanins of a node, and then orders the node itself. The fanins of a node are visited in order of decreasing depth. The node appears in the order just after its fanins, yielding a topological order. If node has already been visited, then simply update the info on the output from which it was last reached, and change the insertion point.] Comment [The nodeToHandle table serves as the visited table for the DFS.] SideEffects [nodeToHandle table is modified] SeeAlso [NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths] ******************************************************************************/ 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); } /**Function******************************************************************** Synopsis [Initializes structure needed to maintain state of ordering routine.] Description [Allocates and initializes data structure needed to maintain the state of the variable ordering routine.] SideEffects [] Comment [The node depths are not stored in a hash table of orderingState, because, for OrdNodesFromArrayCompareDepth, we need to be able to access the depth of a node given *just* the node.] SeeAlso [OrderingStateFree] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Updates the insertion point in orderingState.] Description [Updates the insertion point in orderingState. Assumes that node is already in nodeToHandle.] SideEffects [] SeeAlso [NetworkInitializeOrderingState] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Frees all memory associated with an ordering state.] SideEffects [] SeeAlso [NetworkInitializeOrderingState] ******************************************************************************/ 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); } /**Function******************************************************************** Synopsis [Gets the order list of a node.] Description [Gets the order list of a node. This is a topological ordering of all the nodes in the transitive fanin of the node. Returns NULL if node is not in the nodeToOrderList hash table of orderingState.] SideEffects [] SeeAlso [NodeSetOrderList] ******************************************************************************/ static lsList NodeReadOrderList( Ntk_Node_t * node, OrderingState_t * orderingState) { lsList orderList = (lsList) NULL; st_lookup(orderingState->nodeToOrderList, node, &orderList); return orderList; } /**Function******************************************************************** Synopsis [Sets the orderList of a node.] SideEffects [] SeeAlso [NodeReadOrderList] ******************************************************************************/ static void NodeSetOrderList( Ntk_Node_t * node, lsList orderList, OrderingState_t * orderingState) { st_insert(orderingState->nodeToOrderList, (char *) node, (char *) orderList); } /**Function******************************************************************** Synopsis [Gets the from root of a node.] Description [Gets the from node of a node. This is the root from which the node was last reached during DFS. Returns NULL if node is not in the from hash table of orderingState.] SideEffects [none] SeeAlso [NodeSetFrom] ******************************************************************************/ 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; } /**Function******************************************************************** Synopsis [Sets the from root of a node to the current root.] SideEffects [The from table of orderingState is modified.] SeeAlso [NodeReadFrom] ******************************************************************************/ static void NodeSetFrom( Ntk_Node_t * node, OrderingState_t * orderingState) { st_insert(orderingState->from, (char *) node, (char *) orderingState->root); }