source: vis_dev/vis-2.3/src/ord/ordRoots.c @ 25

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

vis2.3
File size: 9.0 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ordRoots.c]
4
5  PackageName [ord]
6
7  Synopsis    [Routines to order the roots of the network.]
8
9  Description [Routines to order the roots of the network.  The nodes of the
10  network are explored in DFS order from the roots, in the root order
11  computed. To add a new method, create a new value for the Ord_RootMethod
12  enumerated type, and add a call to the new procedure from
13  Ord_NetworkOrderRoots.]
14
15  Author      [Tom Shiple]
16
17  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
18  All rights reserved.
19
20  Permission is hereby granted, without written agreement and without license
21  or royalty fees, to use, copy, modify, and distribute this software and its
22  documentation for any purpose, provided that the above copyright notice and
23  the following two paragraphs appear in all copies of this software.
24
25  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
26  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
27  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
28  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
31  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
32  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
33  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
34  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
35
36******************************************************************************/
37
38#include "ordInt.h"
39
40static char rcsid[] UNUSED = "$Id: ordRoots.c,v 1.7 2002/08/27 08:43:16 fabio Exp $";
41
42/*---------------------------------------------------------------------------*/
43/* Constant declarations                                                     */
44/*---------------------------------------------------------------------------*/
45
46
47/*---------------------------------------------------------------------------*/
48/* Type declarations                                                         */
49/*---------------------------------------------------------------------------*/
50
51
52/*---------------------------------------------------------------------------*/
53/* Structure declarations                                                    */
54/*---------------------------------------------------------------------------*/
55
56
57/*---------------------------------------------------------------------------*/
58/* Variable declarations                                                     */
59/*---------------------------------------------------------------------------*/
60
61
62/*---------------------------------------------------------------------------*/
63/* Macro declarations                                                        */
64/*---------------------------------------------------------------------------*/
65
66
67/**AutomaticStart*************************************************************/
68
69/*---------------------------------------------------------------------------*/
70/* Static function prototypes                                                */
71/*---------------------------------------------------------------------------*/
72
73
74/**AutomaticEnd***************************************************************/
75
76
77/*---------------------------------------------------------------------------*/
78/* Definition of exported functions                                          */
79/*---------------------------------------------------------------------------*/
80
81/**Function********************************************************************
82
83  Synopsis    [Orders the roots of a network.]
84
85  Description [Orders the combinational outputs of a network.  The data inputs
86  of latches always precede the other combinational outputs.  This gives
87  priority to finding the best ordering for the variables in the next state
88  functions. <p>
89
90  The different root ordering methods are documented in the static_order
91  command. If rootMethod is Ord_RootsByDefault_c, then one of the ordering
92  methods is called by default, depending on the number of latches in the
93  network.<p>
94
95  An arbitrary subset of roots can be specified in partialOrder. No check is
96  made to determine if the nodes in partialOrder are contained within the set
97  specified by orderType.  If partialOrder is non-NULL, then a total order on
98  the roots is computed according to rootMethod (as described above), and then
99  the computed order is merged into the partialOrder.]
100
101  SideEffects []
102
103  SeeAlso     [OrdNetworkOrderRootsByDepth OrdNetworkOrderRootsByPerm]
104
105******************************************************************************/
106lsList
107Ord_NetworkOrderRoots(
108  Ntk_Network_t *network,
109  Ord_RootMethod rootMethod,
110  lsList partialOrder,
111  boolean verbose)
112{
113  lsList rootOrderList;
114 
115  switch (rootMethod) {
116    case Ord_RootsByDepth_c:
117      rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose); 
118      break;
119    case Ord_RootsByPerm_c:
120      rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
121      break;
122    case Ord_RootsByDefault_c:
123      /*
124       * RootByPerm method is cubic in the number of latches, so use it by
125       * default only if the number of latches is not too large (30 is somewhat
126       * arbitrary).
127       */
128      if (Ntk_NetworkReadNumLatches(network) < 30) {
129        rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
130      }
131      else {
132        rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose);
133      }
134      break;
135    default:
136      fail("unrecognized root order method");
137  }
138
139  /*
140   * If a partial order is supplied, merge (left, arbitrarily) the computed
141   * order into the supplied order, to get a total ordering on all of the
142   * roots.
143   */
144  if (partialOrder != (lsList) NULL) {
145    lsList partialOrderCopy = lsCopy(partialOrder,
146                                     (lsGeneric (*) (lsGeneric)) NULL);
147
148    Ord_ListMergeList(partialOrderCopy, rootOrderList, Ord_ListMergeLeft_c);
149    (void) lsDestroy(rootOrderList, (void (*) (lsGeneric)) NULL);
150    return partialOrderCopy;
151  }
152  else {
153    return rootOrderList;
154  }
155}
156
157   
158/*---------------------------------------------------------------------------*/
159/* Definition of internal functions                                          */
160/*---------------------------------------------------------------------------*/
161
162/**Function********************************************************************
163
164  Synopsis [Computes a total ordering on the combinational outputs of a
165  network.]
166
167  Description [Computes a total ordering on the combinational outputs of a
168  network.  First, the depth of each combinational output is calculated.  The
169  depth of a node is the longest path (going backwards) to a combinational
170  input or constant. Then, the algorithm creates two lists: 1) data inputs to
171  latches, and 2) all remaining combinational outputs. Next, each list is
172  sorted in order of decreasing depth.  Finally, the second list is appended
173  to the first.]
174
175  SideEffects []
176
177  SeeAlso     [Ord_NetworkOrderRoots OrdNetworkComputeNodeDepths]
178
179******************************************************************************/
180lsList
181OrdNetworkOrderRootsByDepth(
182  Ntk_Network_t *network,
183  boolean verbose)
184{
185  lsGen       gen;
186  Ntk_Node_t *node;
187  st_table   *processedTable = st_init_table(st_ptrcmp, st_ptrhash);
188  lsList dataInputs = lsCreate();
189  lsList otherCombOuts = lsCreate();
190  lsList combOutputs = Ntk_NetworkReadCombOutputs(network);
191
192  /*
193   * A node can drive more than one latch data input, latch initial input,
194   * or primary output. Use a hash table to ensure that no node appears twice
195   * across the two lists.
196   */
197  Ntk_NetworkForEachCombOutput(network, gen, node) {
198    if (Ntk_NodeTestIsLatchDataInput(node)) {
199      OrdNodeAddToList(dataInputs, processedTable, node);
200    }
201    else {
202      OrdNodeAddToList(otherCombOuts, processedTable, node);
203    }
204  }
205  st_free_table(processedTable);
206
207  /* Compute depth of all combinational outputs. */
208  OrdNetworkComputeNodeDepths(network, combOutputs);
209
210  /* Sort each list independently. */
211  lsSort(dataInputs, OrdNodesFromListCompareDepth);
212  lsSort(otherCombOuts, OrdNodesFromListCompareDepth);
213
214  Ord_ListAppendList(dataInputs, otherCombOuts);
215  (void) lsDestroy(otherCombOuts, (void (*) (lsGeneric)) NULL);
216 
217  return dataInputs;
218}
219
220/**Function********************************************************************
221
222  Synopsis    [Inserts a node into a list, unless it already appears in the list.]
223
224  SideEffects []
225
226******************************************************************************/
227void
228OrdNodeAddToList(
229  lsList nodeList,
230  st_table *nodeTable,
231  Ntk_Node_t *node)
232{
233  if (!st_is_member(nodeTable, (char *) node)) {
234    st_insert(nodeTable, (char *) node, NIL(char));
235    (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH);
236  }
237}
238
239
240
241/*---------------------------------------------------------------------------*/
242/* Definition of static functions                                            */
243/*---------------------------------------------------------------------------*/
244
Note: See TracBrowser for help on using the repository browser.