[14] | 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 | |
---|
| 40 | static 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 | ******************************************************************************/ |
---|
| 106 | lsList |
---|
| 107 | Ord_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 | ******************************************************************************/ |
---|
| 180 | lsList |
---|
| 181 | OrdNetworkOrderRootsByDepth( |
---|
| 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 | ******************************************************************************/ |
---|
| 227 | void |
---|
| 228 | OrdNodeAddToList( |
---|
| 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 | |
---|