src/part/partCollapse.c

Go to the documentation of this file.

#include "partInt.h"

static char rcsid[] UNUSED = "$Id: partCollapse.c,v 1.5 2005/04/16 06:14:54 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static Mvf_Function_t * CollapseRecur(graph_t *partition, vertex_t *vertexPtr, st_table *tableOfLeaves, mdd_t *careSet, st_table *alreadyComputed);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

array_t *
Part_PartitionBuildFunctions(
  graph_t *partition,
  array_t *roots,
  array_t *leaves,
  mdd_t *careSet)
{
  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 */

array_t *
Part_PartitionCollapse(
  graph_t *partition,
  array_t *roots,
  st_table *leaves,
  mdd_t *careSet)
{
  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 */

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

static Mvf_Function_t *
CollapseRecur(
  graph_t *partition,
  vertex_t *vertexPtr,
  st_table *tableOfLeaves,
  mdd_t *careSet,
  st_table *alreadyComputed)
{
  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 */