source: vis_dev/vis-2.3/src/ord/ordMain.c @ 93

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

vis2.3

File size: 41.5 KB
Line 
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
34static 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
50static int NodesCompareDepth(Ntk_Node_t *node1, Ntk_Node_t *node2);
51static long NodeComputeDepth(Ntk_Node_t * node);
52static void NetworkAddDanglingNodesToOrderList(Ntk_Network_t * network, lsList nodeOrderList, st_table *nodeToHandle);
53static void NetworkAddNSVarsToOrderList(Ntk_Network_t * network, lsList nodeOrderList, st_table *nodeToHandle, boolean nsAfterSupport);
54static lsList LatchNSListConvertToLatchDataInputList(lsList latchNSList);
55static void NodeSetDepth(Ntk_Node_t * node, long depth);
56static 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******************************************************************************/
109void
110Ord_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******************************************************************************/
234lsList
235Ord_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******************************************************************************/
350void
351Ord_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******************************************************************************/
431void
432Ord_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******************************************************************************/
521void
522Ord_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******************************************************************************/
593void
594Ord_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******************************************************************************/
624void
625Ord_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******************************************************************************/
660void
661Ord_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******************************************************************************/
694int
695OrdNodesFromListCompareDepth(
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******************************************************************************/
713int
714OrdNodesFromArrayCompareDepth(
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******************************************************************************/
738void
739OrdNetworkComputeNodeDepths(
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******************************************************************************/
770void
771OrdNodeListWrite(
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******************************************************************************/
798long
799OrdNodeReadDepth(
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******************************************************************************/
823void
824OrdNetworkAssignMddIds(
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******************************************************************************/
894static int
895NodesCompareDepth(
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******************************************************************************/
941static long
942NodeComputeDepth(
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******************************************************************************/
1008static void
1009NetworkAddDanglingNodesToOrderList(
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******************************************************************************/
1054static void
1055NetworkAddNSVarsToOrderList(
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******************************************************************************/
1119static lsList
1120LatchNSListConvertToLatchDataInputList(
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******************************************************************************/
1148static void
1149NodeSetDepth(
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
1170static void
1171MddGroupVariables(
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
Note: See TracBrowser for help on using the repository browser.