source: vis_dev/vis-2.3/src/part/partCollapse.c @ 50

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

vis2.3
File size: 11.2 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [partCollapse.c]
4
5  PackageName [part]
6
7  Synopsis [Implements a procedure to collapse several internal vertices of a
8  partition into a single one.]
9
10  Description [Given a partition, a set of root vertices and a set of leaf
11  vertices, obtain the array_t of Mvf_Function_t * representing the functions
12  at the root vertices in terms of the variables at the leaf vertices.]
13
14  Author      [Abelardo Pardo]
15
16  Copyright   [This file was created at the University of Colorado at
17  Boulder.  The University of Colorado at Boulder makes no warranty
18  about the suitability of this software for any purpose.  It is
19  presented on an AS IS basis.]
20
21******************************************************************************/
22
23#include "partInt.h"
24
25static char rcsid[] UNUSED = "$Id: partCollapse.c,v 1.5 2005/04/16 06:14:54 fabio Exp $";
26
27/*---------------------------------------------------------------------------*/
28/* Constant declarations                                                     */
29/*---------------------------------------------------------------------------*/
30
31
32/*---------------------------------------------------------------------------*/
33/* Structure declarations                                                    */
34/*---------------------------------------------------------------------------*/
35
36
37/*---------------------------------------------------------------------------*/
38/* Type declarations                                                         */
39/*---------------------------------------------------------------------------*/
40
41
42/*---------------------------------------------------------------------------*/
43/* Variable declarations                                                     */
44/*---------------------------------------------------------------------------*/
45
46
47/*---------------------------------------------------------------------------*/
48/* Macro declarations                                                        */
49/*---------------------------------------------------------------------------*/
50
51
52/**AutomaticStart*************************************************************/
53
54/*---------------------------------------------------------------------------*/
55/* Static function prototypes                                                */
56/*---------------------------------------------------------------------------*/
57
58static Mvf_Function_t * CollapseRecur(graph_t *partition, vertex_t *vertexPtr, st_table *tableOfLeaves, mdd_t *careSet, st_table *alreadyComputed);
59
60/**AutomaticEnd***************************************************************/
61
62
63/*---------------------------------------------------------------------------*/
64/* Definition of exported functions                                          */
65/*---------------------------------------------------------------------------*/
66
67/**Function********************************************************************
68
69  Synopsis    [Create Mdd Arrays given leaves and roots.]
70
71  Description [Given an array of vertex names as roots and an array of
72  mddIds as leaves, obtain the Mvf_Function_t of the root vertices in terms
73  of the mddIds given as leaves. This function just creates the proper
74  parameters to later call Part_PartitionCollapse.]
75
76  SideEffects []
77
78  SeeAlso     [Part_PartitionCollapse]
79
80******************************************************************************/
81array_t *
82Part_PartitionBuildFunctions(
83  graph_t *partition,
84  array_t *roots,
85  array_t *leaves,
86  mdd_t *careSet)
87{
88  st_table *leavesTable;      /* To pass to Part_PartitionCollapse */
89  array_t  *rootVertexArray;  /* To pass to Part_PartitionCollapse */
90  array_t  *result;           /* Array of Arrays of mdd_t * */
91  int      i;
92
93  /* Create the table of leaves */
94  leavesTable = st_init_table(st_ptrcmp, st_ptrhash);
95  for(i = 0; i < array_n(leaves); i++) {
96    int varId = array_fetch(int, leaves, i);
97    vertex_t *vertexPtr;
98
99    /* turned off the check below since it is done later in the */
100    /* function SimTestPartInTermsOfCI                          */
101    /* Make sure the leaves have a valid mddId */
102/*    assert(varId != NTK_UNASSIGNED_MDD_ID); */
103   
104    vertexPtr = Part_PartitionFindVertexByMddId(partition, varId);
105    if (vertexPtr != NIL(vertex_t)) {
106      st_insert(leavesTable, (char *)vertexPtr, NIL(char));
107    } /* End of if */
108  } /* End of for */
109
110  /* Create array of roots */
111  rootVertexArray = array_alloc(vertex_t *, array_n(roots));
112  for(i = 0; i < array_n(roots); i++) {
113    char *vertexName = array_fetch(char *, roots, i);
114    vertex_t *vertexPtr = Part_PartitionFindVertexByName(partition, 
115                                                         vertexName);
116   
117    /* Make sure the vertex is member of the partition */
118    assert(vertexPtr != NIL(vertex_t));
119
120    array_insert(vertex_t *, rootVertexArray, i, vertexPtr);
121  } /* End of for */
122
123  /* Effectively build the functions */
124  result = Part_PartitionCollapse(partition, rootVertexArray,
125                                  leavesTable, careSet);
126
127  /* Clean up */
128  array_free(rootVertexArray);
129  st_free_table(leavesTable);
130
131  return result;
132} /* End of Part_PartitionBuildFunctions */
133
134/**Function********************************************************************
135
136  Synopsis    [Computes root functions in terms of leaf variables.]
137
138  Description [The partition is a DAG. Given an array of vertices (vertex_t*)
139  called roots and a table of vertices (vertex_t*) called leaves, obtains one
140  Mvf_Function_t for every root in terms of the variables attached to the leaf
141  vertices.  Returns the array of Mvf_Function_t*, in one-to-correspondence
142  with the roots.]
143
144  SideEffects []
145
146******************************************************************************/
147array_t *
148Part_PartitionCollapse(
149  graph_t *partition,
150  array_t *roots,
151  st_table *leaves,
152  mdd_t *careSet)
153{
154  int            i;
155  st_table       *vertexCache;          /* Store already processed vertices */
156  st_generator   *stGen;                /* To iterate over st_table */
157  vertex_t       *vertexPtr;            /* Pointer to vertex being processed */
158  array_t        *result;               /* Mvf_Function_ts for the roots */ 
159  Mvf_Function_t *collapsedFunction;
160
161  /* Array holding the result */
162  result = array_alloc(Mvf_Function_t *, array_n(roots));
163 
164  /* Table to store the already computed vertices */
165  vertexCache = st_init_table(st_ptrcmp, st_ptrhash);
166
167  /* iterate over the given roots */
168  arrayForEachItem(vertex_t *, roots, i, vertexPtr) {
169    /* No cluster vertices are allowed in the roots specification */
170    if (PartVertexReadType(vertexPtr) == Part_VertexCluster_c) {
171      (void) fprintf(vis_stderr, "Warning -- Ignoring cluster vertices in");
172      (void) fprintf(vis_stderr, " PartitionCollapse\n");
173    } /* End of if */
174    else {
175      Mvf_Function_t *functionLookUp;
176
177      if (st_lookup(vertexCache, vertexPtr, &functionLookUp) == 1) {
178        collapsedFunction = Mvf_FunctionDuplicate(functionLookUp);
179      }
180      else {
181        collapsedFunction = CollapseRecur(partition, vertexPtr, 
182                                          leaves, careSet, vertexCache);
183      }
184      /* Store the function in the result array */
185      array_insert(Mvf_Function_t *, result, i, collapsedFunction);
186    }
187  } /* End of arrayForEachItem */
188 
189  /*
190   * Save the root nodes from deletion and save their mdds from
191   * deallocation.
192   */
193  arrayForEachItem(vertex_t *, roots, i, vertexPtr) {
194    st_delete(vertexCache, &vertexPtr, NULL);
195  }
196
197  /* Delete the intermediate results produced in the computation */
198  st_foreach_item(vertexCache, stGen, &vertexPtr, &collapsedFunction) {
199    Mvf_FunctionFree(collapsedFunction);
200  }
201  st_free_table(vertexCache);
202
203  return result;
204} /* End of Part_PartitionCollapse */
205
206/*---------------------------------------------------------------------------*/
207/* Definition of internal functions                                          */
208/*---------------------------------------------------------------------------*/
209
210
211/*---------------------------------------------------------------------------*/
212/* Definition of static functions                                            */
213/*---------------------------------------------------------------------------*/
214
215/**Function********************************************************************
216
217  Synopsis    [Executes the recursive step of the collapsing procedure.]
218
219  Description [Given a node, recursively collapses its fanins and then
220  composes the result to obtain the new function. The result is the
221  function after substituting the variables are represented by
222  functions in terms of the leaves.]
223
224  SideEffects []
225
226  SeeAlso     [Part_PartitionCollapse]
227
228******************************************************************************/
229static Mvf_Function_t *
230CollapseRecur(
231  graph_t *partition,
232  vertex_t *vertexPtr,
233  st_table *tableOfLeaves,
234  mdd_t *careSet,
235  st_table *alreadyComputed)
236{
237  Mvf_Function_t *result;      /* Array to return the result */
238  Mvf_Function_t *preresult;   /* Result before careSet minimization */
239  Mvf_Function_t *vertexFn;    /* Mvf attached to vertexPtr */
240  array_t        *faninMddIds; /* Ids of every vertex of the fanin */
241  array_t        *faninMvfs;   /* Array of functions obtained for the fanins */
242  Mvf_Function_t *faninResult; /* Function obtained for one fanin */
243  edge_t         *edgePtr;     /* Fanin edge*/
244  lsGen          gen;          /* List generator used for iteration */
245  int            i;
246   
247  /* Look up in the alreadyComputedTable */
248  if (st_lookup(alreadyComputed, vertexPtr, &result) == 1) {
249    return result;
250  } /* End of if */
251
252  /*
253   * Initialize the arrays needed to call the function
254   * Mvf_FunctionComposeWithFunctionArray
255   */
256  faninMddIds = array_alloc(int, 0);
257  faninMvfs = array_alloc(Mvf_Function_t *, 0);
258
259  /* Obtain results for each fanin */
260  i=0;
261  foreach_in_edge(vertexPtr, gen, edgePtr) {
262    vertex_t *fromVertex = g_e_source(edgePtr);
263
264    /* Skip the fanins that are leaves */
265    if (!st_is_member(tableOfLeaves, (char *)fromVertex) ) {
266      /* Compute the array recursively */
267      faninResult = CollapseRecur(partition, fromVertex, tableOfLeaves, careSet,
268                                  alreadyComputed);
269      array_insert(int, faninMddIds, i, PartVertexReadMddId(fromVertex));
270      array_insert(Mvf_Function_t *, faninMvfs, i, faninResult);
271      i++;
272    } /* End of if */
273  }
274
275  /*
276   * Compose the obtained fanin functions as variables in the
277   * vertexPtr's function. If all the fanins are leaves, the function
278   * Mvf_FunctionComposeWithFunctionArray returns a duplicate of the
279   * array which is needed to be stored in the alreadyComputed table.
280   */
281  vertexFn = PartVertexReadFunction(vertexPtr);
282  preresult = Mvf_FunctionComposeWithFunctionArray(vertexFn, 
283                                                faninMddIds,
284                                                faninMvfs);
285  /* Minimize the result with respect to the given care set */
286  if (careSet != NIL(mdd_t)) {
287    result = Mvf_FunctionMinimize(preresult, careSet);
288    Mvf_FunctionFree(preresult);
289  } 
290  else {
291    result = preresult;
292  }
293 
294  array_free(faninMddIds);
295  /*
296   * There is no need to delete the mdds stored in this array since
297   * they are stored in the alreadyComputed table.
298   */
299  array_free(faninMvfs);
300
301  /* Insert the result in the already-obtained results */
302  st_insert(alreadyComputed, (char *)vertexPtr, (char *)result);
303
304  return result;
305} /* End of CollapseRecur */
306
307
308
309
310
311
312
Note: See TracBrowser for help on using the repository browser.