source: vis_dev/vis-2.3/src/res/resLayer.c @ 64

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

vis2.3
File size: 29.1 KB
RevLine 
[14]1/**CFile***********************************************************************
2
3  FileName    [resLayer.c]
4
5  PackageName [res]
6
7  Synopsis    [This file is responsible for computing the "layers" in a circuit
8  depending on the method]
9
10  Author      [Kavita Ravi    <ravi@boulder.colorado.edu> and
11               Abelardo Pardo <abel@boulder.colorado.edu>]
12               
13  Copyright [This file was created at the University of Colorado at Boulder.
14  The University of Colorado at Boulder makes no warranty about the suitability
15  of this software for any purpose.  It is presented on an AS IS basis.]
16
17******************************************************************************/
18
19#include "resInt.h"
20
21static char rcsid[] UNUSED = "$Id: resLayer.c,v 1.36 2005/04/16 07:31:03 fabio Exp $";
22
23/*---------------------------------------------------------------------------*/
24/* Constant declarations                                                     */
25/*---------------------------------------------------------------------------*/
26
27/*---------------------------------------------------------------------------*/
28/* Structure declarations                                                    */
29/*---------------------------------------------------------------------------*/
30
31/*---------------------------------------------------------------------------*/
32/* Type declarations                                                         */
33/*---------------------------------------------------------------------------*/
34
35/*---------------------------------------------------------------------------*/
36/* Variable declarations                                                     */
37/*---------------------------------------------------------------------------*/
38
39/*---------------------------------------------------------------------------*/
40/* Macro declarations                                                        */
41/*---------------------------------------------------------------------------*/
42
43/**AutomaticStart*************************************************************/
44
45/*---------------------------------------------------------------------------*/
46/* Static function prototypes                                                */
47/*---------------------------------------------------------------------------*/
48
49static array_t * ComputeCompositionLayersAsap(Ntk_Network_t *network, array_t *outputArray, array_t *ignoreArray);
50static array_t * ComputeCompositionLayersAlap(Ntk_Network_t *network, array_t *outputArray, array_t *ignoreArray);
51static int ComputeAlapLabelling(Ntk_Network_t *network, st_table *nodeLabelling);
52static void ComputeAlapLabellingRecur(Ntk_Node_t *node, st_table *nodeLabelling);
53static st_table * ComputeTransitiveFanin(array_t *outputArray);
54static void ComputeTransitiveFaninRecur(Ntk_Node_t *nodePtr, st_table *faninTable);
55static void RecursiveDecrementFanoutCount(Ntk_Node_t *nodePtr, st_table *fanoutCountTable, st_table *visitedTable);
56
57/**AutomaticEnd***************************************************************/
58
59
60/*---------------------------------------------------------------------------*/
61/* Definition of exported functions                                          */
62/*---------------------------------------------------------------------------*/
63
64
65/*---------------------------------------------------------------------------*/
66/* Definition of internal functions                                          */
67/*---------------------------------------------------------------------------*/
68
69/**Function********************************************************************
70
71  Synopsis [Computes the layers of nodes of the network that represent the order
72  for composition.]
73
74  Description [ Computes the layers of nodes of the network that represent the
75  order for composition. When composing an ADD with nodes in the circuit
76  starting with the primary outputs, several nodes in the network can be
77  composed at the same time producing "layers" in the network. When a node is
78  in the layer and it is composed with its fanin nodes, the original node does
79  not belong to the ADD any more, and its fanin nodes become now part of the
80  ADD.  There are several ways to produce this cut, we provide two such
81  methods.  This procedure reads the flag <tt>residue_layers<\tt> and calls the
82  pertinent function. The procedure takes as arguments the network whose layers
83  need to be formed, the set of outputs that need to be considered and the set
84  of outputs that can be ignored. The procedure returns an array of layers]
85
86  SideEffects []
87
88  SeeAlso [ComputeCompositionLayersAsap ComputeCompositionLayersAlap]
89
90******************************************************************************/
91array_t *
92ResComputeCompositionLayers(Ntk_Network_t *network, 
93                            array_t *outputArray,   
94                            array_t *ignoreArray)   
95{
96  ResLayerScheduleMethod layerMethod; /* read from the set value */
97  array_t *result;  /* Result obtained from procedure */
98  char *flagValue;  /* To store the value read from the flag */
99
100  /* Read the value from the flag */
101  flagValue = Cmd_FlagReadByName("residue_layer_schedule");
102  if (flagValue == NIL(char)) {
103    layerMethod = ResDefaultScheduleLayerMethod_c;
104  } 
105  else {
106    if (strcmp(flagValue, "asap") == 0) {
107      layerMethod = ResLayerAsap_c;
108    }
109    else if (strcmp(flagValue, "alap") == 0) {
110      layerMethod = ResLayerAlap_c;
111    }
112    else {
113      (void) fprintf(vis_stderr, "** res error: Unknown method to compute layers.");
114      (void) fprintf(vis_stderr, "** res error: Assuming default method.\n");
115      layerMethod = ResDefaultScheduleLayerMethod_c;
116    }
117  }
118
119  /* Call the pertinent procedure */
120  switch (layerMethod) {
121  case ResLayerAlap_c: {
122      result = ComputeCompositionLayersAlap(network, outputArray, ignoreArray);
123      break;
124      }
125  case ResLayerAsap_c: {
126      result = ComputeCompositionLayersAsap(network, outputArray, ignoreArray);
127      break;
128      }
129  default: {
130      (void) fprintf(vis_stdout, "** res warning: Layer computation method not implemented.");
131      (void) fprintf(vis_stdout, "** res warning: Executing default method.\n");
132      result = ComputeCompositionLayersAlap(network, outputArray, ignoreArray);
133      break;
134    }
135  }
136
137  return result;
138} /* End of ResComputeCompositionLayers */
139
140
141/**Function********************************************************************
142
143  Synopsis [Prints out the different layers in the circuit.]
144
145  Description [Prints the nodes in various layers starting with the output
146  along with their layer numbers. The procedure also counts the number of new
147  variables that the current layer brings in. The procedure takes the network
148  whose layers are to be printed and the layer array structure.]
149 
150  SideEffects        []
151
152  SeeAlso            [Res_NetworkResidueVerify]
153
154******************************************************************************/
155void
156ResLayerPrintInfo(Ntk_Network_t *network, 
157                  array_t *layerArray)
158{
159
160  Ntk_Node_t   *nodePtr, *faninNodePtr; /* Node being processed */
161  st_table *faninTable;                 /* Current nodes */
162  int layerIndex, newVars;              /* index of the layer being processed */
163  int i,j;                              /* For array traversal */
164  array_t *currentLayer;                /* layer info */
165
166  /* keep track of all nodes that have appeared in the support */
167  faninTable = st_init_table(st_ptrcmp, st_ptrhash);
168  /* Loop over the number of elements in layerArray */
169  for (layerIndex = 0; layerIndex < array_n(layerArray); layerIndex++) {
170    /* reset new variables in the support of this array */
171    newVars = 0;
172   
173    (void) fprintf(vis_stdout, "Layer %d: ", layerIndex);
174
175    /* Access the layer info */
176    currentLayer = ResLayerFetchIthLayer(layerArray, layerIndex); 
177
178    /* Print the nodes in a layer that are not PIs */
179    LayerForEachNode(currentLayer, i, nodePtr) {
180      (void) fprintf(vis_stdout, "%s ", Ntk_NodeReadName(nodePtr));
181
182      /* store fanin nodes in the table, keep count */
183      Ntk_NodeForEachFanin(nodePtr, j, faninNodePtr) {
184        if (!st_is_member(faninTable, (char *)faninNodePtr)) {
185          if (!((Ntk_NodeTestIsLatch(nodePtr) &&
186                    (Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
187                     Ntk_NodeTestIsLatchInitialInput(faninNodePtr))) ||
188                Ntk_NodeTestIsConstant(faninNodePtr))) {
189           
190            st_insert(faninTable, (char *)faninNodePtr, NIL(char));
191            newVars++;
192          }
193        }
194      }
195    }
196
197    (void) fprintf(vis_stdout,": SUPPORT = %d", newVars);
198    (void) fprintf(vis_stdout, "\n");
199
200   
201  } /* End of for every layer */
202
203  /* Clean up */
204  st_free_table(faninTable);
205  return;
206} /* End of ResLayerPrintInfo */
207
208
209/**Function********************************************************************
210
211  Synopsis [Free the layer information computed for each network.]
212
213  Description [Free the layer information computed for each network. Takes the
214  layer structure to be freed as the argument.]
215 
216  SideEffects   []
217
218  SeeAlso            [Res_NetworkResidueVerify]
219
220******************************************************************************/
221void
222ResLayerArrayFree(array_t *layerArray)
223{
224  int i, end;
225  array_t *currentLayer;
226
227  i = 0;
228  end = array_n(layerArray);
229  for (i =0; i < end ; i++) {
230    currentLayer = ResLayerFetchIthLayer(layerArray, i);
231    LayerFree(currentLayer);
232  }
233  array_free(layerArray);
234} /* End of ResLayerArrayFree */
235
236/*---------------------------------------------------------------------------*/
237/* Definition of static functions                                            */
238/*---------------------------------------------------------------------------*/
239
240/**Function********************************************************************
241
242  Synopsis [Computes the layers of nodes of the network based on the "as soon
243  as possible" heuristic.]
244
245  Description [Computes the layers of nodes of the network based on the "as
246  soon as possible" heuristic. When composing an Add with nodes starting from
247  the primary outputs, to the primary inputs, several nodes in the network are
248  candidates for composition simultaneously producing what we decided to call
249  "layers". This procedure schedules the composition of the nodes as soon as
250  possible under the "One-Time Rule" restriction. The One-Time Rule states that
251  a node may be composed into the ADD only when all its fanouts have been
252  composed in. The "as soon as possible" schedule is such that a node n is
253  composed with its fanin nodes f1,...,fn AS SOON AS all its fanouts have been
254  composed. The procedure returns an array of layers. Each node appears in only
255  one layer. The procedure takes as arguments the network whose layers are
256  required, the outputs to be considered and the outputs to be ignored.]
257
258  SideEffects        []
259
260  SeeAlso            [Res_NetworkResidueVerify ComputeCompositionLayersAlap]
261
262******************************************************************************/
263static array_t *
264ComputeCompositionLayersAsap(Ntk_Network_t *network, 
265                             array_t *outputArray,   
266                             array_t *ignoreArray)
267{
268  Ntk_Node_t *nodePtr, *faninNodePtr; /* variables to store node pointers */
269  int i, j, k;                        /* iterators */
270  st_generator *stGen;                /* generator to step through st_table */
271  char *key;                          /* values to read from st_table */
272  lsGen listGen;                      /* list generator to step through nodes */
273  array_t *currentLayer, *nextLayer;  /* array of nodes belonging to a layer */
274  array_t *layerArray;                /* array of layers */
275  st_table *fanoutCountTable;         /* table to store fanout counts of each
276                                       * node
277                                       */
278  int fanoutCount;                    /* variable to store fanout count of a
279                                       * node
280                                       */
281  int value;                          /* to read value off the st_table */
282  st_table *visitedTable;             /* table to store visited nodes */
283 
284  /* create a fanout count table starting with all nodes except PIs,
285   * constant node or a shadow node for any node but a latch(counts as
286   * comb output).
287   */
288  fanoutCountTable = st_init_table(st_ptrcmp, st_ptrhash); 
289  Ntk_NetworkForEachNode(network, listGen, nodePtr) {
290    /* does not nodes like PIs, shadow nodes, constants, undefined
291     * nodes to compute the fanouts, since they do not have to be
292     * composed into the circuit.
293     */
294    if ((Ntk_NodeTestIsCombOutput(nodePtr)) ||
295         (!(Ntk_NodeTestIsCombInput(nodePtr) ||
296          Ntk_NodeTestIsConstant(nodePtr) ||
297          Ntk_NodeTestIsUndefined(nodePtr) || 
298          Ntk_NodeTestIsShadow(nodePtr)))) {
299      st_insert(fanoutCountTable, (char *)nodePtr, 
300                (char *)(long)Ntk_NodeReadNumFanouts(nodePtr));
301    }
302  }
303 
304  /* take out outputs in directly verified table, if so desired */
305  /* Assume ignore table has node pointers , reduce fanout count of
306   * transitive fanin of these nodes
307   */
308  if (ignoreArray != NULL) {
309    visitedTable = st_init_table(st_ptrcmp, st_ptrhash);
310    arrayForEachItem(Ntk_Node_t *, ignoreArray, i, nodePtr) {
311      /* each key is an output node */
312      RecursiveDecrementFanoutCount(nodePtr, fanoutCountTable, visitedTable);
313    }
314    st_free_table(visitedTable);
315
316    /* remove all nodes that are primary inputs and those with fanout
317     * count 0 providing they are not primary outputs/ or latch inputs
318     * or latch initial values.
319     */
320    st_foreach_item_int(fanoutCountTable, stGen, &key, &value) {
321      fanoutCount = value;
322      nodePtr = (Ntk_Node_t *)key;
323      assert(fanoutCount >= -1);
324      if ((!Ntk_NodeTestIsCombOutput(nodePtr))
325          && (fanoutCount <= 0)) {
326        /* delete the item corresponding to fanoutCount i.e. value */
327        st_delete_int(fanoutCountTable, (char **)&key, &value);
328      }
329    }
330    /* remove all outputs that belong to ignore outputs */
331    arrayForEachItem(Ntk_Node_t *, ignoreArray, i, nodePtr) {
332      st_delete_int(fanoutCountTable, &nodePtr, &value);
333    }
334  } 
335
336  /* start preparing the layer array */
337  layerArray = array_alloc(array_t *, 0); 
338  currentLayer = LayerCreateEmptyLayer();
339
340  /*  outputs form the first layer */
341  Ntk_NetworkForEachCombOutput(network, listGen, nodePtr) {
342    if (st_lookup_int(fanoutCountTable, (char *)nodePtr, &fanoutCount)) {
343      /* insert all outputs that aren't to be ignored in the first layer of the
344       * layer array
345       */
346      LayerAddNodeAtEnd(currentLayer, nodePtr);
347    }
348  }
349
350  /* if current layer is not empty */
351  while (ResLayerNumNodes(currentLayer) ) {
352    /* insert current layer into layer array */
353    array_insert_last(array_t *, layerArray, currentLayer);
354    nextLayer = LayerCreateEmptyLayer();
355    LayerForEachNode(currentLayer, i, nodePtr) {
356      Ntk_NodeForEachFanin(nodePtr, j, faninNodePtr) {
357        /* do not want to get the fanin for latch outputs */
358        if(!(Ntk_NodeTestIsConstant(nodePtr) ||
359             (Ntk_NodeTestIsLatch(nodePtr) &&
360             (Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
361              Ntk_NodeTestIsLatchInitialInput(faninNodePtr))))) {
362          if (!st_lookup_int(fanoutCountTable, (char *)faninNodePtr,
363                             &fanoutCount)) {
364            /* maybe it is a PI or constant node */
365            if (!(Ntk_NodeTestIsCombInput(faninNodePtr) ||
366                  Ntk_NodeTestIsConstant(faninNodePtr) ||
367                  Ntk_NodeTestIsUndefined(faninNodePtr) ||
368                  Ntk_NodeTestIsShadow(faninNodePtr))) {
369              error_append("Fanin node %s should have been in table");
370              error_append(Ntk_NodeReadName(faninNodePtr));
371              /* Cleanup */
372              arrayForEachItem(array_t *, layerArray, k, currentLayer) {
373                LayerFree(currentLayer);
374              }
375              array_free(layerArray);
376              return NIL(array_t);
377            } /* node is neither PI nor constant */
378          } else { /* node is found in table */
379            fanoutCount--;
380            /* decrement fanout count, will go into a later layer */
381            if (fanoutCount == 0) {
382              /*
383               * it is ready to be put in the array,
384               * since its fanout count is 1
385               */
386              LayerAddNodeAtEnd(nextLayer, faninNodePtr);
387            } else if (fanoutCount > 0) {
388                /* insert new decremented value in table */
389              st_insert(fanoutCountTable, (char *)faninNodePtr,
390                        (char *)(long)fanoutCount);
391
392            } /* end of nodes fanout count larger than 1 */
393          } /* end of fanin node found in fanout count table */
394        } /* do not want to get the fanin for latch outputs */
395      } /* end of iteration through all the fanin nodes of current node */
396    } /* end of iteration through all the nodes of current layer */
397    /* the fanout count ensures unique entry of elements ????*/
398    currentLayer = nextLayer;
399  } /* end of while some nodes in current layer */ 
400 
401  /* the loop always exits with an empty array */
402  LayerFree(currentLayer);
403  st_free_table(fanoutCountTable);
404  if (array_n(layerArray) == 0) {
405    array_free(layerArray);
406    layerArray = NIL(array_t);
407  }
408
409  return (layerArray);
410 
411} /* End of ComputeCompositionLayersAsap */
412
413/**Function**********************************************************************
414
415  Synopsis [ Computes the layers of nodes of the network based on the "as late
416  as possible" heuristic.]
417
418  Description [ Computes the layers of nodes of the network based on the "as
419  late as possible" heuristic. When composing an Add with nodes starting from
420  the primary outputs, to the primary inputs, several nodes in the network are
421  candidates for composition simultaneously producing what we decided to call
422  "layers". This procedure schedules the composition of the nodes as late as
423  possible under the "One-Time Rule" restriction. The One-Time Rule states that
424  a node may be composed into the ADD only when all its fanouts have been
425  composed in. This procedure schedules the composition of the nodes as "late"
426  as possible i.e. only when no further composition can be done without
427  composing the node in question. The order of composition is computed by
428  labeling every node with its maximum distance from the primary inputs. The
429  nodes are then scheduled starting with those with the larger depth and
430  descending until reaching the inputs. Note that with this heuristic we still
431  guarantee that every node appears in one single layer, therefore, it is only
432  composed once. This is not "strictly as late as possible" as the symmetric
433  opposite of the as soon as possible technique. But this scheduling has the
434  additional win of taking advantage of the varying depths of the different
435  paths in the circuit and scheduling the nodes evenly. The procedure takes as
436  arguments the network whose layers are required, the outputs to be considered
437  and the outputs to be ignored.]
438
439  SideEffects []
440
441  SeeAlso            [ResComputeCompositionLayers ComputeCompositionLayersAsap]
442
443  ******************************************************************************/
444static array_t *
445ComputeCompositionLayersAlap(Ntk_Network_t *network,
446                             array_t *outputArray, 
447                             array_t *ignoreArray)
448{
449  Ntk_Node_t *nodePtr;       /* node being processed  */
450  array_t *layerArray;       /* array of layers */
451  array_t *currentLayer;     /* layer of nodes */
452  st_table *nodeLabelling;   /* labeling of a node, its farthest distance
453                              * from the primary input
454                              */
455  int numLayers;             /* Number of Layers */
456  int layerIndex;            /* index of a layer (from the primary output */
457  int arrayIndex;            /* iterator */
458  st_generator *stGen;       /* generator to step through table */
459  char *key;                 /* values to read from table */
460  int value;                 /* integer value to read from the table */
461
462  /* Initialize the labeling table */
463  nodeLabelling = ComputeTransitiveFanin(outputArray);
464
465  /* Compute the labeling of the nodes */
466  numLayers = ComputeAlapLabelling(network, nodeLabelling);
467
468  /* Create the layerArray structure */
469  layerArray = array_alloc(array_t *, numLayers);
470  /* initialize layers */
471  for (layerIndex = 0; layerIndex < numLayers; layerIndex++) {
472    currentLayer = LayerCreateEmptyLayer();
473    array_insert(array_t *, layerArray, layerIndex, currentLayer);
474  } /* end of for */
475
476  /* insert elements of the st_table in the layers */
477  st_foreach_item_int(nodeLabelling, stGen, &key, &value) {
478    layerIndex = value;
479    nodePtr = (Ntk_Node_t *)key;
480    /* don't put PIs or comb inputs or constants or undefined
481     * nodes in layer array
482     */
483    if ((Ntk_NodeTestIsCombOutput(nodePtr)) ||
484        ((layerIndex > 0) &&
485         !(Ntk_NodeTestIsCombInput(nodePtr) ||
486           Ntk_NodeTestIsConstant(nodePtr) ||
487           Ntk_NodeTestIsUndefined(nodePtr) ||
488           Ntk_NodeTestIsShadow(nodePtr)))) {
489      /* the layers are arranged in reverse order of their farthest
490       * distance from the node. Hence each node is inserted into
491       * the numLayers-1-layerIndex. Nodes with layerIndex should be
492       * put in the last array since they are probably constants
493       * at the primary outputs or latch initial value. LayerIndex
494       * could be 0 for primary outputs if it does not appear in the
495       * transitive fanin of the comb inputs.
496       */
497      if (layerIndex == 0) {
498        arrayIndex = 0;
499        assert(Ntk_NodeTestIsCombOutput(nodePtr) == 1);
500      } else {
501        arrayIndex = numLayers - layerIndex;
502      }
503      currentLayer = array_fetch(array_t *, layerArray, arrayIndex);
504      LayerAddNodeAtEnd(currentLayer, nodePtr);
505    }
506  }
507  /* Clean up */
508  st_free_table(nodeLabelling);
509
510 
511  return layerArray;
512} /* End of ComputeCompositionLayersAlap */
513
514
515/**Function*********************************************************************
516
517  Synopsis [ Procedure to label each node with its maximum distance from the
518  primary inputs.]
519
520  Description [The procedure processes iteratively every input. For each of
521  them, it labels recursively its transitive output keeping always the larger
522  depth value. The procedure accepts as arguments the network that need to be
523  labeled and a table with the labeling of nodes to be filled) and returns the
524  maximum layer size.]
525
526  SideEffects        [It modifies the st_table passed as parameter.]
527
528  SeeAlso [ComputeCompositionLayersAlap ComputeAlapLabellingRecur]
529
530  ******************************************************************************/
531static int
532ComputeAlapLabelling(Ntk_Network_t *network, 
533                     st_table *nodeLabelling)
534{
535  Ntk_Node_t *nodePtr; /* Node being processed */
536  lsGen gen;           /* For list traversal */
537  int numLayers;       /* To return as result */
538  int outputDepth;     /* Depth of the output being processed */
539
540  assert(nodeLabelling != NIL(st_table));
541
542  /* For primary inputs in the table (those not in the table
543   * are in the transitive fanin of the ignored outputs only
544   */
545  Ntk_NetworkForEachCombInput(network, gen, nodePtr) {
546    /* do it for fanouts that are in table only */
547    if (st_is_member(nodeLabelling, (char *)nodePtr)) {
548      ComputeAlapLabellingRecur(nodePtr, nodeLabelling);
549    }
550  }
551
552  /* Compute the number of layers */
553  numLayers = 0;
554  Ntk_NetworkForEachCombOutput(network, gen, nodePtr) {
555    /* only those outputs not be to be ignored */
556    if (st_lookup_int(nodeLabelling, (char *)nodePtr, &outputDepth)) {
557      if (outputDepth > numLayers ) {
558        numLayers = outputDepth;
559      } /* End of if */
560    }
561  }
562 
563  return numLayers;
564} /* End of ComputeAlapLabelling */
565
566/**Function*********************************************************************
567
568  Synopsis [Recursive procedure to label every node with its maximum depth
569  from the primary inputs.]
570
571  Description [It labels every node with the current depth and
572  proceeds recursively through the fanouts. The procedure accepts as
573  its arguments the node it is currently recurring on and the table
574  with labeling of the nodes(max distance from the PIs) which gets
575  updated.]
576
577  SideEffects        [It modifies the st_table passed as parameter]
578
579  SeeAlso            [ComputeAlapLabelling]
580
581  ******************************************************************************/
582static void
583ComputeAlapLabellingRecur(Ntk_Node_t *node,
584                          st_table *nodeLabelling)
585{
586  Ntk_Node_t *fanoutPtr;
587  int nodeDepth;
588  int fanoutDepth;
589  int i;
590
591  /* Trivial case */
592  if (Ntk_NodeReadNumFanouts(node) == 0) {
593    return;
594  } /* End of if */
595
596  /* Look up information for the current node */
597  st_lookup_int(nodeLabelling, (char *)node, &nodeDepth);
598 
599  /* Iterate over its fanouts */
600  Ntk_NodeForEachFanout(node, i, fanoutPtr) {
601    /* Do not process as soon as an input is found beyond an output */
602    if (!((Ntk_NodeTestIsLatchDataInput(node) ||
603           Ntk_NodeTestIsLatchInitialInput(node)) &&
604          Ntk_NodeTestIsLatch(fanoutPtr))) {
605      if (st_is_member(nodeLabelling, (char *)fanoutPtr)) {
606        /* Look up information for the fanout */
607        st_lookup_int(nodeLabelling, (char *)fanoutPtr, &fanoutDepth);
608        /* If the fanout depth needs to be modified, do so, and recur */
609        if (nodeDepth >= fanoutDepth) {
610          st_insert(nodeLabelling, (char *)fanoutPtr, 
611                    (char *)(long)(nodeDepth + 1));
612          ComputeAlapLabellingRecur(fanoutPtr, nodeLabelling);
613        } /* End of if */
614      } /* End of if */
615    } /* End of if */
616  } /* End of for each fanout */
617
618  return;
619} /* End of ComputeAlapLabellingRecur */
620
621
622/**Function*********************************************************************
623
624  Synopsis    [Procedure that computes the transitive fanin of a set
625  of nodes in an array.]
626
627  Description [[Procedure that computes the transitive fanin of a set
628  of nodes in an array. The procedure puts the nodes themselves into the
629  array too.The procedure takes as arguments the array whose transitive
630  fanin need to be computed and returns an st_table with the fanin.]
631 
632  SideEffects []
633
634  SeeAlso     [ComputeCompositionLayersAlap ComputeTransitiveFaninRecur]
635
636  *****************************************************************************/
637static st_table *
638ComputeTransitiveFanin(array_t *outputArray)
639{
640  Ntk_Node_t *nodePtr;
641  st_table * faninTable;
642  int i;
643 
644  faninTable = st_init_table(st_ptrcmp, st_ptrhash);
645  arrayForEachItem(Ntk_Node_t *, outputArray, i, nodePtr) {
646    ComputeTransitiveFaninRecur(nodePtr, faninTable);
647  }
648  return faninTable;
649} /* End of ComputeTransitiveFanin */
650
651/**Function*********************************************************************
652
653  Synopsis    [Recursive procedure to compute the transitive fanin of
654  a node.]
655 
656  Description [ Recursive procedure to compute the transitive fanin of a
657  node. After computing the transitive fanin, the node itself goes into the
658  table. The procedure takes in as arguments the node it is recurring on and
659  the table of fanin encountered.]
660 
661  SideEffects []
662
663  SeeAlso     [ComputeTransitiveFanin]
664
665  *****************************************************************************/
666static void
667ComputeTransitiveFaninRecur(Ntk_Node_t *nodePtr, 
668                            st_table *faninTable)
669{
670  Ntk_Node_t *faninNodePtr;
671  int i;
672
673  if (st_lookup(faninTable, (char *)nodePtr, NIL(char *))) {
674    return;
675  }
676
677
678  /* recur on fanin nodes */
679  Ntk_NodeForEachFanin(nodePtr, i, faninNodePtr) {
680    /* Test this case cos other comb inputs have no fanins */
681    if (!((Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
682           Ntk_NodeTestIsLatchInitialInput(faninNodePtr)) &&
683          Ntk_NodeTestIsLatch(nodePtr))) {
684      ComputeTransitiveFaninRecur(faninNodePtr, faninTable);
685    } /* end of if */
686  } /* iterate over all fanins */
687 
688  st_insert(faninTable, (char *)nodePtr, NIL(char));
689  return;
690
691} /* End of ComputeTransitiveFaninRecur */
692
693/**Function*********************************************************************
694
695  Synopsis    [Function to decrement fanout count]
696 
697  Description [Recursive procedure that reduces the fanout count of the
698  current node and recurs on its fanin. Stops when Pis or constant nodes are
699  hit which have no fanins. The procedure takes in as arguments the current it
700  is recurring on and the table with nodes and their fanout counts.]
701 
702  SideEffects []
703
704  SeeAlso     [ComputeCompositionLayersAsap]
705
706  *****************************************************************************/
707static void
708RecursiveDecrementFanoutCount(Ntk_Node_t *nodePtr, 
709                              st_table *fanoutCountTable,
710                              st_table *visitedTable)
711{
712  Ntk_Node_t *faninNodePtr;
713  int i, fanoutCount;
714
715  /* the following kinds of nodes will not be in the table. */
716  if ((!Ntk_NodeTestIsCombOutput(nodePtr)) && 
717       (Ntk_NodeTestIsCombInput(nodePtr) ||
718        Ntk_NodeTestIsUndefined(nodePtr)||
719        Ntk_NodeTestIsConstant(nodePtr) ||
720        Ntk_NodeTestIsShadow(nodePtr))) {
721    return;
722  }
723  /* all nodes called here should exist in table */
724  if (!st_lookup_int(fanoutCountTable, (char *)nodePtr, &fanoutCount)){
725    error_append("Node ");
726    error_append(Ntk_NodeReadName(nodePtr));
727    error_append(" should have been in table\n");
728    return;
729  }
730
731  fanoutCount--;
732  /* reduce fanout count of node */
733  st_insert(fanoutCountTable, (char *)nodePtr, (char *)(long)fanoutCount);
734  /* if this node is visited, decrement its fanout but do not proceed
735   * any further (i.e. do not proceed with its fanins
736   */
737  if (st_is_member(visitedTable, (char *)nodePtr)) {
738    return;
739  } else {
740    st_insert(visitedTable, (char *)nodePtr, NIL(char));
741
742    /*
743     * recur with fanin nodes except nodes with no fanins (that arent in table)
744     * and latch outputs
745     */
746    Ntk_NodeForEachFanin(nodePtr, i, faninNodePtr) {
747      /* may be a redundant test, since it will pop out in the first line of
748       * the procedure anyways.
749       */
750      if (!(Ntk_NodeTestIsConstant(faninNodePtr) ||
751          ((Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
752            Ntk_NodeTestIsLatchInitialInput(faninNodePtr)) &&
753           Ntk_NodeTestIsLatch(nodePtr)))) {
754        RecursiveDecrementFanoutCount(faninNodePtr, fanoutCountTable, visitedTable);
755      } 
756    } /* end of iterating over fanins */
757  } /* end of else if not visited */
758  return;
759} /* End of RecursiveDecrementFanoutCount */
Note: See TracBrowser for help on using the repository browser.