source: vis_dev/vis-2.3/src/ord/ordNodes.c @ 36

Last change on this file since 36 was 14, checked in by cecile, 13 years ago

vis2.3

File size: 29.5 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ordNodes.c]
4
5  PackageName [ord]
6
7  Synopsis    [Routines to order the nodes in the TFI of the roots of a network.]
8
9  Description [Routines to order the nodes in the TFI of the roots of a
10  network. To add a new method, create a new value for the Ord_NodeMethod
11  enumerated type, and add a call to the new procedure from
12  OrdNetworkOrderTFIOfRoots.]
13
14  Author      [Tom Shiple and Fabio Somenzi]
15
16  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
17  All rights reserved.
18
19  Permission is hereby granted, without written agreement and without license
20  or royalty fees, to use, copy, modify, and distribute this software and its
21  documentation for any purpose, provided that the above copyright notice and
22  the following two paragraphs appear in all copies of this software.
23
24  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
25  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
26  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
27  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
30  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
31  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
32  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
33  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
34
35******************************************************************************/
36
37#include "ordInt.h"
38
39static char rcsid[] UNUSED = "$Id: ordNodes.c,v 1.12 2005/04/16 06:15:25 fabio Exp $";
40
41/*---------------------------------------------------------------------------*/
42/* Constant declarations                                                     */
43/*---------------------------------------------------------------------------*/
44
45
46/*---------------------------------------------------------------------------*/
47/* Type declarations                                                         */
48/*---------------------------------------------------------------------------*/
49
50
51/*---------------------------------------------------------------------------*/
52/* Structure declarations                                                    */
53/*---------------------------------------------------------------------------*/
54/**Struct**********************************************************************
55
56  Synopsis    [State needed for performing variable ordering.]
57
58  SeeAlso     [NetworkInitializeOrderingState OrderingStateFree]
59
60******************************************************************************/
61typedef struct OrderingStateStruct {
62  st_table *nodeToOrderList;    /* Ntk_Node_t * to lsList; top. order of tfi
63                                   nodes */
64  st_table *from;               /* Ntk_Node_t * to Ntk_Node_t */
65  lsGen last;                   /* insertion point */
66  Ntk_Node_t *root;             /* current output */
67} OrderingState_t;
68
69/*---------------------------------------------------------------------------*/
70/* Variable declarations                                                     */
71/*---------------------------------------------------------------------------*/
72
73
74/*---------------------------------------------------------------------------*/
75/* Macro declarations                                                        */
76/*---------------------------------------------------------------------------*/
77
78
79/**AutomaticStart*************************************************************/
80
81/*---------------------------------------------------------------------------*/
82/* Static function prototypes                                                */
83/*---------------------------------------------------------------------------*/
84
85static lsList NetworkOrderTFIOfRootsByMerging(Ntk_Network_t *network, lsList roots, Ord_ListMergeMethod method, st_table *nodeToHandle, int verbose);
86static lsList NodeOrderRecursivelyByMerging(Ntk_Node_t * node, OrderingState_t * orderingState, Ord_ListMergeMethod method, int verbose);
87static lsList NetworkOrderTFIOfRootsByAppending(Ntk_Network_t *network, lsList roots, st_table *nodeToHandle, int verbose);
88static void NodeOrderRecursivelyByAppending(Ntk_Node_t * node, lsList orderList, st_table *nodeToHandle, int verbose);
89static lsList NetworkOrderTFIOfRootsByInterleaving(Ntk_Network_t *network, lsList roots, st_table *nodeToHandle, int verbose);
90static void NodeOrderRecursivelyByInterleaving(Ntk_Node_t * node, lsList orderList, st_table *nodeToHandle, OrderingState_t *orderingState, int verbose);
91static OrderingState_t * NetworkInitializeOrderingState(Ntk_Network_t * network);
92static void OrderingStateSetLast(Ntk_Node_t * node, st_table * nodeToHandle, OrderingState_t * orderingState);
93static void OrderingStateFree(OrderingState_t * orderingState);
94static lsList NodeReadOrderList(Ntk_Node_t * node, OrderingState_t * orderingState);
95static void NodeSetOrderList(Ntk_Node_t * node, lsList orderList, OrderingState_t * orderingState);
96static Ntk_Node_t * NodeReadFrom(Ntk_Node_t * node, OrderingState_t * orderingState);
97static void NodeSetFrom(Ntk_Node_t * node, OrderingState_t * orderingState);
98
99/**AutomaticEnd***************************************************************/
100
101
102/*---------------------------------------------------------------------------*/
103/* Definition of exported functions                                          */
104/*---------------------------------------------------------------------------*/
105
106
107/*---------------------------------------------------------------------------*/
108/* Definition of internal functions                                          */
109/*---------------------------------------------------------------------------*/
110
111/**Function********************************************************************
112
113  Synopsis    [Orders the nodes of a network in TFI of roots.]
114
115  Description [Orders the nodes of a network that are in the transitive fanin
116  of the list of roots, including the roots themselves.  The roots are visited
117  in the order given in the root list.  Combinational inputs (primary inputs,
118  pseudo inputs, and latches) and constants terminate the recursion.  If you
119  want a latch next state function to be a root, then the corresponding data
120  input should be in the root list, not the latch itself. Note that next state
121  variables are not included in the ordering; these should be added as a
122  post-processing step.<p>
123
124  The different node ordering methods are documented in the static_order
125  command. If nodeMethod is Ord_NodesByDefault_c, then one of the ordering
126  methods is called by default.<p>
127
128  nodeToHandle should be an empty table created using st_init_table(st_ptrcmp,
129  st_ptrhash).  For every node in the returned list, there is an entry in
130  nodeToHandle mapping the node to the node's handle in the returned list.]
131
132  SideEffects [nodeToHandle table is modified]
133
134  SeeAlso     [Ord_NetworkOrderRoots]
135
136******************************************************************************/
137lsList
138OrdNetworkOrderTFIOfRoots(
139  Ntk_Network_t *network,
140  lsList  roots /* of Ntk_Node_t  */,
141  Ord_NodeMethod nodeOrderMethod,
142  st_table *nodeToHandle /* modified */,
143  int verbose)
144{
145  switch (nodeOrderMethod) {
146    case Ord_NodesByDefault_c:
147    case Ord_NodesByInterleaving_c:
148      return NetworkOrderTFIOfRootsByInterleaving(network, roots,
149                                                  nodeToHandle, verbose);
150    case Ord_NodesByMergingLeft_c:
151      return NetworkOrderTFIOfRootsByMerging(network, roots,
152                                             Ord_ListMergeLeft_c,
153                                             nodeToHandle, verbose);
154    case Ord_NodesByMergingRight_c:
155      return NetworkOrderTFIOfRootsByMerging(network, roots,
156                                             Ord_ListMergeRight_c,
157                                             nodeToHandle, verbose);
158    case Ord_NodesByAppending_c:
159      return NetworkOrderTFIOfRootsByAppending(network, roots,
160                                               nodeToHandle, verbose);
161    default:
162      fail("unrecognized node ordering method");
163      return (lsList) 0;
164  }
165}
166
167
168/*---------------------------------------------------------------------------*/
169/* Definition of static functions                                            */
170/*---------------------------------------------------------------------------*/
171
172/**Function********************************************************************
173
174  Synopsis    [Orders the nodes of a network by the merging method.]
175
176  Description [Orders the nodes of a network by the merging method.  The
177  parameters are the same as in OrdNetworkOrderTFIOfRoots.<p>
178 
179  This function implements an algorithm alluded to in Section 3.2 of Fujii et
180  al., "Interleaving Based Variable Ordering Methods for OBDDs", ICCAD 1993,
181  p. 38.  The ordering returned is a topological ordering.  The algorithm
182  works as follows.  For every node, a topological ordering on the tfi nodes
183  is created and stored at the node.  This is done recursively.  For leaves of
184  the recursion, a trivial list of length 1 is created.  For the general case,
185  the order lists at the fanins are merged together, and then the node itself
186  is appended to the end of the list.  The merging is done from the highest
187  priority fanin to the lowest priority, where a "merge right" or "merge
188  right" is performed, depending on the value of method. Nodes with greater
189  depth have higher priority.<p>
190
191  TODO: This function is consuming more memory than is
192  necessary. Specifically, a node list is computed and stored at each network
193  node.  Currently, this list is not freed until the very end of the node
194  ordering computation.  Instead, a reference count could be precomputed for
195  each node, and when this falls to zero, the list can be immediately freed.]
196
197  SideEffects [nodeToHandle table is modified]
198
199  SeeAlso     [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByMerging
200  OrdNetworkComputeNodeDepths]
201
202******************************************************************************/
203static lsList
204NetworkOrderTFIOfRootsByMerging(
205  Ntk_Network_t *network,
206  lsList  roots /* list of Ntk_Node_t  */,
207  Ord_ListMergeMethod method,
208  st_table *nodeToHandle /* modified */,
209  int verbose)
210{
211  lsGen            gen;
212  Ntk_Node_t      *root;
213  OrderingState_t *orderingState;
214  lsList           orderList = lsCreate(); /* return list */
215
216 
217  /*
218   * Compute and store the depth of each node in the network.  (The depth of a
219   * node is stored in the undef field of the node).
220   */
221  OrdNetworkComputeNodeDepths(network, roots);
222
223  /*
224   * Initialize the necessary state needed for recursing through the network.
225   */
226  orderingState = NetworkInitializeOrderingState(network);
227
228  /*
229   * For each root, recursively order all nodes in its transitive fanin, and
230   * merge this ordering into the nodes already ordered.
231   */
232  lsForEachItem(roots, gen, root) {
233    lsList rootOrderList = NodeOrderRecursivelyByMerging(root, orderingState,
234                                                         method, verbose);
235    Ord_ListMergeListUsingTable(orderList, rootOrderList, nodeToHandle, method);
236
237    if (verbose > 2) {
238      /* This can generate a lot of output. */
239      (void) fprintf(vis_stdout, "\nOrder list after merging node %s\n",
240                     Ntk_NodeReadName(root));
241      OrdNodeListWrite(vis_stdout, orderList);
242    }
243  }
244 
245  /*
246   * Clean up and return the ordering list.
247   */
248  OrderingStateFree(orderingState);
249  return orderList;
250}
251
252 
253/**Function********************************************************************
254
255  Synopsis    [Orders the fanins of a node, and then orders the node itself.]
256
257  Description [Orders the fanins of a node, and then orders the node
258  itself. The fanins of a node are visited in order of decreasing depth, and
259  their orderings are merged.  The node appears in the order just after its
260  fanins, yielding a topological order.  If node has already been visited,
261  then simply return the order previously found.]
262
263  SideEffects []
264
265  SeeAlso     [OrdNetworkComputeNodeDepths NetworkOrderTFIOfRootsByMerging]
266
267******************************************************************************/
268static lsList
269NodeOrderRecursivelyByMerging(
270  Ntk_Node_t * node,
271  OrderingState_t * orderingState,
272  Ord_ListMergeMethod method,
273  int verbose)
274{
275  lsList orderList;
276 
277 
278  /*
279   * If node has already been visited (i.e. its orderList is non-NULL), then
280   * just return the orderList already computed.
281   */
282  orderList = NodeReadOrderList(node, orderingState);
283  if (orderList != (lsList) NULL) {
284    return orderList;
285  }
286
287  /*
288   * Node has not yet been visited.  Create the orderList for node.
289   */
290  if (Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node)) {
291    /*
292     * Combinational inputs and constants terminate the recursion. If node is
293     * one of these, then just create an empty list, to which we will add the
294     * node.
295     */
296    orderList = lsCreate();
297  }
298  else if (Ntk_NodeReadNumFanins(node) == 1) {
299    /*
300     * If there is just one fanin, then just make a copy of the the fanin's
301     * orderList. This case is distinguished from the general case for
302     * efficiency.
303     */
304    lsList faninOrderList = NodeOrderRecursivelyByMerging(Ntk_NodeReadFaninNode(node, 0),
305                                                          orderingState,
306                                                          method, verbose);
307    orderList = lsCopy(faninOrderList, (lsGeneric (*) (lsGeneric)) NULL);
308  }
309  else {
310    int       i;
311    array_t  *sortedFanins;
312    st_table *nodeToHandle;
313
314    /*
315     * Sort the fanins of node in decreasing order of depth.  See
316     * OrdNetworkComputeNodeDepths.
317     */
318    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
319    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);
320
321    /*
322     * Start with an empty list for the orderList of the node.  Also, start
323     * with an empty nodeToHandle table.  This table is only used locally, and
324     * will be deleted below.
325     */
326    orderList = lsCreate();
327    nodeToHandle  = st_init_table(st_ptrcmp, st_ptrhash);
328   
329    /*
330     * Recursively visit the fanins in order of decreasing depth. The
331     * nodeToHandle table keeps track of the nodes currently in orderList.
332     */
333    for (i = 0; i < array_n(sortedFanins); i++) {
334      Ntk_Node_t *fanin          = array_fetch(Ntk_Node_t *, sortedFanins, i);
335      lsList      faninOrderList = NodeOrderRecursivelyByMerging(fanin,
336                                                                 orderingState,
337                                                                 method, verbose);
338      /*
339       * Merge faninOrderList into the list of nodes already ordered.
340       */
341      Ord_ListMergeListUsingTable(orderList, faninOrderList, nodeToHandle, method);
342    }
343    array_free(sortedFanins);
344    st_free_table(nodeToHandle);
345  }
346
347  /*
348   * Regardless of the branch taken above, add node to the end of the
349   * orderList, and set the node's orderList.
350   */
351  (void) lsNewEnd(orderList, (lsGeneric) node, LS_NH);
352  NodeSetOrderList(node, orderList, orderingState);
353
354  if (verbose > 2) {
355    /* This can generate a lot of output. */
356    (void) fprintf(vis_stdout, "\nOrder list for node %s\n", Ntk_NodeReadName(node));
357    OrdNodeListWrite(vis_stdout, orderList);
358  }
359 
360  return orderList;
361}
362
363
364/**Function********************************************************************
365
366  Synopsis    [Orders the nodes of a network by the appending method.]
367
368  Description [Orders the nodes of a network by the appending method.  The
369  parameters are the same as in OrdNetworkOrderTFIOfRoots.<p>
370 
371  This function implements the algorithm of Malik, et al. "Logic Verification
372  using Binary Decision Diagrams in a Logic Synthesis Environment," ICCAD,
373  1988.  The ordering returned is a topological ordering.  The algorithm works
374  as follows.  For every root, a topological ordering on the tfi nodes not
375  yet ordered is generated by DFS. The ordered obtained starting from a root
376  is appended to the order already found.]
377
378  SideEffects [nodeToHandle table is modified]
379
380  SeeAlso     [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByAppending]
381
382******************************************************************************/
383static lsList
384NetworkOrderTFIOfRootsByAppending(
385  Ntk_Network_t *network,
386  lsList  roots /* list of Ntk_Node_t  */,
387  st_table *nodeToHandle /* modified */,
388  int verbose)
389{
390  lsGen       gen;
391  Ntk_Node_t *root;
392  lsList      orderList = lsCreate(); /* return list */
393
394 
395  /*
396   * Compute and store the depth of each node in the network.  (The depth of a
397   * node is stored in the undef field of the node).
398   */
399  OrdNetworkComputeNodeDepths(network, roots);
400
401  if (verbose > 1) {
402    Ntk_Node_t *node;
403    (void) fprintf(vis_stdout, "\nDepths of network nodes:\n");
404    Ntk_NetworkForEachNode(network, gen, node) {
405      (void) fprintf(vis_stdout, "%s: depth = %ld\n", Ntk_NodeReadName(node),
406                     OrdNodeReadDepth(node));
407    }
408  }
409
410  /*
411   * For each root, recursively order all nodes in its transitive fanin.
412   */
413  lsForEachItem(roots, gen, root) {
414    NodeOrderRecursivelyByAppending(root, orderList, nodeToHandle, verbose);
415  }
416 
417  return orderList;
418}
419
420
421/**Function********************************************************************
422
423  Synopsis    [Orders the fanins of a node, and then orders the node itself.]
424
425  Description [Orders the fanins of a node, and then orders the node
426  itself. The fanins of a node are visited in order of decreasing depth.  The
427  node appears in the order just after its fanins, yielding a topological
428  order.  If node has already been visited, then simply return the order
429  previously found.]
430
431  Comment [The nodeToHandle table serves as the visited table for the DFS.]
432 
433  SideEffects [nodeToHandle table is modified]
434
435  SeeAlso     [NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths]
436
437******************************************************************************/
438static void
439NodeOrderRecursivelyByAppending(
440  Ntk_Node_t * node,
441  lsList orderList,
442  st_table *nodeToHandle,
443  int verbose)
444{
445  lsHandle handle;
446 
447  /*
448   * If node has already been visited (i.e. its in the nodeToHandle table), then
449   * just return.
450   */
451  if (st_is_member(nodeToHandle, (char *) node)) {
452    return;
453  }
454 
455  /*
456   * Node has not yet been visited.  Recurse on the inputs, and then add node
457   * to the end of the current ordering.
458   */
459  if (!(Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node))) {
460    /*
461     * Combinational inputs and constants terminate the recursion. If node is
462     * not one of these, then recurse on the inputs.
463     */
464    int       i;
465    array_t  *sortedFanins;
466
467    /*
468     * Sort the fanins of node in decreasing order of depth.  See
469     * OrdNetworkComputeNodeDepths.
470     */
471    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
472    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);
473
474    /*
475     * Recursively visit the fanins in order of decreasing depth. The
476     * nodeToHandle table keeps track of the nodes currently in orderList.
477     */
478    for (i = 0; i < array_n(sortedFanins); i++) {
479      Ntk_Node_t *fanin = array_fetch(Ntk_Node_t *, sortedFanins, i);
480
481      NodeOrderRecursivelyByAppending(fanin, orderList, nodeToHandle, verbose);
482    }
483    array_free(sortedFanins);
484  }
485
486  /*
487   * Regardless of the branch taken above, add node to the end of the
488   * orderList and to the nodeToHandle table.
489   */
490  (void) lsNewEnd(orderList, (lsGeneric) node, &handle);
491  st_insert(nodeToHandle, (char *) node, (char *) handle);
492}
493
494 
495/**Function********************************************************************
496
497  Synopsis    [Orders the nodes of a network by the interleaving method.]
498
499  Description [Orders the nodes of a network by the interleaving method.  The
500  parameters are the same as in OrdNetworkOrderTFIOfRoots.<p>
501 
502  This function implements Algorithm 2 of Fujii, et al. "Inteleaving Based
503  Variable Ordering Methods for Ordered Binary Decision Diagrams," ICCAD,
504  1993.  The ordering returned is a topological ordering.  The algorithm is a
505  modified DFS that keeps track of an insertion point so that variables in the
506  tfi of the second and successive outputs be properly interleaved with the
507  variables already ordered.]
508
509  SideEffects [nodeToHandle table is modified]
510
511  SeeAlso     [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByInterleaving]
512
513******************************************************************************/
514static lsList
515NetworkOrderTFIOfRootsByInterleaving(
516  Ntk_Network_t *network,
517  lsList roots /* list of Ntk_Node_t  */,
518  st_table *nodeToHandle /* modified */,
519  int verbose)
520{
521  lsGen       gen;
522  Ntk_Node_t *root;
523  lsList      orderList = lsCreate(); /* return list */
524  OrderingState_t *orderingState;
525
526  /*
527   * Compute and store the depth of each node in the network.  (The depth of a
528   * node is stored in the undef field of the node.)
529   */
530  OrdNetworkComputeNodeDepths(network, roots);
531
532  /*
533   * Initialize the state needed for recurring through the network.
534   */
535  orderingState = NetworkInitializeOrderingState(network);
536
537  if (verbose > 1) {
538    Ntk_Node_t *node;
539    (void) fprintf(vis_stdout, "\nDepths of network nodes:\n");
540    Ntk_NetworkForEachNode(network, gen, node) {
541      (void) fprintf(vis_stdout, "%s: depth = %ld\n", Ntk_NodeReadName(node),
542                     OrdNodeReadDepth(node));
543    }
544  }
545
546  /*
547   * For each root, recursively order all nodes in its transitive fanin.
548   */
549  lsForEachItem(roots, gen, root) {
550    orderingState->root = root;
551    orderingState->last = lsStart(orderList);
552    NodeOrderRecursivelyByInterleaving(root, orderList, nodeToHandle,
553                                       orderingState, verbose);
554    lsFinish(orderingState->last);
555
556    if (verbose > 2) {
557      /* This can generate a lot of output. */
558      (void) fprintf(vis_stdout, "\nOrder list after merging node %s\n",
559                     Ntk_NodeReadName(root));
560      OrdNodeListWrite(vis_stdout, orderList);
561    }
562  }
563
564  /*
565   * Clean up and return the ordering list.
566   */
567  OrderingStateFree(orderingState);
568  return orderList;
569}
570
571 
572/**Function********************************************************************
573
574  Synopsis    [Orders the fanins of a node, and then orders the node itself.]
575
576  Description [Orders the fanins of a node, and then orders the node
577  itself. The fanins of a node are visited in order of decreasing depth.  The
578  node appears in the order just after its fanins, yielding a topological
579  order.  If node has already been visited, then simply update the info on
580  the output from which it was last reached, and change the insertion point.]
581
582  Comment [The nodeToHandle table serves as the visited table for the DFS.]
583 
584  SideEffects [nodeToHandle table is modified]
585
586  SeeAlso     [NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths]
587
588******************************************************************************/
589static void
590NodeOrderRecursivelyByInterleaving(
591  Ntk_Node_t * node,
592  lsList orderList,
593  st_table *nodeToHandle,
594  OrderingState_t *orderingState,
595  int verbose)
596{
597  lsHandle handle;
598 
599  /*
600   * If node has already been visited (i.e., it is in the nodeToHandle table),
601   * then update the info on the output from which it was last reached,
602   * and change the insertion point to this node.
603   */
604  if (st_is_member(nodeToHandle, (char *) node)) {
605    if (NodeReadFrom(node, orderingState) != orderingState->root) {
606      OrderingStateSetLast(node, nodeToHandle, orderingState);
607      NodeSetFrom(node, orderingState);
608    }
609    return;
610  }
611
612  /*
613   * Node has not yet been visited.  Recur on the inputs, and then add node
614   * to the end of the current ordering.
615   */
616  if (!(Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node))) {
617    /*
618     * Combinational inputs and constants terminate the recursion. If node is
619     * not one of these, then recur on the inputs.
620     */
621    int       i;
622    array_t  *sortedFanins;
623
624    /*
625     * Sort the fanins of node in decreasing order of depth.  See
626     * OrdNetworkComputeNodeDepths.
627     */
628    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
629    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);
630
631    /*
632     * Recursively visit the fanins in order of decreasing depth. The
633     * nodeToHandle table keeps track of the nodes currently in orderList.
634     */
635    for (i = 0; i < array_n(sortedFanins); i++) {
636      Ntk_Node_t *fanin = array_fetch(Ntk_Node_t *, sortedFanins, i);
637
638      NodeOrderRecursivelyByInterleaving(fanin, orderList, nodeToHandle,
639                                         orderingState,verbose);
640    }
641    array_free(sortedFanins);
642  }
643
644  /*
645   * Regardless of the branch taken above, add node to orderList at the
646   * insertion point and to the nodeToHandle table. Make node the new
647   * insertion point.
648   */
649  NodeSetFrom(node, orderingState);
650  (void) lsInBefore(orderingState->last, (lsGeneric) node, &handle);
651  st_insert(nodeToHandle, (char *) node, (char *) handle);
652  OrderingStateSetLast(node, nodeToHandle, orderingState);
653}
654
655
656/**Function********************************************************************
657
658  Synopsis    [Initializes structure needed to maintain state of ordering
659  routine.]
660
661  Description [Allocates and initializes data structure needed to maintain the
662  state of the variable ordering routine.]
663
664  SideEffects []
665
666  Comment [The node depths are not stored in a hash table of orderingState,
667  because, for OrdNodesFromArrayCompareDepth, we need to be able to access the
668  depth of a node given *just* the node.]
669 
670  SeeAlso     [OrderingStateFree]
671
672******************************************************************************/
673static OrderingState_t *
674NetworkInitializeOrderingState(
675  Ntk_Network_t * network)
676{
677  OrderingState_t *orderingState = ALLOC(OrderingState_t, 1);
678
679  /* nodeToOrderList is used by the merging method. */
680  orderingState->nodeToOrderList = st_init_table(st_ptrcmp, st_ptrhash);
681
682  /* from, last, and root used by the interleaving method. */
683  orderingState->from = st_init_table(st_ptrcmp, st_ptrhash);
684  orderingState->last = NULL;
685  orderingState->root = NULL;
686
687  return orderingState;
688}
689
690
691/**Function********************************************************************
692
693  Synopsis    [Updates the insertion point in orderingState.]
694
695  Description [Updates the insertion point in orderingState. Assumes that
696  node is already in nodeToHandle.]
697
698  SideEffects []
699
700  SeeAlso     [NetworkInitializeOrderingState]
701
702******************************************************************************/
703static void
704OrderingStateSetLast(
705  Ntk_Node_t * node,
706  st_table * nodeToHandle,
707  OrderingState_t * orderingState)
708{
709  lsHandle handle;
710  lsGen gen;
711  lsGeneric data;
712
713  /* Dispose of the current generator. */
714  lsFinish(orderingState->last);
715
716  /* Get a handle for the current node. */
717  st_lookup(nodeToHandle, node, &handle);
718
719  /*
720   * Create a new generator positioned after node and register it
721   * in orderingState.
722   */
723  gen = lsGenHandle(handle,&data,LS_AFTER);
724  orderingState->last = gen;
725}
726
727/**Function********************************************************************
728
729  Synopsis    [Frees all memory associated with an ordering state.]
730
731  SideEffects []
732
733  SeeAlso     [NetworkInitializeOrderingState]
734
735******************************************************************************/
736static void
737OrderingStateFree(
738  OrderingState_t * orderingState)
739{
740  st_generator *stGen;
741  lsList orderList;
742  Ntk_Node_t *node;
743 
744  st_foreach_item(orderingState->nodeToOrderList, stGen, &node, &orderList) {
745    (void) lsDestroy(orderList, (void (*) (lsGeneric)) NULL);
746  }
747 
748  st_free_table(orderingState->nodeToOrderList);
749  st_free_table(orderingState->from);
750 
751  FREE(orderingState);
752}
753
754
755/**Function********************************************************************
756
757  Synopsis    [Gets the order list of a node.]
758
759  Description [Gets the order list of a node.  This is a topological ordering
760  of all the nodes in the transitive fanin of the node.  Returns NULL if node
761  is not in the nodeToOrderList hash table of orderingState.]
762 
763  SideEffects []
764
765  SeeAlso     [NodeSetOrderList]
766
767******************************************************************************/
768static lsList
769NodeReadOrderList(
770  Ntk_Node_t * node,
771  OrderingState_t * orderingState)
772{
773  lsList orderList = (lsList) NULL;
774
775  st_lookup(orderingState->nodeToOrderList, node, &orderList);
776 
777  return orderList;
778}
779
780
781/**Function********************************************************************
782
783  Synopsis    [Sets the orderList of a node.]
784
785  SideEffects []
786
787  SeeAlso     [NodeReadOrderList]
788
789******************************************************************************/
790static void
791NodeSetOrderList(
792  Ntk_Node_t * node,
793  lsList orderList,
794  OrderingState_t * orderingState)
795{
796  st_insert(orderingState->nodeToOrderList, (char *) node, (char *) orderList);
797}
798
799
800/**Function********************************************************************
801
802  Synopsis    [Gets the from root of a node.]
803
804  Description [Gets the from node of a node.  This is the root from
805  which the node was last reached during DFS. Returns NULL if node is
806  not in the from hash table of orderingState.]
807 
808  SideEffects [none]
809
810  SeeAlso     [NodeSetFrom]
811
812******************************************************************************/
813static Ntk_Node_t *
814NodeReadFrom(
815  Ntk_Node_t * node,
816  OrderingState_t * orderingState)
817{
818  Ntk_Node_t * from = NULL;
819
820  st_lookup(orderingState->from, node, &from);
821 
822  return from;
823}
824
825
826/**Function********************************************************************
827
828  Synopsis    [Sets the from root of a node to the current root.]
829
830  SideEffects [The from table of orderingState is modified.]
831
832  SeeAlso     [NodeReadFrom]
833
834******************************************************************************/
835static void
836NodeSetFrom(
837  Ntk_Node_t * node,
838  OrderingState_t * orderingState)
839{
840  st_insert(orderingState->from, (char *) node, (char *) orderingState->root);
841}
Note: See TracBrowser for help on using the repository browser.