source: vis_dev/vis-2.3/src/spfd/spfdReg.c @ 57

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

vis2.3
File size: 7.7 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [spfdReg.c]
4
5  PackageName [spfd]
6
7  Synopsis [Routines to compute a cluster of nodes for optimization.]
8
9  Description [Routines to compute a cluster of nodes for optimization.]
10
11  SeeAlso     [spfdOpt.c]
12
13  Author      [Balakrishna Kumthekar]
14
15  Copyright [This file was created at the University of Colorado at Boulder.
16  The University of Colorado at Boulder makes no warranty about the suitability
17  of this software for any purpose.  It is presented on an AS IS basis.]
18
19******************************************************************************/
20
21#include "spfdInt.h"
22
23/*---------------------------------------------------------------------------*/
24/* Constant declarations                                                     */
25/*---------------------------------------------------------------------------*/
26
27/*---------------------------------------------------------------------------*/
28/* Type declarations                                                         */
29/*---------------------------------------------------------------------------*/
30
31
32/*---------------------------------------------------------------------------*/
33/* Structure declarations                                                    */
34/*---------------------------------------------------------------------------*/
35
36
37/*---------------------------------------------------------------------------*/
38/* Variable declarations                                                     */
39/*---------------------------------------------------------------------------*/
40
41
42/*---------------------------------------------------------------------------*/
43/* Macro declarations                                                        */
44/*---------------------------------------------------------------------------*/
45
46
47/**AutomaticStart*************************************************************/
48
49/*---------------------------------------------------------------------------*/
50/* Static function prototypes                                                */
51/*---------------------------------------------------------------------------*/
52
53
54/**AutomaticEnd***************************************************************/
55
56
57/*---------------------------------------------------------------------------*/
58/* Definition of exported functions                                          */
59/*---------------------------------------------------------------------------*/
60
61
62/*---------------------------------------------------------------------------*/
63/* Definition of internal functions                                          */
64/*---------------------------------------------------------------------------*/
65/**Function********************************************************************
66
67  Synopsis [Find a cluster of nodes that are within regionDepth of
68  startNode.]
69
70  SideEffects        [None]
71
72******************************************************************************/
73array_t *
74SpfdNodeComputeFanoutRegion(
75  SpfdApplData_t *applData,
76  Ntk_Node_t *startNode,
77  int regionDepth)
78{
79  Ntk_Node_t *fanout,*ntkNode;
80  st_table *reached;
81  st_generator *stGen;
82  array_t *regionArray,*from,*new_;
83  int bound,i,j,k;
84
85  reached = st_init_table(st_ptrcmp,st_ptrhash);
86  if (Ntk_NodeTestIsPrimaryOutput(startNode)) {
87    st_insert(reached,(char *)startNode,(char *)1);
88  } else {
89    /* Sort the fanout array of startNode according to depth */
90    from = array_dup(Ntk_NodeReadFanouts(startNode));
91    array_sort(from,SpfdDepthCompare);
92    /* Put fanoutArray into reached */
93    arrayForEachItem(Ntk_Node_t *,from,i,fanout) {
94      if (!Ntk_NodeTestIsPrimaryOutput(fanout)) {
95        bound = 0;
96      } else {
97        bound = 1;
98      }
99      st_insert(reached,(char *)fanout,(char *)(long)bound);
100    }
101
102    /* Proceed for depth regionDepth */
103    for (i = 0; i < regionDepth; i++) {
104      new_ = array_alloc(Ntk_Node_t *,0);
105      arrayForEachItem(Ntk_Node_t *,from,j,ntkNode) {
106        st_lookup(reached,(char *)ntkNode,&bound);
107        if (!bound) {
108          Ntk_NodeForEachFanout(ntkNode,k,fanout) {
109            if (!st_lookup(reached,(char *)fanout,&bound)) {
110              if (Ntk_NodeTestIsPrimaryOutput(fanout) ||
111                  Ntk_NodeReadNumFanouts(fanout) < 1 || /* Just to be safe */
112                  i == regionDepth - 1) {
113                bound = 1;
114              } else {
115                bound = 0;
116              }
117              st_insert(reached,(char *)fanout,(char *)(long)bound);
118              array_insert_last(Ntk_Node_t *,new_,fanout);
119            }
120          }
121        }
122      }
123      array_free(from);
124      from = new_;
125      array_sort(from,SpfdDepthCompare);
126    }
127    array_free(from);
128 
129    /* Finally make the startNode an internal node */
130    st_insert(reached,(char *)startNode,(char *)0);
131  } 
132
133  /* Put the nodes in reached according to their depth */
134  regionArray = array_alloc(Ntk_Node_t *,0);
135  st_foreach_item_int(reached,stGen,&fanout,&bound) {
136    array_insert_last(Ntk_Node_t *,regionArray,fanout);
137  }
138  array_sort(regionArray,SpfdDepthCompare);
139
140  if (applData->currRegionNodes) {
141    (void) fprintf(vis_stdout,
142                   "** spfd warning: Possible memory leak.\n");
143  }
144  applData->currRegionNodes = reached;
145 
146  return regionArray;
147 
148} /* End of SpfdNodeComputeFanoutRegion */
149
150
151/**Function********************************************************************
152
153  Synopsis [The returned array contains the nodes in TFI of startNode,
154  except the immediate fanin of startNode.]
155
156  SideEffects        [None]
157
158******************************************************************************/
159array_t *
160SpfdNodeComputeTFIUntilDepth(
161  Ntk_Node_t *startNode,
162  int regionDepth)
163{
164  Ntk_Node_t *fanin,*ntkNode;
165  st_table *reached,*faninTable;
166  st_generator *stGen;
167  array_t *regionArray,*from,*new_;
168  char *dummy;
169  int i,j,k;
170
171  /* Make sure that startNode is not a PI to start with. */
172
173  if (Ntk_NodeTestIsPrimaryInput(startNode))
174    return NIL(array_t);
175
176  reached = st_init_table(st_ptrcmp,st_ptrhash);
177  faninTable = st_init_table(st_ptrcmp,st_ptrhash);
178 
179  /* Put the fanin array of startNode in faninTable */
180  from = array_dup(Ntk_NodeReadFanins(startNode));
181  arrayForEachItem(Ntk_Node_t *,from,i,ntkNode) {
182    st_insert(faninTable,(char *)ntkNode,(char *)1);
183  }
184
185  /* Proceed for depth regionDepth */
186  for (i = 0; i < regionDepth; i++) {
187    new_ = array_alloc(Ntk_Node_t *,0);
188    arrayForEachItem(Ntk_Node_t *,from,j,ntkNode) {
189      Ntk_NodeForEachFanin(ntkNode,k,fanin) {
190        if (!st_lookup(reached,(char *)fanin,&dummy) &&
191            !st_lookup(faninTable,(char *)fanin,&dummy)) {
192          st_insert(reached,(char *)fanin,(char *)1);
193          array_insert_last(Ntk_Node_t *,new_,fanin);
194        }
195      }
196    }
197    array_free(from);
198    from = new_;
199  }
200  array_free(from);
201  st_free_table(faninTable);
202 
203  /* Put the nodes in reached according to their depth */
204  regionArray = array_alloc(Ntk_Node_t *,0);
205  st_foreach_item(reached,stGen,&ntkNode,&dummy) {
206    array_insert_last(Ntk_Node_t *,regionArray,ntkNode);
207  }
208  array_sort(regionArray,SpfdDepthCompare);
209
210  st_free_table(reached);
211  return regionArray;
212 
213} /* End of SpfdNodeComputeTFIUntilDepth */
214
215
216/**Function********************************************************************
217
218  Synopsis [Returns in tfoNodes, the nodes in the transitive fanout of
219  node.]
220
221  SideEffects        [None]
222
223******************************************************************************/
224void
225SpfdNodesInTFO(
226  Ntk_Network_t *network,
227  Ntk_Node_t *node,
228  st_table *tfoNodes)
229{
230  int i;
231  Ntk_Node_t *fanout;
232 
233  st_insert(tfoNodes,(char *)node,(char *)0);
234  Ntk_NodeForEachFanout(node,i,fanout) {
235    SpfdNodesInTFO(network,fanout,tfoNodes);
236  }
237
238  return;
239} /* End of SpfdNodesInTFO */
240
241
242/*---------------------------------------------------------------------------*/
243/* Definition of static functions                                            */
244/*---------------------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.