#include "partInt.h"
Include dependency graph for partCollapse.c:
Go to the source code of this file.
Functions | |
| static Mvf_Function_t * | CollapseRecur (graph_t *partition, vertex_t *vertexPtr, st_table *tableOfLeaves, mdd_t *careSet, st_table *alreadyComputed) |
| array_t * | Part_PartitionBuildFunctions (graph_t *partition, array_t *roots, array_t *leaves, mdd_t *careSet) |
| array_t * | Part_PartitionCollapse (graph_t *partition, array_t *roots, st_table *leaves, mdd_t *careSet) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: partCollapse.c,v 1.5 2005/04/16 06:14:54 fabio Exp $" |
Function Documentation
| static Mvf_Function_t * CollapseRecur | ( | graph_t * | partition, |
| vertex_t * | vertexPtr, | ||
| st_table * | tableOfLeaves, | ||
| mdd_t * | careSet, | ||
| st_table * | alreadyComputed | ||
| ) | [static] |
AutomaticStart
Function********************************************************************
Synopsis [Executes the recursive step of the collapsing procedure.]
Description [Given a node, recursively collapses its fanins and then composes the result to obtain the new function. The result is the function after substituting the variables are represented by functions in terms of the leaves.]
SideEffects []
SeeAlso [Part_PartitionCollapse]
Definition at line 230 of file partCollapse.c.
{
Mvf_Function_t *result; /* Array to return the result */
Mvf_Function_t *preresult; /* Result before careSet minimization */
Mvf_Function_t *vertexFn; /* Mvf attached to vertexPtr */
array_t *faninMddIds; /* Ids of every vertex of the fanin */
array_t *faninMvfs; /* Array of functions obtained for the fanins */
Mvf_Function_t *faninResult; /* Function obtained for one fanin */
edge_t *edgePtr; /* Fanin edge*/
lsGen gen; /* List generator used for iteration */
int i;
/* Look up in the alreadyComputedTable */
if (st_lookup(alreadyComputed, vertexPtr, &result) == 1) {
return result;
} /* End of if */
/*
* Initialize the arrays needed to call the function
* Mvf_FunctionComposeWithFunctionArray
*/
faninMddIds = array_alloc(int, 0);
faninMvfs = array_alloc(Mvf_Function_t *, 0);
/* Obtain results for each fanin */
i=0;
foreach_in_edge(vertexPtr, gen, edgePtr) {
vertex_t *fromVertex = g_e_source(edgePtr);
/* Skip the fanins that are leaves */
if (!st_is_member(tableOfLeaves, (char *)fromVertex) ) {
/* Compute the array recursively */
faninResult = CollapseRecur(partition, fromVertex, tableOfLeaves, careSet,
alreadyComputed);
array_insert(int, faninMddIds, i, PartVertexReadMddId(fromVertex));
array_insert(Mvf_Function_t *, faninMvfs, i, faninResult);
i++;
} /* End of if */
}
/*
* Compose the obtained fanin functions as variables in the
* vertexPtr's function. If all the fanins are leaves, the function
* Mvf_FunctionComposeWithFunctionArray returns a duplicate of the
* array which is needed to be stored in the alreadyComputed table.
*/
vertexFn = PartVertexReadFunction(vertexPtr);
preresult = Mvf_FunctionComposeWithFunctionArray(vertexFn,
faninMddIds,
faninMvfs);
/* Minimize the result with respect to the given care set */
if (careSet != NIL(mdd_t)) {
result = Mvf_FunctionMinimize(preresult, careSet);
Mvf_FunctionFree(preresult);
}
else {
result = preresult;
}
array_free(faninMddIds);
/*
* There is no need to delete the mdds stored in this array since
* they are stored in the alreadyComputed table.
*/
array_free(faninMvfs);
/* Insert the result in the already-obtained results */
st_insert(alreadyComputed, (char *)vertexPtr, (char *)result);
return result;
} /* End of CollapseRecur */
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* Part_PartitionBuildFunctions | ( | graph_t * | partition, |
| array_t * | roots, | ||
| array_t * | leaves, | ||
| mdd_t * | careSet | ||
| ) |
AutomaticEnd Function********************************************************************
Synopsis [Create Mdd Arrays given leaves and roots.]
Description [Given an array of vertex names as roots and an array of mddIds as leaves, obtain the Mvf_Function_t of the root vertices in terms of the mddIds given as leaves. This function just creates the proper parameters to later call Part_PartitionCollapse.]
SideEffects []
SeeAlso [Part_PartitionCollapse]
Definition at line 82 of file partCollapse.c.
{
st_table *leavesTable; /* To pass to Part_PartitionCollapse */
array_t *rootVertexArray; /* To pass to Part_PartitionCollapse */
array_t *result; /* Array of Arrays of mdd_t * */
int i;
/* Create the table of leaves */
leavesTable = st_init_table(st_ptrcmp, st_ptrhash);
for(i = 0; i < array_n(leaves); i++) {
int varId = array_fetch(int, leaves, i);
vertex_t *vertexPtr;
/* turned off the check below since it is done later in the */
/* function SimTestPartInTermsOfCI */
/* Make sure the leaves have a valid mddId */
/* assert(varId != NTK_UNASSIGNED_MDD_ID); */
vertexPtr = Part_PartitionFindVertexByMddId(partition, varId);
if (vertexPtr != NIL(vertex_t)) {
st_insert(leavesTable, (char *)vertexPtr, NIL(char));
} /* End of if */
} /* End of for */
/* Create array of roots */
rootVertexArray = array_alloc(vertex_t *, array_n(roots));
for(i = 0; i < array_n(roots); i++) {
char *vertexName = array_fetch(char *, roots, i);
vertex_t *vertexPtr = Part_PartitionFindVertexByName(partition,
vertexName);
/* Make sure the vertex is member of the partition */
assert(vertexPtr != NIL(vertex_t));
array_insert(vertex_t *, rootVertexArray, i, vertexPtr);
} /* End of for */
/* Effectively build the functions */
result = Part_PartitionCollapse(partition, rootVertexArray,
leavesTable, careSet);
/* Clean up */
array_free(rootVertexArray);
st_free_table(leavesTable);
return result;
} /* End of Part_PartitionBuildFunctions */
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* Part_PartitionCollapse | ( | graph_t * | partition, |
| array_t * | roots, | ||
| st_table * | leaves, | ||
| mdd_t * | careSet | ||
| ) |
Function********************************************************************
Synopsis [Computes root functions in terms of leaf variables.]
Description [The partition is a DAG. Given an array of vertices (vertex_t*) called roots and a table of vertices (vertex_t*) called leaves, obtains one Mvf_Function_t for every root in terms of the variables attached to the leaf vertices. Returns the array of Mvf_Function_t*, in one-to-correspondence with the roots.]
SideEffects []
Definition at line 148 of file partCollapse.c.
{
int i;
st_table *vertexCache; /* Store already processed vertices */
st_generator *stGen; /* To iterate over st_table */
vertex_t *vertexPtr; /* Pointer to vertex being processed */
array_t *result; /* Mvf_Function_ts for the roots */
Mvf_Function_t *collapsedFunction;
/* Array holding the result */
result = array_alloc(Mvf_Function_t *, array_n(roots));
/* Table to store the already computed vertices */
vertexCache = st_init_table(st_ptrcmp, st_ptrhash);
/* iterate over the given roots */
arrayForEachItem(vertex_t *, roots, i, vertexPtr) {
/* No cluster vertices are allowed in the roots specification */
if (PartVertexReadType(vertexPtr) == Part_VertexCluster_c) {
(void) fprintf(vis_stderr, "Warning -- Ignoring cluster vertices in");
(void) fprintf(vis_stderr, " PartitionCollapse\n");
} /* End of if */
else {
Mvf_Function_t *functionLookUp;
if (st_lookup(vertexCache, vertexPtr, &functionLookUp) == 1) {
collapsedFunction = Mvf_FunctionDuplicate(functionLookUp);
}
else {
collapsedFunction = CollapseRecur(partition, vertexPtr,
leaves, careSet, vertexCache);
}
/* Store the function in the result array */
array_insert(Mvf_Function_t *, result, i, collapsedFunction);
}
} /* End of arrayForEachItem */
/*
* Save the root nodes from deletion and save their mdds from
* deallocation.
*/
arrayForEachItem(vertex_t *, roots, i, vertexPtr) {
st_delete(vertexCache, &vertexPtr, NULL);
}
/* Delete the intermediate results produced in the computation */
st_foreach_item(vertexCache, stGen, &vertexPtr, &collapsedFunction) {
Mvf_FunctionFree(collapsedFunction);
}
st_free_table(vertexCache);
return result;
} /* End of Part_PartitionCollapse */
Here is the call graph for this function:
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: partCollapse.c,v 1.5 2005/04/16 06:14:54 fabio Exp $" [static] |
CFile***********************************************************************
FileName [partCollapse.c]
PackageName [part]
Synopsis [Implements a procedure to collapse several internal vertices of a partition into a single one.]
Description [Given a partition, a set of root vertices and a set of leaf vertices, obtain the array_t of Mvf_Function_t * representing the functions at the root vertices in terms of the variables at the leaf vertices.]
Author [Abelardo Pardo]
Copyright [This file was created at the University of Colorado at Boulder. The University of Colorado at Boulder makes no warranty about the suitability of this software for any purpose. It is presented on an AS IS basis.]
Definition at line 25 of file partCollapse.c.
