[14] | 1 | /**CFile*********************************************************************** |
---|
| 2 | |
---|
| 3 | FileName [ordMain.c] |
---|
| 4 | |
---|
| 5 | PackageName [ord] |
---|
| 6 | |
---|
| 7 | Synopsis [Routines for static ordering of MDD variables.] |
---|
| 8 | |
---|
| 9 | Author [Adnan Aziz, Tom Shiple, Serdar Tasiran] |
---|
| 10 | |
---|
| 11 | Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. |
---|
| 12 | All rights reserved. |
---|
| 13 | |
---|
| 14 | Permission is hereby granted, without written agreement and without license |
---|
| 15 | or royalty fees, to use, copy, modify, and distribute this software and its |
---|
| 16 | documentation for any purpose, provided that the above copyright notice and |
---|
| 17 | the following two paragraphs appear in all copies of this software. |
---|
| 18 | |
---|
| 19 | IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR |
---|
| 20 | DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT |
---|
| 21 | OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF |
---|
| 22 | CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
---|
| 23 | |
---|
| 24 | THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, |
---|
| 25 | INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
---|
| 26 | FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN |
---|
| 27 | "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE |
---|
| 28 | MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.] |
---|
| 29 | |
---|
| 30 | ******************************************************************************/ |
---|
| 31 | |
---|
| 32 | #include "ordInt.h" |
---|
| 33 | |
---|
| 34 | static char rcsid[] UNUSED = "$Id: ordMain.c,v 1.17 2005/04/16 06:15:25 fabio Exp $"; |
---|
| 35 | |
---|
| 36 | /*---------------------------------------------------------------------------*/ |
---|
| 37 | /* Constant declarations */ |
---|
| 38 | /*---------------------------------------------------------------------------*/ |
---|
| 39 | |
---|
| 40 | /*---------------------------------------------------------------------------*/ |
---|
| 41 | /* Structure declarations */ |
---|
| 42 | /*---------------------------------------------------------------------------*/ |
---|
| 43 | |
---|
| 44 | /**AutomaticStart*************************************************************/ |
---|
| 45 | |
---|
| 46 | /*---------------------------------------------------------------------------*/ |
---|
| 47 | /* Static function prototypes */ |
---|
| 48 | /*---------------------------------------------------------------------------*/ |
---|
| 49 | |
---|
| 50 | static int NodesCompareDepth(Ntk_Node_t *node1, Ntk_Node_t *node2); |
---|
| 51 | static long NodeComputeDepth(Ntk_Node_t * node); |
---|
| 52 | static void NetworkAddDanglingNodesToOrderList(Ntk_Network_t * network, lsList nodeOrderList, st_table *nodeToHandle); |
---|
| 53 | static void NetworkAddNSVarsToOrderList(Ntk_Network_t * network, lsList nodeOrderList, st_table *nodeToHandle, boolean nsAfterSupport); |
---|
| 54 | static lsList LatchNSListConvertToLatchDataInputList(lsList latchNSList); |
---|
| 55 | static void NodeSetDepth(Ntk_Node_t * node, long depth); |
---|
| 56 | static void MddGroupVariables(mdd_manager *mddMgr, int initMddId, int blockSize); |
---|
| 57 | |
---|
| 58 | /**AutomaticEnd***************************************************************/ |
---|
| 59 | |
---|
| 60 | |
---|
| 61 | /*---------------------------------------------------------------------------*/ |
---|
| 62 | /* Definition of exported functions */ |
---|
| 63 | /*---------------------------------------------------------------------------*/ |
---|
| 64 | |
---|
| 65 | /**Function******************************************************************** |
---|
| 66 | |
---|
| 67 | Synopsis [Orders the MDD variables of a network.] |
---|
| 68 | |
---|
| 69 | Description [Orders the MDD variables of a network. The ordering is based |
---|
| 70 | solely on the topology of the network; the binary variables that make up the |
---|
| 71 | MDD variables are not interleaved. OutputOrderType can be either Ord_All_c |
---|
| 72 | or Ord_InputAndLatch_c. If it is Ord_All_c, then every node (and latch NS) |
---|
| 73 | in the network is assigned an MDD id. If it is Ord_InputAndLatch_c, then |
---|
| 74 | every primary input, pseudo input, latch, and latch NS is assigned an MDD |
---|
| 75 | id.<p> |
---|
| 76 | |
---|
| 77 | SuppliedOrderType can be any value of Ord_OrderType. If it is Ord_All_c or |
---|
| 78 | Ord_InputAndLatch_c, then suppliedNodeList must give an ordering of the |
---|
| 79 | network nodes (included in the set specified by suppliedOrderType). |
---|
| 80 | Otherwise, Ord_NetworkOrderNodes is called, with the same arguments as this |
---|
| 81 | function, to compute an ordering of the network nodes. In any case, the |
---|
| 82 | ordering of nodes is projected onto the set specified by generatedOrderType, |
---|
| 83 | and MDD ids are assigned (in order) to the nodes in the projection. The |
---|
| 84 | starting MDD id is the total number of variables currently in the MDD |
---|
| 85 | manager of the network. An MDD manager is created for the network if one |
---|
| 86 | doesn't already exist.<p> |
---|
| 87 | |
---|
| 88 | No checks are made to insure that suppliedNodeList contains what is implied |
---|
| 89 | by the value of suppliedOrderType. The MDD ids of nodes not specified by |
---|
| 90 | generatedOrderType are unaffected.<p> |
---|
| 91 | |
---|
| 92 | If nsAfterSupport is TRUE, then for a given latch, its next state variable |
---|
| 93 | is ordered just after the variables in the support of the latch's |
---|
| 94 | corresponding dataInput function. <p> |
---|
| 95 | |
---|
| 96 | If nsAfterSupport is FALSE, then for a given latch, its NS variable is |
---|
| 97 | ordered just after the corresponding present state variable. In this case, |
---|
| 98 | the ps variable and the ns variable are grouped together in the variable |
---|
| 99 | ordering, so that when reordering is performed they remain adjacent in the |
---|
| 100 | new variable ordering. Similarly, when an ordering is read from a file, NS |
---|
| 101 | variables immediately following corresponding PS variables are grouped |
---|
| 102 | together.<p>] |
---|
| 103 | |
---|
| 104 | SideEffects [Writes over the MDD id field of nodes.] |
---|
| 105 | |
---|
| 106 | SeeAlso [Ord_NetworkOrderNodes] |
---|
| 107 | |
---|
| 108 | ******************************************************************************/ |
---|
| 109 | void |
---|
| 110 | Ord_NetworkOrderVariables( |
---|
| 111 | Ntk_Network_t *network, |
---|
| 112 | Ord_RootMethod rootOrderMethod, |
---|
| 113 | Ord_NodeMethod nodeOrderMethod, |
---|
| 114 | boolean nsAfterSupport, |
---|
| 115 | Ord_OrderType generatedOrderType /* Ord_All_c or Ord_InputAndLatch_c */, |
---|
| 116 | Ord_OrderType suppliedOrderType /* no restrictions */, |
---|
| 117 | lsList suppliedNodeList /* list of nodes Ntk_Node_t* from ordering file */, |
---|
| 118 | int verbose) |
---|
| 119 | { |
---|
| 120 | lsList totalOrderList; /* list of nodes (Ntk_Node_t *) */ |
---|
| 121 | long initialTime = util_cpu_time(); |
---|
| 122 | |
---|
| 123 | /* |
---|
| 124 | * The condition where suppliedOrderType==InputAndLatch and |
---|
| 125 | * generatedOrderType==All is not currently allowed because we're not sure |
---|
| 126 | * if it's useful. |
---|
| 127 | */ |
---|
| 128 | assert(!((suppliedOrderType == Ord_InputAndLatch_c) |
---|
| 129 | && (generatedOrderType == Ord_All_c))); |
---|
| 130 | |
---|
| 131 | /* |
---|
| 132 | * Either get a total ordering of the network nodes from suppliedNodeList, |
---|
| 133 | * or compute it working from the network. |
---|
| 134 | */ |
---|
| 135 | if ((suppliedOrderType == Ord_All_c) |
---|
| 136 | || (suppliedOrderType == Ord_InputAndLatch_c)) { |
---|
| 137 | totalOrderList = lsCopy(suppliedNodeList, |
---|
| 138 | (lsGeneric (*) (lsGeneric)) NULL); |
---|
| 139 | } |
---|
| 140 | else { |
---|
| 141 | totalOrderList = Ord_NetworkOrderNodes(network, rootOrderMethod, |
---|
| 142 | nodeOrderMethod, nsAfterSupport, |
---|
| 143 | generatedOrderType, |
---|
| 144 | suppliedOrderType, |
---|
| 145 | suppliedNodeList, |
---|
| 146 | verbose); |
---|
| 147 | } |
---|
| 148 | |
---|
| 149 | |
---|
| 150 | OrdNetworkAssignMddIds(network, generatedOrderType, totalOrderList, nsAfterSupport); |
---|
| 151 | (void) lsDestroy(totalOrderList, (void (*) (lsGeneric)) NULL); |
---|
| 152 | |
---|
| 153 | /* |
---|
| 154 | * If nsAfterSupport is FALSE, this implies that NS comes right after PS. |
---|
| 155 | * |
---|
| 156 | */ |
---|
| 157 | if ( nsAfterSupport == FALSE ) { |
---|
| 158 | lsGen tmpGen; |
---|
| 159 | Ntk_Node_t *tmpLatch; |
---|
| 160 | |
---|
| 161 | /* |
---|
| 162 | * Iterate over each latch, and group the PS variable with the next |
---|
| 163 | * variable in the ordering, which is guaranteed to be the corresponding NS |
---|
| 164 | * variable. |
---|
| 165 | */ |
---|
| 166 | Ntk_NetworkForEachLatch(network, tmpGen, tmpLatch) { |
---|
| 167 | mdd_manager *mddMgr = Ntk_NetworkReadMddManager( network ); |
---|
| 168 | Ntk_Node_t *nsNode = Ntk_NodeReadShadow( tmpLatch ); |
---|
| 169 | int psMddId = Ntk_NodeReadMddId( tmpLatch ); |
---|
| 170 | int nsMddId = Ntk_NodeReadMddId( nsNode ); |
---|
| 171 | |
---|
| 172 | /* |
---|
| 173 | * Group size = 2 ( ps and ns ) |
---|
| 174 | */ |
---|
| 175 | if (nsMddId == (psMddId+1)) { |
---|
| 176 | MddGroupVariables(mddMgr, psMddId, 2); |
---|
| 177 | } |
---|
| 178 | /* Adnan's fix: See his mail to vis@ic on Oct 24, 1997 */ |
---|
| 179 | if (nsMddId == (psMddId-1)) { |
---|
| 180 | MddGroupVariables(mddMgr, nsMddId, 2); |
---|
| 181 | } |
---|
| 182 | } |
---|
| 183 | } |
---|
| 184 | |
---|
| 185 | if (verbose > 0) { |
---|
| 186 | long finalTime = util_cpu_time(); |
---|
| 187 | (void) fprintf(vis_stdout, "\nTotal ordering time = %2.1f\n", |
---|
| 188 | (finalTime-initialTime)/1000.0); |
---|
| 189 | } |
---|
| 190 | } |
---|
| 191 | |
---|
| 192 | |
---|
| 193 | /**Function******************************************************************** |
---|
| 194 | |
---|
| 195 | Synopsis [Orders the nodes of a network.] |
---|
| 196 | |
---|
| 197 | Description [Orders the nodes of a network. The ordering is based solely on |
---|
| 198 | the topology of the network, and is intended to be suitable for deriving an |
---|
| 199 | MDD variable ordering by extracting those nodes for which MDD variables are |
---|
| 200 | needed. GeneratedOrderType can be either Ord_All_c or |
---|
| 201 | Ord_InputAndLatch_c. If it is Ord_All_c, then every node (and latch NS) in |
---|
| 202 | the network is ordered. If it is Ord_InputAndLatch_c, then every primary |
---|
| 203 | input, pseudo input, latch, and latch NS is ordered. <p> |
---|
| 204 | |
---|
| 205 | SuppliedOrderType can be any of the following values: Ord_NextStateNode_c, |
---|
| 206 | Ord_Partial_c, or Ord_Unassigned_c. If it is Ord_Unassigned_c, then |
---|
| 207 | suppliedNodeList is ignored, and there is no effect. If it is *not* |
---|
| 208 | Ord_Unassigned_c, then suppliedNodeList must be a non-empty list of |
---|
| 209 | (pointers to) nodes. SuppliedNodeList can be used to specify the relative |
---|
| 210 | order of some or the nodes.<p> |
---|
| 211 | |
---|
| 212 | If suppliedOrderType is Ord_NextStateNode_c, then suppliedNodeList should |
---|
| 213 | contain a complete list of next state nodes; the transitive fanins of the |
---|
| 214 | latches are visited according to the order of the next state nodes in |
---|
| 215 | suppliedNodeList. If suppliedOrderType is Ord_Partial_c, then |
---|
| 216 | suppliedNodeList may contain an arbitrary subset of network nodes; in this |
---|
| 217 | case, an ordering is found disregarding suppliedNodeList, and then this |
---|
| 218 | ordering is merged into the suppliedNodeList. No checks are made to insure |
---|
| 219 | that suppliedNodeList contains what is implied by the value of |
---|
| 220 | suppliedOrderType.<p> |
---|
| 221 | |
---|
| 222 | If nsAfterSupport is TRUE, then for a given latch, its next state variable |
---|
| 223 | is ordered just after the latch's corresponding dataInput node. If |
---|
| 224 | nsAfterSupport is FALSE, then for a given latch, its next state variable is |
---|
| 225 | ordered just after the latch (i.e. its present state variable). (If the |
---|
| 226 | latch itself is not present yet in the nodeOrderList, then first adds latch |
---|
| 227 | to the end of the ordering.)] |
---|
| 228 | |
---|
| 229 | SideEffects [] |
---|
| 230 | |
---|
| 231 | SeeAlso [Ord_NetworkOrderVariables] |
---|
| 232 | |
---|
| 233 | ******************************************************************************/ |
---|
| 234 | lsList |
---|
| 235 | Ord_NetworkOrderNodes( |
---|
| 236 | Ntk_Network_t *network, |
---|
| 237 | Ord_RootMethod rootOrderMethod, |
---|
| 238 | Ord_NodeMethod nodeOrderMethod, |
---|
| 239 | boolean nsAfterSupport, |
---|
| 240 | Ord_OrderType generatedOrderType /* Ord_All_c or Ord_InputAndLatch_c */, |
---|
| 241 | Ord_OrderType suppliedOrderType /* Ord_NextStateNode_c, Ord_Partial_c, or |
---|
| 242 | Ord_Unassigned_c */, |
---|
| 243 | lsList suppliedNodeList /* list of nodes Ntk_Node_t* from ordering file */, |
---|
| 244 | int verbose) |
---|
| 245 | { |
---|
| 246 | lsList partialRootOrder; /* list of nodes (Ntk_Node_t *) */ |
---|
| 247 | lsList roots; /* list of nodes (Ntk_Node_t *) */ |
---|
| 248 | lsList nodeOrderList; /* list of nodes (Ntk_Node_t *) */ |
---|
| 249 | st_table *nodeToHandle; /* Ntk_Node_t* to lsHandle */ |
---|
| 250 | |
---|
| 251 | /* |
---|
| 252 | * Check the input arguments. |
---|
| 253 | */ |
---|
| 254 | assert( (generatedOrderType == Ord_All_c) |
---|
| 255 | || (generatedOrderType == Ord_InputAndLatch_c)); |
---|
| 256 | |
---|
| 257 | assert( (suppliedOrderType == Ord_NextStateNode_c) |
---|
| 258 | || (suppliedOrderType == Ord_Partial_c) |
---|
| 259 | || (suppliedOrderType == Ord_Unassigned_c)); |
---|
| 260 | |
---|
| 261 | |
---|
| 262 | /* |
---|
| 263 | * Compute an ordering on the roots. The nodes of the network are explored |
---|
| 264 | * in DFS order from the roots, in the root order computed. If |
---|
| 265 | * suppliedOrderType is Ord_NextStateNode_c, then suppliedNodeList contains |
---|
| 266 | * the next state nodes; this list serves as a seed to compute the root |
---|
| 267 | * ordering. |
---|
| 268 | */ |
---|
| 269 | partialRootOrder = (suppliedOrderType == Ord_NextStateNode_c) |
---|
| 270 | ? LatchNSListConvertToLatchDataInputList(suppliedNodeList) |
---|
| 271 | : (lsList) NULL; |
---|
| 272 | roots = Ord_NetworkOrderRoots(network, rootOrderMethod, |
---|
| 273 | partialRootOrder, verbose); |
---|
| 274 | if (suppliedOrderType == Ord_NextStateNode_c) { |
---|
| 275 | (void) lsDestroy(partialRootOrder, (void (*) (lsGeneric)) NULL); |
---|
| 276 | } |
---|
| 277 | if (verbose > 0) { |
---|
| 278 | (void) fprintf(vis_stdout, "\nOrder in which roots are visited:\n"); |
---|
| 279 | OrdNodeListWrite(vis_stdout, roots); |
---|
| 280 | } |
---|
| 281 | |
---|
| 282 | /* |
---|
| 283 | * Compute an order on all nodes in the transitive fanin of roots, including |
---|
| 284 | * the roots themselves. Pass in an empty nodeToHandle table. |
---|
| 285 | */ |
---|
| 286 | nodeToHandle = st_init_table(st_ptrcmp, st_ptrhash); |
---|
| 287 | nodeOrderList = OrdNetworkOrderTFIOfRoots(network, roots, nodeOrderMethod, |
---|
| 288 | nodeToHandle, verbose); |
---|
| 289 | (void) lsDestroy(roots, (void (*) (lsGeneric)) NULL); |
---|
| 290 | |
---|
| 291 | if (verbose > 0) { |
---|
| 292 | (void) fprintf(vis_stdout, "\nOrder of network nodes without NS:\n"); |
---|
| 293 | OrdNodeListWrite(vis_stdout, nodeOrderList); |
---|
| 294 | } |
---|
| 295 | |
---|
| 296 | /* |
---|
| 297 | * Add in the next state variables (represented by the shadow nodes of |
---|
| 298 | * latches). |
---|
| 299 | */ |
---|
| 300 | NetworkAddNSVarsToOrderList(network, nodeOrderList, nodeToHandle, nsAfterSupport); |
---|
| 301 | if (verbose > 2) { |
---|
| 302 | (void) fprintf(vis_stdout, "\nOrder of network nodes with NS:\n"); |
---|
| 303 | OrdNodeListWrite(vis_stdout, nodeOrderList); |
---|
| 304 | } |
---|
| 305 | |
---|
| 306 | |
---|
| 307 | /* |
---|
| 308 | * There may be some nodes that are not in the TFI of any root. Put such |
---|
| 309 | * nodes at the end of nodeOrderList (in no particular order). |
---|
| 310 | */ |
---|
| 311 | NetworkAddDanglingNodesToOrderList(network, nodeOrderList, nodeToHandle); |
---|
| 312 | st_free_table(nodeToHandle); |
---|
| 313 | |
---|
| 314 | /* |
---|
| 315 | * If the suppliedOrderType is Partial, then merge (left, arbitrarily) the |
---|
| 316 | * computed node order into the supplied node order and return the result. |
---|
| 317 | * Otherwise, just return the nodeOrderList computed. |
---|
| 318 | */ |
---|
| 319 | if (suppliedOrderType == Ord_Partial_c) { |
---|
| 320 | lsList suppliedNodeListCopy = lsCopy(suppliedNodeList, |
---|
| 321 | (lsGeneric (*) (lsGeneric)) NULL); |
---|
| 322 | |
---|
| 323 | Ord_ListMergeList(suppliedNodeListCopy, nodeOrderList, Ord_ListMergeLeft_c); |
---|
| 324 | (void) lsDestroy(nodeOrderList, (void (*) (lsGeneric)) NULL); |
---|
| 325 | return suppliedNodeListCopy; |
---|
| 326 | } |
---|
| 327 | else { |
---|
| 328 | return nodeOrderList; |
---|
| 329 | } |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | |
---|
| 333 | /**Function******************************************************************** |
---|
| 334 | |
---|
| 335 | Synopsis [Assigns an mddId to a node.] |
---|
| 336 | |
---|
| 337 | Description [Assigns an mddId to a node. If the node already has a valid |
---|
| 338 | mddId (i.e. it is not NTK_UNASSIGNED_MDD_ID), then nothing is done. |
---|
| 339 | Otherwise, the node is assigned an mddId, and this Id is created within the |
---|
| 340 | MDD manager of the network. (An MDD manager is created for the network if |
---|
| 341 | the network doesn't already have one.) ] |
---|
| 342 | |
---|
| 343 | SideEffects [] |
---|
| 344 | |
---|
| 345 | Comment [(Tom): this should be more intelligent, and get the id from the |
---|
| 346 | total ordering on all the network nodes, and then do insertion into variable |
---|
| 347 | ordering. Use ntk appl info to store total node order.] |
---|
| 348 | |
---|
| 349 | ******************************************************************************/ |
---|
| 350 | void |
---|
| 351 | Ord_NetworkAssignMddIdForNode( |
---|
| 352 | Ntk_Network_t *network, |
---|
| 353 | Ntk_Node_t *node) |
---|
| 354 | { |
---|
| 355 | if (Ntk_NodeReadMddId(node) != NTK_UNASSIGNED_MDD_ID) { |
---|
| 356 | return; |
---|
| 357 | } |
---|
| 358 | else { |
---|
| 359 | int mddId; |
---|
| 360 | mdd_manager *mddManager = Ntk_NetworkReadMddManager(network); |
---|
| 361 | array_t *mvarValues = array_alloc(int, 0); |
---|
| 362 | array_t *mvarNames = array_alloc(char *, 0); |
---|
| 363 | |
---|
| 364 | /* |
---|
| 365 | * If the network doesn't already have an MDD manager, then create one. In |
---|
| 366 | * any case, set mddId to be the number of variables currently existing in |
---|
| 367 | * the manager. |
---|
| 368 | */ |
---|
| 369 | if (mddManager == NIL(mdd_manager)) { |
---|
| 370 | mddManager = Ntk_NetworkInitializeMddManager(network); |
---|
| 371 | mddId = 0; |
---|
| 372 | } |
---|
| 373 | else { |
---|
| 374 | array_t *mvarArray = mdd_ret_mvar_list(mddManager); |
---|
| 375 | mddId = array_n(mvarArray); |
---|
| 376 | } |
---|
| 377 | |
---|
| 378 | Ntk_NodeSetMddId(node, mddId); |
---|
| 379 | |
---|
| 380 | array_insert_last(int, mvarValues, |
---|
| 381 | Var_VariableReadNumValues(Ntk_NodeReadVariable(node))); |
---|
| 382 | array_insert_last(char *, mvarNames, Ntk_NodeReadName(node)); |
---|
| 383 | |
---|
| 384 | /* |
---|
| 385 | * Create the variable in the MDD manager. The last argument being NIL |
---|
| 386 | * means that the variable will not be interleaved. |
---|
| 387 | */ |
---|
| 388 | mdd_create_variables(mddManager, mvarValues, mvarNames, NIL(array_t)); |
---|
| 389 | |
---|
| 390 | array_free(mvarValues); |
---|
| 391 | array_free(mvarNames); |
---|
| 392 | } |
---|
| 393 | } |
---|
| 394 | |
---|
| 395 | |
---|
| 396 | /**Function******************************************************************** |
---|
| 397 | |
---|
| 398 | Synopsis [Merges left list2 into list1, using the provided table for efficiency.] |
---|
| 399 | |
---|
| 400 | Description [Merges left list2 into list1, using the provided table for |
---|
| 401 | efficiency. dataToHandle1 is a hash table mapping each item in list1 to its |
---|
| 402 | handle in list1. <p> |
---|
| 403 | |
---|
| 404 | This function implements the merge described in Algorithm 1 by Fujii et al., |
---|
| 405 | "Interleaving Based Variable Ordering Methods for OBDDs", ICCAD 1993, p. 38. |
---|
| 406 | For each item in list2: if item is already present in list1, do nothing; |
---|
| 407 | else if item is the head of list2, then insert item at the head of list1; |
---|
| 408 | else, insert item into list1 immediately following the location in list1 of |
---|
| 409 | the item's predessor item in list2. This has the effect of locating the |
---|
| 410 | items in list2 as far to the left as possible in list1, while still |
---|
| 411 | preserving the partial order for those elements of list2 not initially |
---|
| 412 | appearing in list1 (a "merge left"). Examples: |
---|
| 413 | |
---|
| 414 | <pre> |
---|
| 415 | list1=abc, list2=dbe --> list1=dabec |
---|
| 416 | list1=abc, list2=deb --> list1=deabc. |
---|
| 417 | </pre> |
---|
| 418 | |
---|
| 419 | Note that this merging is not commutative. That is, Ord_ListMergeLeftList(l1,l2) |
---|
| 420 | may give a different ordering than Ord_ListMergeLeftList(l2,l1).] |
---|
| 421 | |
---|
| 422 | SideEffects [List1 is modified, and dataToHandle1 is modified to reflect the |
---|
| 423 | newly inserted items.] |
---|
| 424 | |
---|
| 425 | Comment [All references to "handle" in the code are references to |
---|
| 426 | handles in list1. We never reference or care about handles in list2. ] |
---|
| 427 | |
---|
| 428 | SeeAlso [Ord_ListMergeRightListUsingTable] |
---|
| 429 | |
---|
| 430 | ******************************************************************************/ |
---|
| 431 | void |
---|
| 432 | Ord_ListMergeLeftListUsingTable( |
---|
| 433 | lsList list1, |
---|
| 434 | lsList list2, |
---|
| 435 | st_table *dataToHandle1) |
---|
| 436 | { |
---|
| 437 | lsGen gen1; /* generator for list1 */ |
---|
| 438 | lsGen gen2; /* generator for list2 */ |
---|
| 439 | lsHandle handle; /* handle of an item in list1 */ |
---|
| 440 | lsGeneric data; |
---|
| 441 | lsGeneric prevData; |
---|
| 442 | |
---|
| 443 | /* |
---|
| 444 | * Walk through list2 forwards, keeping track of the previous item just visited. |
---|
| 445 | */ |
---|
| 446 | gen2 = lsStart(list2); |
---|
| 447 | prevData = NULL; |
---|
| 448 | while (lsNext(gen2, &data, LS_NH) == LS_OK) { |
---|
| 449 | |
---|
| 450 | if (!st_is_member(dataToHandle1, (char *) data)) { |
---|
| 451 | /* |
---|
| 452 | * Data is not present in list1, so we must insert it at the proper |
---|
| 453 | * location. |
---|
| 454 | */ |
---|
| 455 | if (prevData == NULL) { |
---|
| 456 | /* |
---|
| 457 | * Data is the head of list2, so insert it at the head of list1. |
---|
| 458 | */ |
---|
| 459 | (void) lsNewBegin(list1, data, &handle); |
---|
| 460 | } |
---|
| 461 | else { |
---|
| 462 | lsGeneric dummyData; |
---|
| 463 | lsHandle prevHandle; |
---|
| 464 | |
---|
| 465 | /* |
---|
| 466 | * Data is not the head of list1. Hence, insert it just to the right |
---|
| 467 | * of the location of prevData in list1 (by induction, prevData must |
---|
| 468 | * currently exist in list1). Do this by getting the handle of |
---|
| 469 | * prevData in list1, creating a generator initialized to just after |
---|
| 470 | * prevData, and then inserting data at this point. Note that |
---|
| 471 | * lsInAfter and lsInBefore are equivalent in this case, since we |
---|
| 472 | * immediately kill gen1. |
---|
| 473 | */ |
---|
| 474 | st_lookup(dataToHandle1, prevData, &prevHandle); |
---|
| 475 | gen1 = lsGenHandle(prevHandle, &dummyData, LS_AFTER); |
---|
| 476 | (void) lsInAfter(gen1, data, &handle); |
---|
| 477 | (void) lsFinish(gen1); |
---|
| 478 | } |
---|
| 479 | st_insert(dataToHandle1, data, handle); |
---|
| 480 | |
---|
| 481 | } /* else, data already present in list1, so do nothing */ |
---|
| 482 | |
---|
| 483 | prevData = data; |
---|
| 484 | |
---|
| 485 | } /* end while */ |
---|
| 486 | (void) lsFinish(gen2); |
---|
| 487 | } |
---|
| 488 | |
---|
| 489 | |
---|
| 490 | /**Function******************************************************************** |
---|
| 491 | |
---|
| 492 | Synopsis [Merges right list2 into list1, using the provided table for efficiency.] |
---|
| 493 | |
---|
| 494 | Description [Merges right list2 into list1, using the provided table for |
---|
| 495 | efficiency. This function is the same as Ord_ListMergeLeftListUsingTable, |
---|
| 496 | except that a "merge right" is done, rather than a "merge left". For each |
---|
| 497 | item in list2: if item is already present in list1, do nothing; else if item |
---|
| 498 | is the tail of list2, then insert item at the tail of list1; else, insert |
---|
| 499 | item into list1 immediately preceeding the location in list1 of the item's |
---|
| 500 | successor item in list2. This has the effect of locating the items in list2 |
---|
| 501 | as far to the right as possible in list1, while still preserving the partial |
---|
| 502 | order for those elements of list2 not initially appearing in list1 (a "merge |
---|
| 503 | right"). Examples: |
---|
| 504 | |
---|
| 505 | <pre> |
---|
| 506 | list1=abc, list2=dbe --> list1=adbce |
---|
| 507 | list1=abc, list2=deb --> list1=adebc. |
---|
| 508 | </pre> |
---|
| 509 | |
---|
| 510 | ] |
---|
| 511 | |
---|
| 512 | SideEffects [List1 is modified, and dataToHandle1 is modified to reflect the |
---|
| 513 | newly inserted items.] |
---|
| 514 | |
---|
| 515 | Comment [All references to "handle" in the code are references to |
---|
| 516 | handles in list1. We never reference or care about handles in list2. ] |
---|
| 517 | |
---|
| 518 | SeeAlso [Ord_ListMergeLeftListUsingTable] |
---|
| 519 | |
---|
| 520 | ******************************************************************************/ |
---|
| 521 | void |
---|
| 522 | Ord_ListMergeRightListUsingTable( |
---|
| 523 | lsList list1, |
---|
| 524 | lsList list2, |
---|
| 525 | st_table *dataToHandle1) |
---|
| 526 | { |
---|
| 527 | lsGen gen1; /* generator for list1 */ |
---|
| 528 | lsGen gen2; /* generator for list2 */ |
---|
| 529 | lsHandle handle; /* handle of an item in list1 */ |
---|
| 530 | lsGeneric data; |
---|
| 531 | lsGeneric succData; |
---|
| 532 | |
---|
| 533 | /* |
---|
| 534 | * Walk through list2 backwards, keeping track of the successor item just visited. |
---|
| 535 | */ |
---|
| 536 | gen2 = lsEnd(list2); |
---|
| 537 | succData = NULL; |
---|
| 538 | while (lsPrev(gen2, &data, LS_NH) == LS_OK) { |
---|
| 539 | |
---|
| 540 | if (!st_is_member(dataToHandle1, (char *) data)) { |
---|
| 541 | /* |
---|
| 542 | * Data is not present in list1, so we must insert it at the proper |
---|
| 543 | * location. |
---|
| 544 | */ |
---|
| 545 | if (succData == NULL) { |
---|
| 546 | /* |
---|
| 547 | * Data is the tail of list2, so insert it at the tail of list1. |
---|
| 548 | */ |
---|
| 549 | (void) lsNewEnd(list1, data, &handle); |
---|
| 550 | } |
---|
| 551 | else { |
---|
| 552 | lsGeneric dummyData; |
---|
| 553 | lsHandle succHandle; |
---|
| 554 | |
---|
| 555 | /* |
---|
| 556 | * Data is not the tail of list1. Hence, insert it just to the left |
---|
| 557 | * of the location of succData in list1 (by induction, succData must |
---|
| 558 | * currently exist in list1). Do this by getting the handle of |
---|
| 559 | * succData in list1, creating a generator initialized to just before |
---|
| 560 | * succData, and then inserting data at this point. Note that |
---|
| 561 | * lsInAfter and lsInBefore are equivalent in this case, since we are |
---|
| 562 | * immediately kill gen1. |
---|
| 563 | */ |
---|
| 564 | st_lookup(dataToHandle1, succData, &succHandle); |
---|
| 565 | gen1 = lsGenHandle(succHandle, &dummyData, LS_BEFORE); |
---|
| 566 | (void) lsInAfter(gen1, data, &handle); |
---|
| 567 | (void) lsFinish(gen1); |
---|
| 568 | } |
---|
| 569 | st_insert(dataToHandle1, data, handle); |
---|
| 570 | |
---|
| 571 | } /* else, data already present in list1, so do nothing */ |
---|
| 572 | |
---|
| 573 | succData = data; |
---|
| 574 | |
---|
| 575 | } /* end while */ |
---|
| 576 | (void) lsFinish(gen2); |
---|
| 577 | } |
---|
| 578 | |
---|
| 579 | |
---|
| 580 | /**Function******************************************************************** |
---|
| 581 | |
---|
| 582 | Synopsis [Merges list2 into list1, using the provided table for efficiency.] |
---|
| 583 | |
---|
| 584 | Description [Merges list2 into list1, using the provided table for |
---|
| 585 | efficiency. Calls Ord_ListMergeLeftListUsingTable or |
---|
| 586 | Ord_ListMergeRightListUsingTable depending on the value of method.] |
---|
| 587 | |
---|
| 588 | SideEffects [list1 is modified] |
---|
| 589 | |
---|
| 590 | SeeAlso [Ord_ListMergeLeftListUsingTable Ord_ListMergeRightListUsingTable] |
---|
| 591 | |
---|
| 592 | ******************************************************************************/ |
---|
| 593 | void |
---|
| 594 | Ord_ListMergeListUsingTable( |
---|
| 595 | lsList list1, |
---|
| 596 | lsList list2, |
---|
| 597 | st_table *dataToHandle1, |
---|
| 598 | Ord_ListMergeMethod method) |
---|
| 599 | { |
---|
| 600 | if (method == Ord_ListMergeLeft_c) { |
---|
| 601 | Ord_ListMergeLeftListUsingTable(list1, list2, dataToHandle1); |
---|
| 602 | } |
---|
| 603 | else if (method == Ord_ListMergeRight_c) { |
---|
| 604 | Ord_ListMergeRightListUsingTable(list1, list2, dataToHandle1); |
---|
| 605 | } |
---|
| 606 | else { |
---|
| 607 | fail("unrecognized method"); |
---|
| 608 | } |
---|
| 609 | } |
---|
| 610 | |
---|
| 611 | |
---|
| 612 | /**Function******************************************************************** |
---|
| 613 | |
---|
| 614 | Synopsis [Merges list2 into list1.] |
---|
| 615 | |
---|
| 616 | Description [Merges list2 into list1. Creates a hash table mapping the items |
---|
| 617 | of list1 to their handles in list1, and then calls Ord_ListMergeListUsingTable.] |
---|
| 618 | |
---|
| 619 | SideEffects [list1 is modified] |
---|
| 620 | |
---|
| 621 | SeeAlso [Ord_ListMergeListUsingTable] |
---|
| 622 | |
---|
| 623 | ******************************************************************************/ |
---|
| 624 | void |
---|
| 625 | Ord_ListMergeList( |
---|
| 626 | lsList list1, |
---|
| 627 | lsList list2, |
---|
| 628 | Ord_ListMergeMethod method) |
---|
| 629 | { |
---|
| 630 | lsGen gen1; /* generator for list1 */ |
---|
| 631 | lsHandle handle; /* handle of an item in list1 */ |
---|
| 632 | lsGeneric data; |
---|
| 633 | st_table *dataToHandle1 = st_init_table(st_ptrcmp, st_ptrhash); |
---|
| 634 | |
---|
| 635 | /* |
---|
| 636 | * Load a hash table mapping each item in list1 to its handle in list1. |
---|
| 637 | */ |
---|
| 638 | gen1 = lsStart(list1); |
---|
| 639 | while (lsNext(gen1, &data, &handle) == LS_OK) { |
---|
| 640 | st_insert(dataToHandle1, (char *) data, (char *) handle); |
---|
| 641 | } |
---|
| 642 | (void) lsFinish(gen1); |
---|
| 643 | |
---|
| 644 | Ord_ListMergeListUsingTable(list1, list2, dataToHandle1, method); |
---|
| 645 | |
---|
| 646 | st_free_table(dataToHandle1); |
---|
| 647 | } |
---|
| 648 | |
---|
| 649 | |
---|
| 650 | /**Function******************************************************************** |
---|
| 651 | |
---|
| 652 | Synopsis [Appends list2 into list1.] |
---|
| 653 | |
---|
| 654 | Description [Appends list2 into list1. List1 is modified; list2 is not |
---|
| 655 | changed.] |
---|
| 656 | |
---|
| 657 | SideEffects [list1 is modified] |
---|
| 658 | |
---|
| 659 | ******************************************************************************/ |
---|
| 660 | void |
---|
| 661 | Ord_ListAppendList( |
---|
| 662 | lsList list1, |
---|
| 663 | lsList list2) |
---|
| 664 | { |
---|
| 665 | lsGen gen; |
---|
| 666 | lsHandle handle; /* unused */ |
---|
| 667 | lsGeneric data; |
---|
| 668 | |
---|
| 669 | /* |
---|
| 670 | * Walk through list2 forwards, inserting each element to the end of list1. |
---|
| 671 | */ |
---|
| 672 | gen = lsStart(list2); |
---|
| 673 | while (lsNext(gen, &data, LS_NH) == LS_OK) { |
---|
| 674 | (void) lsNewEnd(list1, data, &handle); |
---|
| 675 | } |
---|
| 676 | (void) lsFinish(gen); |
---|
| 677 | } |
---|
| 678 | |
---|
| 679 | |
---|
| 680 | /*---------------------------------------------------------------------------*/ |
---|
| 681 | /* Definition of internal functions */ |
---|
| 682 | /*---------------------------------------------------------------------------*/ |
---|
| 683 | |
---|
| 684 | /**Function******************************************************************** |
---|
| 685 | |
---|
| 686 | Synopsis [Compares the depth of two nodes in an lsList.] |
---|
| 687 | |
---|
| 688 | Description [Compares the depth of two nodes in an lsList. Greater depth |
---|
| 689 | node should appear before a lower depth node.] |
---|
| 690 | |
---|
| 691 | SideEffects [] |
---|
| 692 | |
---|
| 693 | ******************************************************************************/ |
---|
| 694 | int |
---|
| 695 | OrdNodesFromListCompareDepth( |
---|
| 696 | lsGeneric node1, |
---|
| 697 | lsGeneric node2) |
---|
| 698 | { |
---|
| 699 | return NodesCompareDepth((Ntk_Node_t *) node1, (Ntk_Node_t *) node2); |
---|
| 700 | } |
---|
| 701 | |
---|
| 702 | |
---|
| 703 | /**Function******************************************************************** |
---|
| 704 | |
---|
| 705 | Synopsis [Compares the depth of two nodes in an array_t.] |
---|
| 706 | |
---|
| 707 | Description [Compares the depth of two nodes in an array_t. Greater depth |
---|
| 708 | node should appear before a lower depth node.] |
---|
| 709 | |
---|
| 710 | SideEffects [] |
---|
| 711 | |
---|
| 712 | ******************************************************************************/ |
---|
| 713 | int |
---|
| 714 | OrdNodesFromArrayCompareDepth( |
---|
| 715 | const void * node1, |
---|
| 716 | const void * node2) |
---|
| 717 | { |
---|
| 718 | return NodesCompareDepth(*(Ntk_Node_t **) node1, *(Ntk_Node_t **) node2); |
---|
| 719 | } |
---|
| 720 | |
---|
| 721 | |
---|
| 722 | /**Function******************************************************************** |
---|
| 723 | |
---|
| 724 | Synopsis [Computes the depth of each node in the TFI of roots.] |
---|
| 725 | |
---|
| 726 | Description [Computes the depth of each node in the transitive fanin of the |
---|
| 727 | list of roots. The depth of a node is defined inductively: latches, and |
---|
| 728 | nodes with no inputs, have depth 0. Otherwise, the depth of a node is 1 more |
---|
| 729 | than the maximum depth over the node's fanins. Intuitively, the depth of a |
---|
| 730 | node is the length of the longest (backward) path from the node to a latch, |
---|
| 731 | primary input, pseudo input, or constant.] |
---|
| 732 | |
---|
| 733 | SideEffects [Uses undef field of Ntk_Node_t.] |
---|
| 734 | |
---|
| 735 | SeeAlso [Ord_NetworkOrderVariables] |
---|
| 736 | |
---|
| 737 | ******************************************************************************/ |
---|
| 738 | void |
---|
| 739 | OrdNetworkComputeNodeDepths( |
---|
| 740 | Ntk_Network_t * network, |
---|
| 741 | lsList roots /* list of Ntk_Node_t */) |
---|
| 742 | { |
---|
| 743 | lsGen gen; |
---|
| 744 | Ntk_Node_t *node; |
---|
| 745 | Ntk_Node_t *root; |
---|
| 746 | |
---|
| 747 | /* |
---|
| 748 | * Initialize the depth of each node to unassigned. |
---|
| 749 | */ |
---|
| 750 | Ntk_NetworkForEachNode(network, gen, node) { |
---|
| 751 | NodeSetDepth(node, ORDUNASSIGNED_DEPTH); |
---|
| 752 | } |
---|
| 753 | |
---|
| 754 | /* |
---|
| 755 | * Start the recursive computation from each root. |
---|
| 756 | */ |
---|
| 757 | lsForEachItem(roots, gen, root) { |
---|
| 758 | (void) NodeComputeDepth(root); |
---|
| 759 | } |
---|
| 760 | } |
---|
| 761 | |
---|
| 762 | |
---|
| 763 | /**Function******************************************************************** |
---|
| 764 | |
---|
| 765 | Synopsis [Prints the names of a list of nodes, one per line.] |
---|
| 766 | |
---|
| 767 | SideEffects [] |
---|
| 768 | |
---|
| 769 | ******************************************************************************/ |
---|
| 770 | void |
---|
| 771 | OrdNodeListWrite( |
---|
| 772 | FILE *fp, |
---|
| 773 | lsList nodeList) |
---|
| 774 | { |
---|
| 775 | lsGen gen; |
---|
| 776 | Ntk_Node_t *node; |
---|
| 777 | |
---|
| 778 | lsForEachItem(nodeList, gen, node) { |
---|
| 779 | (void) fprintf(fp, "%s\n", Ntk_NodeReadName(node)); |
---|
| 780 | } |
---|
| 781 | } |
---|
| 782 | |
---|
| 783 | |
---|
| 784 | /**Function******************************************************************** |
---|
| 785 | |
---|
| 786 | Synopsis [Reads the depth of a node.] |
---|
| 787 | |
---|
| 788 | SideEffects [] |
---|
| 789 | |
---|
| 790 | Comment [The depth is not stored in a hash table of orderingState, because, |
---|
| 791 | for OrdNodesFromArrayCompareDepth, we need to be able to access the depth of |
---|
| 792 | a node given *just* the node.] |
---|
| 793 | |
---|
| 794 | SeeAlso [NodeSetDepth OrdNodesFromArrayCompareDepth |
---|
| 795 | OrdNodesFromListCompareDepth] |
---|
| 796 | |
---|
| 797 | ******************************************************************************/ |
---|
| 798 | long |
---|
| 799 | OrdNodeReadDepth( |
---|
| 800 | Ntk_Node_t * node) |
---|
| 801 | { |
---|
| 802 | return ((long) Ntk_NodeReadUndef(node)); |
---|
| 803 | } |
---|
| 804 | |
---|
| 805 | |
---|
| 806 | /**Function******************************************************************** |
---|
| 807 | |
---|
| 808 | Synopsis [Assigns consecutive MDD ids to nodes in orderList.] |
---|
| 809 | |
---|
| 810 | Description [Assigns consecutive MDD ids to nodes in orderList. Ids are |
---|
| 811 | assigned starting from the number of variables in the MDD manager of |
---|
| 812 | network. (An MDD manager is created for the network if the network doesn't |
---|
| 813 | already have one.) OrderType can be Ord_All_c or Ord_InputAndLatch_c. If |
---|
| 814 | orderType is Ord_All_c, then all nodes in orderList are assigned an id. If |
---|
| 815 | orderType is Ord_InputAndLatch_c only primary inputs, pseudo input, latches, |
---|
| 816 | and latch NSs are assigned ids. Presently, nsAfterSupport is unused.<p>] |
---|
| 817 | |
---|
| 818 | SideEffects [] |
---|
| 819 | |
---|
| 820 | SeeAlso [OrdNetworkOrderTFIOfRoots Ntk_NetworkInitializeMddManager] |
---|
| 821 | |
---|
| 822 | ******************************************************************************/ |
---|
| 823 | void |
---|
| 824 | OrdNetworkAssignMddIds( |
---|
| 825 | Ntk_Network_t * network, |
---|
| 826 | Ord_OrderType orderType, |
---|
| 827 | lsList orderList, |
---|
| 828 | boolean nsAfterSupport) |
---|
| 829 | { |
---|
| 830 | lsGen gen; |
---|
| 831 | Ntk_Node_t *node; |
---|
| 832 | int mddId; |
---|
| 833 | mdd_manager *mddManager = Ntk_NetworkReadMddManager(network); |
---|
| 834 | array_t *mvarValues = array_alloc(int, lsLength(orderList)); |
---|
| 835 | array_t *mvarNames = array_alloc(char *, lsLength(orderList)); |
---|
| 836 | |
---|
| 837 | assert((orderType == Ord_All_c) || (orderType == Ord_InputAndLatch_c)); |
---|
| 838 | |
---|
| 839 | /* |
---|
| 840 | * If the network doesn't already have an MDD manager, then create one. In |
---|
| 841 | * any case, set mddId to be the number of variables currently existing in |
---|
| 842 | * the manager. |
---|
| 843 | */ |
---|
| 844 | if (mddManager == NIL(mdd_manager)) { |
---|
| 845 | mddManager = Ntk_NetworkInitializeMddManager(network); |
---|
| 846 | mddId = 0; |
---|
| 847 | } |
---|
| 848 | else { |
---|
| 849 | array_t *mvarArray = mdd_ret_mvar_list(mddManager); |
---|
| 850 | mddId = array_n(mvarArray); |
---|
| 851 | } |
---|
| 852 | |
---|
| 853 | lsForEachItem(orderList, gen, node) { |
---|
| 854 | /* |
---|
| 855 | * A node gets an MDD id if node is a combinational input, next state |
---|
| 856 | * node, or orderType is Ord_All_c. |
---|
| 857 | */ |
---|
| 858 | if (Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsNextStateNode(node) |
---|
| 859 | || (orderType == Ord_All_c) ) { |
---|
| 860 | |
---|
| 861 | Ntk_NodeSetMddId(node, mddId); |
---|
| 862 | mddId++; |
---|
| 863 | |
---|
| 864 | array_insert_last(int, mvarValues, |
---|
| 865 | Var_VariableReadNumValues(Ntk_NodeReadVariable(node))); |
---|
| 866 | array_insert_last(char *, mvarNames, Ntk_NodeReadName(node)); |
---|
| 867 | } |
---|
| 868 | } |
---|
| 869 | |
---|
| 870 | /* |
---|
| 871 | * Create the variables in the MDD manager. The last argument being NIL |
---|
| 872 | * means that the variables will not be interleaved. |
---|
| 873 | */ |
---|
| 874 | mdd_create_variables(mddManager, mvarValues, mvarNames, NIL(array_t)); |
---|
| 875 | |
---|
| 876 | array_free(mvarValues); |
---|
| 877 | array_free(mvarNames); |
---|
| 878 | } |
---|
| 879 | |
---|
| 880 | |
---|
| 881 | /*---------------------------------------------------------------------------*/ |
---|
| 882 | /* Definition of static functions */ |
---|
| 883 | /*---------------------------------------------------------------------------*/ |
---|
| 884 | |
---|
| 885 | /**Function******************************************************************** |
---|
| 886 | |
---|
| 887 | Synopsis [Compares depths of node1 and node2 for sorting; greater depth |
---|
| 888 | node should appear before a lower depth node. Ties are broken based on the |
---|
| 889 | node names; it's an error if the two nodes have the same name.] |
---|
| 890 | |
---|
| 891 | SideEffects [] |
---|
| 892 | |
---|
| 893 | ******************************************************************************/ |
---|
| 894 | static int |
---|
| 895 | NodesCompareDepth( |
---|
| 896 | Ntk_Node_t *node1, |
---|
| 897 | Ntk_Node_t *node2) |
---|
| 898 | { |
---|
| 899 | long depth1 = OrdNodeReadDepth(node1); |
---|
| 900 | long depth2 = OrdNodeReadDepth(node2); |
---|
| 901 | |
---|
| 902 | if (depth1 > depth2) { |
---|
| 903 | return -1; |
---|
| 904 | } |
---|
| 905 | else if (depth1 < depth2) { |
---|
| 906 | return 1; |
---|
| 907 | } |
---|
| 908 | else { |
---|
| 909 | char *name1 = Ntk_NodeReadName(node1); |
---|
| 910 | char *name2 = Ntk_NodeReadName(node2); |
---|
| 911 | |
---|
| 912 | /* |
---|
| 913 | * As a tiebreaker, sort based on name, so that the sorted result is not |
---|
| 914 | * sensitive to the order in which the nodes are passed to the compare |
---|
| 915 | * function. When sorting based on name, the order doesn't really matter, |
---|
| 916 | * but right now it's done so that "foo<i>" will come before "foo<j>" in |
---|
| 917 | * the ordering, where i < j. This is just a little heuristic to put lower |
---|
| 918 | * order bits first. */ |
---|
| 919 | if (strcmp(name1, name2) < 0) { |
---|
| 920 | return -1; |
---|
| 921 | } |
---|
| 922 | else if (strcmp(name1, name2) > 0) { |
---|
| 923 | return 1; |
---|
| 924 | } |
---|
| 925 | else { |
---|
| 926 | return 0; |
---|
| 927 | } |
---|
| 928 | } |
---|
| 929 | } |
---|
| 930 | |
---|
| 931 | |
---|
| 932 | /**Function******************************************************************** |
---|
| 933 | |
---|
| 934 | Synopsis [Computes the depth of a node.] |
---|
| 935 | |
---|
| 936 | SideEffects [] |
---|
| 937 | |
---|
| 938 | SeeAlso [OrdNetworkComputeNodeDepths] |
---|
| 939 | |
---|
| 940 | ******************************************************************************/ |
---|
| 941 | static long |
---|
| 942 | NodeComputeDepth( |
---|
| 943 | Ntk_Node_t * node) |
---|
| 944 | { |
---|
| 945 | long depth = OrdNodeReadDepth(node); |
---|
| 946 | |
---|
| 947 | /* |
---|
| 948 | * If the node's depth has already been computed (i.e. it's not unassigned), |
---|
| 949 | * then just return it below. If it's unassigned, then recursively compute |
---|
| 950 | * it. |
---|
| 951 | */ |
---|
| 952 | if (depth == ORDUNASSIGNED_DEPTH) { |
---|
| 953 | |
---|
| 954 | if (Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node)) { |
---|
| 955 | /* |
---|
| 956 | * Latches, and nodes with no fanins, get depth 0. This is the terminal |
---|
| 957 | * case of recursion. |
---|
| 958 | */ |
---|
| 959 | depth = 0; |
---|
| 960 | } |
---|
| 961 | else { |
---|
| 962 | int i; |
---|
| 963 | Ntk_Node_t *fanin; |
---|
| 964 | /* |
---|
| 965 | * Compute the depth of each fanin node in the support of node, and |
---|
| 966 | * maintain the maximum. We start depth at 0 for max calculation. |
---|
| 967 | */ |
---|
| 968 | depth = 0; |
---|
| 969 | Ntk_NodeForEachFanin(node, i, fanin) { |
---|
| 970 | long faninDepth = NodeComputeDepth(fanin); |
---|
| 971 | |
---|
| 972 | depth = (depth > faninDepth) ? depth : faninDepth; |
---|
| 973 | } |
---|
| 974 | |
---|
| 975 | /* |
---|
| 976 | * The depth of node is one more than the max depths of its fanins. |
---|
| 977 | */ |
---|
| 978 | depth++; |
---|
| 979 | } |
---|
| 980 | |
---|
| 981 | /* |
---|
| 982 | * Store the depth. |
---|
| 983 | */ |
---|
| 984 | NodeSetDepth(node, depth); |
---|
| 985 | } |
---|
| 986 | |
---|
| 987 | return depth; |
---|
| 988 | } |
---|
| 989 | |
---|
| 990 | |
---|
| 991 | /**Function******************************************************************** |
---|
| 992 | |
---|
| 993 | Synopsis [Adds to nodeOrderList all network nodes not currently in the list.] |
---|
| 994 | |
---|
| 995 | Description [Adds to the end of nodeOrderList all network nodes that are not |
---|
| 996 | yet present in nodeOrderList. This is used to pick up those (dangling) |
---|
| 997 | nodes that weren't in the transitive fanins of the roots in the call to |
---|
| 998 | OrdNetworkOrderTFIOfRoots. nodeToHandle is a hash table mapping each node in |
---|
| 999 | nodeOrderList to its handle in the list; dangling nodes are inserted into |
---|
| 1000 | this table.] |
---|
| 1001 | |
---|
| 1002 | SideEffects [nodeOrderList and nodeToHandle will be modified if dangling |
---|
| 1003 | nodes exist.] |
---|
| 1004 | |
---|
| 1005 | SeeAlso [OrdNetworkOrderTFIOfRoots] |
---|
| 1006 | |
---|
| 1007 | ******************************************************************************/ |
---|
| 1008 | static void |
---|
| 1009 | NetworkAddDanglingNodesToOrderList( |
---|
| 1010 | Ntk_Network_t * network, |
---|
| 1011 | lsList nodeOrderList /* of Ntk_Node_t* */, |
---|
| 1012 | st_table *nodeToHandle /* Ntk_Node_t* to lsHandle */) |
---|
| 1013 | { |
---|
| 1014 | lsGen gen; |
---|
| 1015 | Ntk_Node_t *node; |
---|
| 1016 | |
---|
| 1017 | /* |
---|
| 1018 | * For each network node, if it's not in nodeOrderList, then add it to the |
---|
| 1019 | * end of the list. |
---|
| 1020 | * (NOTE: may be sensitive to ordering in memory.) |
---|
| 1021 | */ |
---|
| 1022 | Ntk_NetworkForEachNode(network, gen, node) { |
---|
| 1023 | if (!st_is_member(nodeToHandle, (char *) node)) { |
---|
| 1024 | lsHandle handle; |
---|
| 1025 | |
---|
| 1026 | (void) lsNewEnd(nodeOrderList, (lsGeneric) node, &handle); |
---|
| 1027 | st_insert(nodeToHandle, (char *) node, (char *) handle); |
---|
| 1028 | } |
---|
| 1029 | } |
---|
| 1030 | } |
---|
| 1031 | |
---|
| 1032 | |
---|
| 1033 | /**Function******************************************************************** |
---|
| 1034 | |
---|
| 1035 | Synopsis [Adds to nodeOrderList all next state variables.] |
---|
| 1036 | |
---|
| 1037 | Description [Adds to nodeOrderList all next state variables. If |
---|
| 1038 | nsAfterSupport is TRUE, then for a given latch, its NS variable is added in |
---|
| 1039 | nodeOrderList just after the latch's corresponding dataInput node. If |
---|
| 1040 | nsAfterSupport is FALSE, then for a given latch, its NS variable is added in |
---|
| 1041 | nodeOrderList just after the latch (i.e. its present state variable). (If the |
---|
| 1042 | latch itself is not present yet in the nodeOrderList, then first adds latch |
---|
| 1043 | to the end of the ordering.)<p> |
---|
| 1044 | |
---|
| 1045 | nodeToHandle is a hash table mapping each node in nodeOrderList to its |
---|
| 1046 | handle in the list; next state nodes are inserted into this table.] |
---|
| 1047 | |
---|
| 1048 | SideEffects [nodeOrderList and nodeToHandle will be modified if latches |
---|
| 1049 | exist.] |
---|
| 1050 | |
---|
| 1051 | SeeAlso [OrdNetworkOrderTFIOfRoots] |
---|
| 1052 | |
---|
| 1053 | ******************************************************************************/ |
---|
| 1054 | static void |
---|
| 1055 | NetworkAddNSVarsToOrderList( |
---|
| 1056 | Ntk_Network_t * network, |
---|
| 1057 | lsList nodeOrderList /* of Ntk_Node_t */, |
---|
| 1058 | st_table *nodeToHandle /* Ntk_Node_t* to lsHandle */, |
---|
| 1059 | boolean nsAfterSupport) |
---|
| 1060 | { |
---|
| 1061 | lsGen gen1; |
---|
| 1062 | Ntk_Node_t *latch; |
---|
| 1063 | |
---|
| 1064 | /* |
---|
| 1065 | * For each latch, add the latch's corresponding NS node to the ordering. |
---|
| 1066 | * (NOTE: may be sensitive to ordering in memory.) |
---|
| 1067 | */ |
---|
| 1068 | Ntk_NetworkForEachLatch(network, gen1, latch) { |
---|
| 1069 | lsHandle handle; |
---|
| 1070 | lsGen gen2; |
---|
| 1071 | lsGeneric dummyData; |
---|
| 1072 | Ntk_Node_t *latchNS = Ntk_NodeReadShadow(latch); |
---|
| 1073 | |
---|
| 1074 | if (nsAfterSupport) { |
---|
| 1075 | /* Add just after the latch's dataInput. */ |
---|
| 1076 | lsHandle dataInputHandle; |
---|
| 1077 | Ntk_Node_t *dataInput = Ntk_LatchReadDataInput(latch); |
---|
| 1078 | int status UNUSED = st_lookup(nodeToHandle, dataInput, |
---|
| 1079 | &dataInputHandle); |
---|
| 1080 | |
---|
| 1081 | assert(status); |
---|
| 1082 | gen2 = lsGenHandle(dataInputHandle, &dummyData, LS_AFTER); |
---|
| 1083 | } |
---|
| 1084 | else { |
---|
| 1085 | /* Add just after the latch. */ |
---|
| 1086 | lsHandle latchHandle; |
---|
| 1087 | int status = st_lookup(nodeToHandle, latch, &latchHandle); |
---|
| 1088 | |
---|
| 1089 | if (!status) { |
---|
| 1090 | /* |
---|
| 1091 | * Latch itself is not yet in the ordering. This can happen if the |
---|
| 1092 | * latch is not in the TFI of any other latch. So add the latch first |
---|
| 1093 | * (at the end of the ordering). |
---|
| 1094 | */ |
---|
| 1095 | (void) lsNewEnd(nodeOrderList, (lsGeneric) latch, &latchHandle); |
---|
| 1096 | st_insert(nodeToHandle, (char *) latch, (char *) latchHandle); |
---|
| 1097 | } |
---|
| 1098 | |
---|
| 1099 | gen2 = lsGenHandle(latchHandle, &dummyData, LS_AFTER); |
---|
| 1100 | } |
---|
| 1101 | |
---|
| 1102 | /* Actually add to list here. */ |
---|
| 1103 | (void) lsInAfter(gen2, (lsGeneric) latchNS, &handle); |
---|
| 1104 | st_insert(nodeToHandle, (char *) latchNS, (char *) handle); |
---|
| 1105 | (void) lsFinish(gen2); |
---|
| 1106 | |
---|
| 1107 | } |
---|
| 1108 | } |
---|
| 1109 | |
---|
| 1110 | |
---|
| 1111 | /**Function******************************************************************** |
---|
| 1112 | |
---|
| 1113 | Synopsis [Converts a list of latch next state nodes to the corresponding |
---|
| 1114 | list of latch data input nodes.] |
---|
| 1115 | |
---|
| 1116 | SideEffects [] |
---|
| 1117 | |
---|
| 1118 | ******************************************************************************/ |
---|
| 1119 | static lsList |
---|
| 1120 | LatchNSListConvertToLatchDataInputList( |
---|
| 1121 | lsList latchNSList) |
---|
| 1122 | { |
---|
| 1123 | lsGen gen; |
---|
| 1124 | Ntk_Node_t *node; |
---|
| 1125 | Ntk_Node_t *latch; |
---|
| 1126 | lsList latchDataInputList = lsCreate(); |
---|
| 1127 | |
---|
| 1128 | lsForEachItem(latchNSList, gen, node) { |
---|
| 1129 | assert(Ntk_NodeTestIsNextStateNode(node)); |
---|
| 1130 | latch = Ntk_ShadowReadOrigin(node); |
---|
| 1131 | (void) lsNewEnd(latchDataInputList, (lsGeneric) |
---|
| 1132 | Ntk_LatchReadDataInput(latch), LS_NH); |
---|
| 1133 | } |
---|
| 1134 | |
---|
| 1135 | return latchDataInputList; |
---|
| 1136 | } |
---|
| 1137 | |
---|
| 1138 | |
---|
| 1139 | /**Function******************************************************************** |
---|
| 1140 | |
---|
| 1141 | Synopsis [Sets the depth of a node.] |
---|
| 1142 | |
---|
| 1143 | SideEffects [] |
---|
| 1144 | |
---|
| 1145 | SeeAlso [OrdNodeReadDepth] |
---|
| 1146 | |
---|
| 1147 | ******************************************************************************/ |
---|
| 1148 | static void |
---|
| 1149 | NodeSetDepth( |
---|
| 1150 | Ntk_Node_t * node, |
---|
| 1151 | long depth) |
---|
| 1152 | { |
---|
| 1153 | Ntk_NodeSetUndef(node, (void *) depth); |
---|
| 1154 | } |
---|
| 1155 | |
---|
| 1156 | /**Function******************************************************************** |
---|
| 1157 | |
---|
| 1158 | Synopsis [Group all bdd vars corresponding to mdd vars initMddId to |
---|
| 1159 | initMddId + (blockSize-1) in a block which will not be split in reordering.] |
---|
| 1160 | |
---|
| 1161 | Description [Group all bdd vars corresponding to mdd vars initMddId to |
---|
| 1162 | initMddId + blockSize in a block which will not be reordered internally. |
---|
| 1163 | Ths bdd's corresponding to these mdd's should be contiguous; if not the |
---|
| 1164 | function will fail.] |
---|
| 1165 | |
---|
| 1166 | SideEffects [] |
---|
| 1167 | |
---|
| 1168 | ******************************************************************************/ |
---|
| 1169 | |
---|
| 1170 | static void |
---|
| 1171 | MddGroupVariables( |
---|
| 1172 | mdd_manager *mddMgr, |
---|
| 1173 | int initMddId, |
---|
| 1174 | int blockSize ) |
---|
| 1175 | { |
---|
| 1176 | int i, j; |
---|
| 1177 | int length; |
---|
| 1178 | int aIndex; |
---|
| 1179 | int startingBddIndex; |
---|
| 1180 | int sanityCheck; |
---|
| 1181 | mvar_type initMv, anMv; |
---|
| 1182 | bvar_type initBvar, aBvar; |
---|
| 1183 | array_t *mvar_list, *bvar_list; |
---|
| 1184 | bdd_t *bdd; |
---|
| 1185 | |
---|
| 1186 | mvar_list = mdd_ret_mvar_list(mddMgr); |
---|
| 1187 | bvar_list = mdd_ret_bvar_list(mddMgr); |
---|
| 1188 | |
---|
| 1189 | /* |
---|
| 1190 | * mvar for initMddId |
---|
| 1191 | */ |
---|
| 1192 | initMv = array_fetch(mvar_type, mvar_list, initMddId); |
---|
| 1193 | |
---|
| 1194 | /* |
---|
| 1195 | * bvar for first bdd for initMddId |
---|
| 1196 | */ |
---|
| 1197 | initBvar = mdd_ret_bvar(&initMv, 0, bvar_list); |
---|
| 1198 | |
---|
| 1199 | /* |
---|
| 1200 | * number of bdd variables to group |
---|
| 1201 | */ |
---|
| 1202 | length = 0; |
---|
| 1203 | |
---|
| 1204 | /* |
---|
| 1205 | * startingBddIndex is the level of the first bdd variable |
---|
| 1206 | */ |
---|
| 1207 | startingBddIndex = bdd_top_var_level( mddMgr, initBvar.node ); |
---|
| 1208 | sanityCheck = startingBddIndex; |
---|
| 1209 | |
---|
| 1210 | /* |
---|
| 1211 | * in this loop we are simply ensuring that the bdd variables |
---|
| 1212 | * corresponding to the mdd vars are infact contiguous. If this |
---|
| 1213 | * is not the case we fail. length is the total number of bdd variables |
---|
| 1214 | * to be grouped. |
---|
| 1215 | */ |
---|
| 1216 | for( i = 0; i < blockSize; i++) { |
---|
| 1217 | anMv = array_fetch(mvar_type, mvar_list, ( initMddId + i ) ); |
---|
| 1218 | for ( j = 0 ; j < anMv.encode_length; j++ ) { |
---|
| 1219 | |
---|
| 1220 | aBvar = mdd_ret_bvar( & anMv, j, bvar_list ); |
---|
| 1221 | aIndex = bdd_top_var_level( mddMgr, aBvar.node ); |
---|
| 1222 | |
---|
| 1223 | if ( sanityCheck != aIndex ) { |
---|
| 1224 | /* bdd vars are not contiguous!! */ |
---|
| 1225 | fprintf(vis_stderr, "Badly formed block - bdd vars for %s (mvar_id = %d) are not contiguous!!\n", |
---|
| 1226 | anMv.name, anMv.mvar_id ); |
---|
| 1227 | fail("Wont go on\n"); |
---|
| 1228 | } |
---|
| 1229 | else { |
---|
| 1230 | /* number of variables to group increased by one */ |
---|
| 1231 | sanityCheck++; |
---|
| 1232 | length++; |
---|
| 1233 | } |
---|
| 1234 | } |
---|
| 1235 | } |
---|
| 1236 | |
---|
| 1237 | bdd = bdd_var_with_index(mddMgr, startingBddIndex); |
---|
| 1238 | (void) bdd_new_var_block(bdd, length); |
---|
| 1239 | bdd_free(bdd); |
---|
| 1240 | } |
---|
| 1241 | |
---|
| 1242 | |
---|