source: vis_dev/vis-2.3/src/ntk/ntkGraph.c @ 99

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

vis2.3

File size: 29.9 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ntkGraph.c]
4
5  PackageName [ntk]
6
7  Synopsis    [Routines related to the abstract graph of a network.]
8
9  Author      [Adnan Aziz, Tom Shiple]
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 "ntkInt.h"
33
34static char rcsid[] UNUSED = "$Id: ntkGraph.c,v 1.11 2005/04/16 04:24:15 fabio Exp $";
35
36/*---------------------------------------------------------------------------*/
37/* Structure declarations                                                     */
38/*---------------------------------------------------------------------------*/
39
40/**Enum************************************************************************
41
42  Synopsis [Used to keep track of the state of a node during depth first
43  search.required]
44
45******************************************************************************/
46typedef enum {
47  dfsWhite_c,   /* unvisited node */
48  dfsGrey_c,    /* node on "stack" */
49  dfsBlack_c    /* node completely visited */
50} DfsColor;
51
52
53/**AutomaticStart*************************************************************/
54
55/*---------------------------------------------------------------------------*/
56/* Static function prototypes                                                */
57/*---------------------------------------------------------------------------*/
58
59static void RegionFindNodesRecursively(Ntk_Node_t *node, st_table *leaves, st_table *result);
60static boolean NodeTestCannotReachCycle(Ntk_Node_t * node);
61static boolean NodeTestCoveredByLeaves(Ntk_Node_t *node, st_table *leaves, st_table *visited);
62static DfsColor NodeReadColor(Ntk_Node_t * node);
63static void NodeSetColor(Ntk_Node_t * node, DfsColor color);
64static void NodeSetTfoLatchList(Ntk_Node_t * node, lsList tfoLatchList);
65static lsList NodeReadTfoLatchList(Ntk_Node_t * node);
66static void NodeFreeTfoLatchList(Ntk_Node_t * node);
67static void ListAppendList(lsList list1, lsList list2);
68static lsList NodeComputeTfoLatchList(Ntk_Node_t * node);
69static void NodeRecursivelyComputeTransitiveFaninNodes(Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches);
70static void NodeComputeTopologicalOrderRecursively(Ntk_Node_t *node, st_table *leafNodesTable, lsList topologicalNodeList);
71static void NodeComputeTransitiveFaninNodes(Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches);
72
73/**AutomaticEnd***************************************************************/
74
75
76/*---------------------------------------------------------------------------*/
77/* Definition of exported functions                                          */
78/*---------------------------------------------------------------------------*/
79
80/**Function********************************************************************
81
82  Synopsis    [Returns array of nodes in transitive fanout of node.]
83
84  Description [Returns array of nodes in transitive fanout of node.  If depth is
85  non-zero, then only includes nodes within depth of node.  If depth is zero,
86  then includes all nodes up to and including combinational outputs.]
87
88  SideEffects [required]
89
90  SeeAlso     [optional]
91
92******************************************************************************/
93array_t *
94Ntk_NodeComputeTransitiveFanoutNodes(
95  array_t * nodeArray,
96  int  depth)
97{
98  fail("not yet implemented");
99  return(NIL(array_t));
100}
101
102/**Function********************************************************************
103
104  Synopsis    [Returns array of nodes in transitive fanin of node.]
105
106  Description [Returns array of nodes in transitive fanin of node.  If depth is
107  non-zero, then only includes nodes within depth of node.  If depth is zero,
108  then includes all nodes up to and including combinational inputs.]
109
110  SideEffects [required]
111
112  SeeAlso     [optional]
113
114******************************************************************************/
115array_t *
116Ntk_NodeComputeTransitiveFanInputNodes(
117  array_t * nodeArray,
118  int  depth)
119{
120  fail("not yet implemented");
121  return(NIL(array_t));
122}
123
124/**Function********************************************************************
125
126  Synopsis [Returns array of nodes in transitive fanin of nodeArray.]
127
128  Description [Returns array of nodes in transitive fanin of nodes in
129  nodeArray.  If stopAtLatches is TRUE, the search terminates at
130  combinational inputs which are latches; otherwise it continues, and
131  the search terminates only at primary inputs and pseudo inputs. It
132  is an error if this function is called with an empty array.]
133
134  SideEffects [required]
135
136  SeeAlso     [optional]
137
138******************************************************************************/
139array_t *
140Ntk_NodeComputeTransitiveFaninNodes(
141  Ntk_Network_t *network,
142  array_t * nodeArray,
143  boolean stopAtLatches,
144  boolean combInputsOnly)
145{
146  int i;
147  Ntk_Node_t *node;
148  st_generator *stGen;
149  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
150  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );
151
152  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
153    NodeComputeTransitiveFaninNodes(node, resultTable, stopAtLatches );
154  }
155 
156  st_foreach_item( resultTable, stGen, &node, NULL ){
157    if ( !combInputsOnly || Ntk_NodeTestIsCombInput(node) ) 
158      array_insert_last( Ntk_Node_t *, resultArray, node );
159  }
160  st_free_table( resultTable );
161 
162  return resultArray;
163}
164
165/**Function********************************************************************
166
167  Synopsis    [Returns array of combinational inputs in transitive fanin
168  of nodeArray.]
169
170  Description [Returns array of nodes in transitive fanin of nodes in
171  nodeArray.  If stopAtLatches is TRUE, the search terminates at
172  combinational inputs which are latches; otherwise it continues, and
173  the search terminates only at primary inputs and pseudo inputs. It
174  is an error if this function is called with an empty array.]
175
176  SideEffects [required]
177
178  SeeAlso     [optional]
179
180******************************************************************************/
181array_t *
182Ntk_NodeComputeCombinationalSupport(
183  Ntk_Network_t *network,
184  array_t * nodeArray,
185  boolean stopAtLatches )
186{
187  lsGen gen;
188  int i;
189  Ntk_Node_t *node;
190  st_generator *stGen;
191  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
192  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );
193
194  Ntk_NetworkForEachNode( network, gen, node ) {
195        NodeSetColor( node, dfsWhite_c );
196  }
197
198  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
199        NodeRecursivelyComputeTransitiveFaninNodes( node, resultTable, stopAtLatches );
200  }
201
202  st_foreach_item( resultTable, stGen, &node, NULL ){
203        array_insert_last( Ntk_Node_t *, resultArray, node );
204  }
205  st_free_table( resultTable );
206
207  return resultArray;
208}
209
210
211/**Function********************************************************************
212
213  Synopsis [Return table of all nodes lying in fanin of roots, stopping
214  whenever a leaf node is reached. The search also stops on nodes that pass
215  the test Ntk_NodeTestIsConstant.  Note that the leaves are also present in
216  the returned table.]
217
218  SideEffects []
219
220******************************************************************************/
221st_table *
222Ntk_RegionFindNodes(
223  array_t *roots, 
224  st_table *leaves)
225{
226  int i;
227  st_table *result = st_init_table(st_ptrcmp, st_ptrhash);
228  for (i = 0; i < array_n(roots); i++) {
229    Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
230    RegionFindNodesRecursively(root, leaves, result);
231  }
232  return result;
233}
234
235/**Function********************************************************************
236
237  Synopsis    [Computes the set of latches that each latch transitively
238  fanouts to.]
239
240  Description [For each latch, builds a list containing those latches which
241  can be transitively reached from the fanout of the latch.  If a latch
242  doesn't have any latches in its TFO, then an empty list will be built. The
243  dependencies are returned as a hash table mapping each latch (Ntk_Node_t *)
244  to a list (lsList). It is the user's responsibility to free the returned
245  hash table and the lists stored as values in the table.  NOTE: this function
246  name is a misnomer because it does not compute the latches on which a given
247  latch depends, but instead computes the latches to which a given latch
248  fanouts.]
249
250  SideEffects []
251
252******************************************************************************/
253st_table *
254Ntk_NetworkComputeLatchDependencies(
255  Ntk_Network_t * network)
256{
257  lsGen       gen;
258  Ntk_Node_t *node;
259  Ntk_Node_t *latch;
260  st_table   *latchDependencies = st_init_table(st_ptrcmp, st_ptrhash);
261
262  /*
263   * Initialize the TFO latch list of each node to NULL.
264   */
265  Ntk_NetworkForEachNode(network, gen, node) {
266    NodeSetTfoLatchList(node, (lsList) NULL);
267  }
268
269  /*
270   * For each latch, compute the set of latches in its TFO (including possibly
271   * itself).  Accumulate this set of latches into a list, and when the list
272   * is complete, store the latch and list as the key and value in the hash
273   * table.
274   */
275  Ntk_NetworkForEachLatch(network, gen, latch) {
276    int         i;
277    Ntk_Node_t *fanout;
278    lsList      tfoLatchList = lsCreate();  /* allocate a fresh list */
279
280    /*
281     * Get the latches in the TFO of each fanout of latch, and accumulate into
282     * a list. Note that we can't call NodeComputeTfoLatchList on latch
283     * itself, because latches serve as the terminal case of the recursion.
284     */
285    Ntk_NodeForEachFanout(latch, i, fanout) {
286      lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);
287
288      ListAppendList(tfoLatchList, fanoutTfoLatchList);
289    }
290
291    st_insert(latchDependencies, (char *) latch, (char *) tfoLatchList);
292   
293  }
294
295  /*
296   * Free the tfoLatchList stored at the nodes.  Only nodes in the transitive
297   * fanout of latches will have a non-NULL list, but we just call free
298   * tfoLatchList function on each node.  Note that the lists being returned
299   * in the hash table are distinct from those stored at nodes.
300   */
301  Ntk_NetworkForEachNode(network, gen, node) {
302    NodeFreeTfoLatchList(node);
303  }
304
305  return (latchDependencies);
306}
307
308
309/**Function********************************************************************
310
311  Synopsis    [Returns 0 if a combinational cycle exists, else returns 1.]
312
313  Description [Returns 0 if a cycle exists in the network, else returns 1.
314  Latches are considered to break cycles.  If a cycle is found, then a message
315  is written to error_string (see the error package) giving two nodes in the
316  cycle.  Use a code fragment like the following to retrieve the error message:
317  <pre>
318    error_init();
319    status = Ntk_NetworkTestIsAcyclic(network);
320    if (status == 0) {
321      (void) fprintf(fp, "%s", error_string());
322    }
323  </pre>]
324 
325  SideEffects []
326
327  Comment     [This function implements the DFS routine outlined in Cormen,
328  Leiserson, Rivest, "Introduction to Algorithms", p. 478. It has been
329  specialized to just detect cycles.]
330
331******************************************************************************/
332boolean
333Ntk_NetworkTestIsAcyclic(
334  Ntk_Network_t * network)
335{
336  lsGen       gen;
337  Ntk_Node_t *node;
338  boolean     status = 1; /* In case network has no vertices. */
339
340  /* The meaning of the colors is:
341   *   white: node has not been visited yet
342   *   grey:  node is on the "stack"
343   *   black: node, and all its descendents, have been visited
344   */
345
346  /*
347   * Initialize the color of each node to white.
348   */
349  Ntk_NetworkForEachNode(network, gen, node) {
350    NodeSetColor(node, dfsWhite_c);
351  }
352 
353  /*
354   * Recursively visit each unvisited node.  The order in which we visit the
355   * nodes is immaterial. 
356   */ 
357  Ntk_NetworkForEachNode(network, gen, node) {
358    if (NodeReadColor(node) == dfsWhite_c) {
359      status = NodeTestCannotReachCycle(node);
360      if (status == 0) {
361        /* A cycle has been found. */
362        break;
363      }
364    }
365  }
366
367  /*
368   * Colors will be left in the undef field of the nodes, but we don't care.
369   */
370  return (status);
371}
372
373
374/**Function********************************************************************
375
376  Synopsis [Returns TRUE if leaves cover the support of roots, otherwise
377  returns FALSE.]
378
379  Description [The function takes as input a network, a hash table of nodes
380  called leaves, and an array of nodes called roots. It returns TRUE if the
381  nodes in leaves cover the support of the nodes in roots, otherwise it
382  returns FALSE.  In other words, if there exists a combinational input in the
383  transitive fanin of a root, which can be reached from the root without
384  passing through a leaf, then FALSE is returned.  If FALSE is returned, then
385  the message "Node b found in the support of node c" is written to
386  error_string, where b is a combinational input not in leaves and c is a
387  root. It is allowed that some roots are themselves leaves, and that some
388  leaves are in the transitive fanin of other leaves.  Combinational cycles
389  within the region defined by roots and leaves have no effect on the result.
390  If TRUE is returned, then the runtime of this procedure is proportional to
391  the number of nodes in the region defined by roots and leaves; if FALSE is
392  returned, then the worst case is proportional to the number of nodes in the
393  network.]
394
395  Comment [The undef field is modified of some of the nodes in the network to
396  which node belongs.]
397 
398  SideEffects []
399
400******************************************************************************/
401boolean
402Ntk_NetworkTestLeavesCoverSupportOfRoots(
403  Ntk_Network_t *network,
404  array_t       *roots,
405  st_table      *leaves)
406{
407  int         i;
408  Ntk_Node_t *root;
409  st_table   *visited = st_init_table(st_ptrcmp, st_ptrhash);
410 
411  /* Perform DFS from the roots.  Return FALSE upon the first failure. */
412  arrayForEachItem(Ntk_Node_t *, roots, i, root) {
413    boolean status = NodeTestCoveredByLeaves(root, leaves, visited);
414   
415    if(!status) {
416      error_append(Ntk_NodeReadName(root));
417      error_append(".\n");
418      st_free_table(visited);
419      return FALSE; 
420    }
421  }
422  st_free_table(visited);
423  return TRUE;
424}
425
426
427/*---------------------------------------------------------------------------*/
428/* Definition of internal functions                                          */
429/*---------------------------------------------------------------------------*/
430/**Function********************************************************************
431
432  Synopsis    [Computes the topological order of nodes in the network
433  for a given array of root nodes and the leaf nodes.]
434
435  Description [Depth first traversal is used from each node in the
436  root node array. The search is terminated when a node in the leaf
437  table is reached. It is necessary that all the root nodes eventually
438  depend on the leaf nodes. The returned list contains the nodes in
439  the topological order.]
440
441  SideEffects []
442
443  SeeAlso     []
444
445******************************************************************************/
446lsList
447Ntk_NetworkComputeTopologicalOrder(Ntk_Network_t *network, array_t
448                                  *rootNodesArray, st_table
449                                  *leafNodesTable) 
450{
451  int i;
452  lsList topologicalNodeList = lsCreate();
453  Ntk_Node_t *node;
454  lsGen gen;
455 
456  Ntk_NetworkForEachNode(network, gen, node) {
457    NodeSetColor(node, dfsWhite_c);
458  }
459
460  for (i=0; i<array_n(rootNodesArray); i++){
461    node = array_fetch(Ntk_Node_t *, rootNodesArray, i);
462    NodeComputeTopologicalOrderRecursively(node, leafNodesTable,
463                                           topologicalNodeList);
464  }
465  return topologicalNodeList;
466}
467
468
469/*---------------------------------------------------------------------------*/
470/* Definition of static functions                                            */
471/*---------------------------------------------------------------------------*/
472
473/**Function********************************************************************
474
475  Synopsis [Recursively add all fanins of node to result, stopping at leaves
476  and constants.]
477
478  SideEffects []
479
480******************************************************************************/
481static void
482RegionFindNodesRecursively(
483  Ntk_Node_t *node, 
484  st_table *leaves,
485  st_table *result)
486{
487  int i;
488  Ntk_Node_t *fanin;
489
490  if (st_is_member(result, (char *) node)) {
491    /* already visited this node */
492    return;
493  }
494  else {
495    /*
496     * Add to table before recursing, to avoid infinite loops in presence of
497     * combinational cycles.
498     */
499    st_insert(result, (char *) node, NIL(char));
500  }
501 
502 
503  if (!st_is_member(leaves, (char *) node) && !Ntk_NodeTestIsConstant(node)) {
504    /* not a leaf; recurse */
505    Ntk_NodeForEachFanin(node, i, fanin) {
506      RegionFindNodesRecursively(fanin, leaves, result);
507    }
508  }
509
510  return;
511}
512
513/**Function********************************************************************
514
515  Synopsis    [Returns 1 if node cannot reach a cycle, else returns 0.]
516
517  Description [Visits a node, and recursively all of its children, to
518  determine if the node can reach a combinational cycle. If it cannot, the
519  function return 1, else it returns 0.  If a cycle is found, then a message
520  is written to error_string.]
521
522  SideEffects []
523
524******************************************************************************/
525static boolean
526NodeTestCannotReachCycle(
527  Ntk_Node_t * node)
528{
529  Ntk_Node_t *fanout;
530  int i;
531
532  /*
533   * Set the color of node to grey to indicate that it is on the "stack".
534   */
535  NodeSetColor(node, dfsGrey_c);
536
537  Ntk_NodeForEachFanout(node, i, fanout) {
538    /*
539     * Traverse fanout if it is *not* a latch; latches break combinational cycles.
540     */
541    if (Ntk_NodeTestIsLatch(fanout) == 0) {
542      DfsColor fanoutColor = NodeReadColor(fanout);
543
544      /*
545       * If fanout is white, it has not been visited yet, so visit it, and
546       * break the search if it can reach a cycle.  Else if fanout is grey, it
547       * means that fanout is also on the stack, so a cycle has been found;
548       * thus break.  Else, the fanout is black, and there is nothing to do.
549       */
550      if (fanoutColor == dfsWhite_c) {
551        if (NodeTestCannotReachCycle(fanout) == 0) {
552          return (0);
553        }
554      }
555      else if (fanoutColor == dfsGrey_c) {
556        error_append("(");
557        error_append(Ntk_NodeReadName(node));
558        error_append(", ");
559        error_append(Ntk_NodeReadName(fanout));
560        error_append(")");
561        return (0);
562      } 
563    }
564  }
565
566  /*
567   * Set the color of node to black to indicate that it has been visited.
568   */
569  NodeSetColor(node, dfsBlack_c);
570 
571  /*
572   * No cycles found from node.
573   */
574  return (1);
575}
576
577
578/**Function********************************************************************
579
580  Synopsis [Returns FALSE if the support of node contains a combinational
581  input that is not a leaf, otherwise returns TRUE.]
582
583  Description [The function does a DFS starting from node, never going beyond
584  a leaf or a node already visited. If it reaches a combinational input that
585  is not a leaf it returns FALSE.  If this doesn't happen for all the fanins
586  of the node, then TRUE is returned.]
587
588  SideEffects []
589
590  SeeAlso     [Ntk_NetworkTestLeavesCoverSupportOfRoots]
591
592******************************************************************************/
593static boolean
594NodeTestCoveredByLeaves(
595  Ntk_Node_t *node,
596  st_table   *leaves,
597  st_table   *visited)
598{
599  int         i;
600  Ntk_Node_t *fanin;
601
602  /*
603   * If node has already been visited, just return.  Else, mark it as
604   * visited. Note that it is important to mark it as visited BEFORE recursing,
605   * in case combinational cycles are present.
606   */
607  if (st_is_member(visited, (char *) node)) {
608    return TRUE;
609  }
610  else {
611    st_insert(visited, (char *) node, NIL(char));
612  }
613
614  if (st_is_member(leaves, (char *) node)) {
615    /*
616     * Positive termination of recursion: if node is a leaf, then everything
617     * is fine.
618     */ 
619    return TRUE;
620  }
621  else {
622    /* Node is not a leaf. */
623    if (Ntk_NodeTestIsCombInput(node)) {
624      /*
625       * Negative termination of recursion: a combinational input was reached
626       * without seeing a leaf.
627       */ 
628      error_append("Node ");
629      error_append(Ntk_NodeReadName(node));
630      error_append(" found in the support of node ");
631      return FALSE;
632    }
633    else {
634      /*
635       * Node is not a leaf nor a combinational input.  Recurse over fanins.
636       * Return FALSE if any fanins fail the test.
637       */
638      Ntk_NodeForEachFanin(node, i, fanin) {
639        boolean status = NodeTestCoveredByLeaves(fanin, leaves, visited);
640        if (!status) {
641          return FALSE;
642        }
643      }
644      /*
645       * If the loop terminates without the function returning, then each
646       * fanin has already been visited and no dfsWhite_c-labelled comb input
647       * can be reached from the fanins. Therefore, return TRUE.
648       */
649      return TRUE;
650    }
651  }
652 
653}
654
655
656/**Function********************************************************************
657
658  Synopsis    [Gets the color of a node.]
659
660  SideEffects []
661
662  SeeAlso     [NodeSetColor]
663
664******************************************************************************/
665static DfsColor
666NodeReadColor(
667  Ntk_Node_t * node)
668{
669  return ((DfsColor) (long) Ntk_NodeReadUndef(node));
670}
671
672
673/**Function********************************************************************
674
675  Synopsis    [Sets the color of a node.]
676
677  SideEffects []
678
679  SeeAlso     [NodeReadColor]
680
681******************************************************************************/
682static void
683NodeSetColor(
684  Ntk_Node_t * node,
685  DfsColor  color)
686{
687  Ntk_NodeSetUndef(node, (void *) (long) color);
688}
689
690
691/**Function********************************************************************
692
693  Synopsis    [Sets the tfoLatchList of a node.]
694
695  SideEffects []
696
697  SeeAlso     [NodeReadTfoLatchList NodeFreeTfoLatchList]
698
699******************************************************************************/
700static void
701NodeSetTfoLatchList(
702  Ntk_Node_t * node,
703  lsList  tfoLatchList)
704{
705  Ntk_NodeSetUndef(node, (void *) tfoLatchList);
706}
707
708
709/**Function********************************************************************
710
711  Synopsis    [Gets the TfoLatchList of a node.]
712
713  SideEffects []
714
715  SeeAlso     [NodeSetTfoLatchList NodeFreeTfoLatchList]
716
717******************************************************************************/
718static lsList
719NodeReadTfoLatchList(
720  Ntk_Node_t * node)
721{
722  return ((lsList) Ntk_NodeReadUndef(node));
723}
724
725
726/**Function********************************************************************
727
728  Synopsis    [Frees the tfoLatchList of a node.]
729
730  Description [If the node has a non-NULL tfoLatchList, then frees the list
731  and sets the tfoLatchList of node to NULL; else, does nothing.]
732 
733  SideEffects []
734
735  SeeAlso     [NodeReadTfoLatchList NodeSetTfoLatchList ]
736
737******************************************************************************/
738static void
739NodeFreeTfoLatchList(
740  Ntk_Node_t * node)
741{
742  lsList tfoLatchList = NodeReadTfoLatchList(node);
743
744  if (tfoLatchList != (lsList) NULL) {
745    (void) lsDestroy(tfoLatchList, (void (*) (lsGeneric)) NULL);
746    Ntk_NodeSetUndef(node, (void *) NULL);
747  }
748}
749
750/**Function********************************************************************
751
752  Synopsis    [Appends list2 to list1.]
753
754  Description [Adds the elements of list2 to the end of list1.  The elements
755  of list2 are not copied. If an element of list2 already exists in list1,
756  then it is not added to the end of list1. List2 is not changed by this
757  operation.]
758
759  SideEffects [List1 is modified.]
760
761  SeeAlso     []
762
763******************************************************************************/
764static void
765ListAppendList(
766  lsList  list1,
767  lsList  list2)
768{
769  lsGen      gen;
770  lsGeneric  data;
771  st_table  *table1 = st_init_table(st_ptrcmp, st_ptrhash);
772 
773  /*
774   * Load a hash table mapping each item in list1 to NULL.
775   */
776  gen = lsStart(list1);
777  while (lsNext(gen, &data, LS_NH) == LS_OK) {
778    st_insert(table1, (char *) data, (char *) NULL);
779  }
780  (void) lsFinish(gen);
781
782  /*
783   * For each item in list2, if it's not already present in list1, then add it
784   * to the end of list1.
785   */
786  lsForEachItem(list2, gen, data) {
787    if (st_is_member(table1, (char *) data) == 0) {
788      lsNewEnd(list1, data, LS_NH);
789    }
790  }
791  st_free_table(table1);
792}
793
794
795/**Function********************************************************************
796
797  Synopsis    [Computes the set of latches in the TFO of a node.]
798
799  Description [Computes the set of latches in the TFO of a node.  If there are
800  no latches in the TFO, then an empty list is returned.  In the special case
801  where the node is itself a latch, then a list containing just the node is
802  returned; this is one of the terminal cases of the recursion. The other
803  terminal case is a node with no immediate fanouts.]
804
805  SideEffects []
806
807******************************************************************************/
808static lsList
809NodeComputeTfoLatchList(
810  Ntk_Node_t * node)
811{
812  lsList tfoLatchList = NodeReadTfoLatchList(node);
813
814  /*
815   * If node already has a non-NULL tfoLatchList, then just return it (this
816   * can happen if the node was already visited via one of its other
817   * fanins). Otherwise, create an empty list and fill it appropriately.
818   */
819  if (tfoLatchList != (lsList) NULL) {
820    return (tfoLatchList);
821  }
822  else {
823    tfoLatchList = lsCreate();
824
825    if (Ntk_NodeTestIsLatch(node)) {
826      /*
827       * Special case; terminal condition.
828       */
829      lsNewEnd(tfoLatchList, (lsGeneric) node, LS_NH);
830    }
831    else {
832      int         i;
833      Ntk_Node_t *fanout;
834     
835      /*
836       * Get the latches in the TFO of each fanout of node, and accumulate into
837       * a list.
838       */
839      Ntk_NodeForEachFanout(node, i, fanout) {
840        lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);
841
842        ListAppendList(tfoLatchList, fanoutTfoLatchList);
843      }
844    }
845
846    /*
847     * Store the list with the node, then return the list.
848     */
849    NodeSetTfoLatchList(node, tfoLatchList);
850    return (tfoLatchList);   
851  }
852}
853
854
855
856/**Function********************************************************************
857
858  Synopsis    [Computes the set of combinational inputs in the TFI of the node.]
859
860  Description [Computes the set of combinational inputs in the TFI of the node.
861  If stopAtLatches is TRUE, the search terminates at combinational inputs which
862  are latches; otherwise it continues, and the search terminates only at primary
863  inputs and pseudo inputs.]
864
865  SideEffects []
866
867******************************************************************************/
868static void
869NodeRecursivelyComputeTransitiveFaninNodes( 
870  Ntk_Node_t *node, 
871  st_table *resultTable,
872  boolean stopAtLatches) 
873{
874  int i;
875  Ntk_Node_t * fanin;
876
877  /* test if we have already started processing this node */
878  if ( NodeReadColor( node ) == dfsBlack_c ) {
879        return;
880  }
881  NodeSetColor( node, dfsBlack_c );
882
883  if ( Ntk_NodeTestIsCombInput( node ) ) {
884        st_insert( resultTable, (char *) node, (char *) 0 );
885  }
886
887  if ( Ntk_NodeTestIsInput(node) || ((stopAtLatches == TRUE)&&(Ntk_NodeTestIsLatch(node))) ) {
888        return;
889  }
890
891  Ntk_NodeForEachFanin( node, i, fanin ) {
892        NodeRecursivelyComputeTransitiveFaninNodes( fanin, resultTable, stopAtLatches );
893  }
894}
895
896
897
898/**Function********************************************************************
899
900  Synopsis    [Recursively performs the depth-first traversal of the
901  network starting at the given node.]
902
903  Description [Recursively performs the depth-first traversal of the
904  network starting at the given node.]
905
906  SideEffects []
907
908  SeeAlso     []
909
910******************************************************************************/
911static void
912NodeComputeTopologicalOrderRecursively(Ntk_Node_t *node, st_table
913                                       *leafNodesTable, lsList
914                                       topologicalNodeList) 
915{
916  int i;
917  Ntk_Node_t *fanin;
918 
919  if (NodeReadColor(node) == dfsBlack_c){
920    /* Has already been put in the list. */
921    return;
922  }
923  if (NodeReadColor(node) == dfsGrey_c){
924    /* Indicates that this node is currently being processed (possibly a
925       combinational loop). */
926    return;
927  }
928  if (st_is_member(leafNodesTable, (char *)node)== 0){
929    NodeSetColor(node, dfsGrey_c);
930    Ntk_NodeForEachFanin(node, i, fanin){
931      NodeComputeTopologicalOrderRecursively(fanin, leafNodesTable,
932                                             topologicalNodeList);
933    }
934  }
935  NodeSetColor(node, dfsBlack_c);
936  lsNewEnd(topologicalNodeList, (lsGeneric)node, LS_NH);
937  return;
938}
939
940/**Function********************************************************************
941
942  Synopsis [Computes the set of nodes in the TFI of the node.]
943
944  Description [Computes the set of nodes in the TFI of the node.  If
945  stopAtLatches is TRUE, the search terminates at combinational inputs
946  which are latches; otherwise it continues, and the search terminates
947  only at primary inputs and pseudo inputs.]
948
949  SideEffects []
950
951******************************************************************************/
952static void
953NodeComputeTransitiveFaninNodes( 
954  Ntk_Node_t *node, 
955  st_table *resultTable,
956  boolean stopAtLatches) 
957{
958  int i;
959  Ntk_Node_t * fanin;
960 
961  /* test if we have already started processing this node */
962  if (st_is_member(resultTable, node))
963    return;
964
965  st_insert(resultTable, node, (char *)(long)2);
966
967  if (Ntk_NodeTestIsInput(node) || (stopAtLatches && Ntk_NodeTestIsLatch(node)))
968    return;
969
970  Ntk_NodeForEachFanin(node, i, fanin) {
971    NodeComputeTransitiveFaninNodes(fanin, resultTable, stopAtLatches);
972  }
973}
974
Note: See TracBrowser for help on using the repository browser.