src/part/partInOut.c

Go to the documentation of this file.

#include "partInt.h"

static char rcsid[] UNUSED = "$Id: partInOut.c,v 1.15 2005/04/16 14:52:45 fabio Exp $";

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


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

graph_t *
Part_CreatePartitionFromMvfs(
  mdd_manager *manager,                      
  st_table *nameToMvf,
  st_table *nameToId,
  st_table *leafTable,
  char *partName)
{
    graph_t        *partition;
    Mvf_Function_t *mddFunction;
    vertex_t       *toVertex;
    lsList         sinkList;
    lsGen          gen;
    st_table       *mddIdToNodeName;
    st_generator   *stGen;
    char           *str;
    long            mddId;

    /* Initialize variables */
    mddIdToNodeName = leafTable;

    /* Allocate the new partition to be returned */
    partition = g_alloc();
    if (partName) {
        partition->user_data = 
            (gGeneric)PartPartitionInfoCreate(partName,manager,Part_InOut_c);
    } /* End of if */
    else {
        partition->user_data = 
            (gGeneric)PartPartitionInfoCreate("dummy",manager,Part_InOut_c);
    } /* End of if-then-else */

    /* Create vertices for the functions in nameToMvf */
    st_foreach_item(nameToMvf,stGen,&str,&mddFunction) {
        toVertex = g_add_vertex(partition);

        /* Update the look-up tables in the graph */
        st_insert(PartPartitionReadNameToVertex(partition),str,toVertex);
        if (nameToId) {
            if (st_lookup(nameToId, str, &mddId)) {
                st_insert(PartPartitionReadMddIdToVertex(partition),
                          (char *)mddId, toVertex);
            } /* End of if */
        } /* End of if */

        /* Fill in the fields of the data attached to the vertex */
        toVertex->user_data = 
            (gGeneric)PartVertexInfoCreateSingle(str, 
                                            Mvf_FunctionDuplicate(mddFunction),
                                            mddId);
    }
  
    /* Read the list of vertices on the graph */
    sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);

    /* 
     * For every function on every combinational output, compute the
     * support and create vertices in the graph when needed 
     */
    lsForEachItem(sinkList, gen, toVertex) {
        st_table *mddSupport; /* Support of the Mvf_Function */
        st_generator *stGen;  /* To iterate over the MddIds of the support */
        vertex_t *fromVertex; /* Holds the current vertex in the support */

        /* Obtain an array of mdd_t * */
        mddFunction = PartVertexReadFunction(toVertex);

        /* Compute the support of the set of mdds*/
        mddSupport = PartCreateFunctionSupportTable(mddFunction);

        /* 
         * Create one edge (and one vertex if necessary) for every element
         * in mddSupport 
         */
        st_foreach_item(mddSupport, stGen, &mddId, NULL) {
            char *name;

            /* Create vertex with the information if needed */
            if (st_lookup(PartPartitionReadMddIdToVertex(partition), 
                          (char *)mddId, &fromVertex) == 0) {
                fromVertex = g_add_vertex(partition);
        
                st_lookup(mddIdToNodeName, (char *)mddId, &name);

                /* Update the look-up tables in the graph */
                st_insert(PartPartitionReadNameToVertex(partition), 
                          name, (char *)fromVertex);
                st_insert(PartPartitionReadMddIdToVertex(partition),
                          (char *)(long) mddId, (char *)fromVertex);
        
                /* Create vertex data */
                fromVertex->user_data = 
                    (gGeneric)PartVertexInfoCreateSingle(name,
                              Mvf_FunctionCreateFromVariable(manager,mddId),
                                                         mddId);
            } /* End of if */
      
            /* 
             * Add the edge to the graph. Make sure a self loop is not added.
             * The self loop may be produced by a mdd that has in its support
             * the same variables that represent the mddId of the node.
             */
            if (fromVertex != toVertex) {
                g_add_edge(fromVertex, toVertex);
            } /* End of if */
            
        } /* End of st_foreach_item */
    
        /* Clean the support table */
        st_free_table(mddSupport);
    } /* End of lsForEachItem */

    lsDestroy(sinkList, (void (*)(lsGeneric))0);

    return partition;
} /* End of Part_CreatePartitionFromMvfs */

graph_t *
Part_NetworkCreatePartitionFromMvfs(
  Ntk_Network_t *network,
  st_table *nameToMvf)
{
    graph_t        *partition;
    Ntk_Node_t     *node;
    Mvf_Function_t *mddFunction;
    vertex_t       *toVertex;
    mdd_manager    *manager;
    lsList         sinkList;
    lsGen          gen;
    st_table       *mddIdToNodeName;
    st_generator   *stGen;
    char           *ntkName;
    char           *str;
    long           mddId;

    /* Initialize variables */
    manager = Ntk_NetworkReadMddManager(network);
    ntkName = Ntk_NetworkReadName(network);

    /* Allocate the new partition to be returned */
    partition = g_alloc();
    partition->user_data = 
        (gGeneric)PartPartitionInfoCreate(ntkName,manager,Part_InOut_c);

    /* Create vertices for the functions in nameToMvf */
    st_foreach_item(nameToMvf,stGen,&str,&mddFunction) {
        node = Ntk_NetworkFindNodeByName(network,str);
        if (node == NIL(Ntk_Node_t)) {
            fprintf(vis_stderr,"%s has no corresponding node in network \n",
                    str);
            Part_PartitionFree(partition);
            return NIL(graph_t);
        }
        mddId = Ntk_NodeReadMddId(node);
        toVertex = g_add_vertex(partition);

        /* Update the look-up tables in the graph */
        st_insert(PartPartitionReadNameToVertex(partition),str,
                  (char *)toVertex);

        if (mddId != NTK_UNASSIGNED_MDD_ID) {
            st_insert(PartPartitionReadMddIdToVertex(partition),
                      (char *)(long) mddId, (char *)toVertex);
        }

        /* Fill in the fields of the data attached to the vertex */
        toVertex->user_data = 
            (gGeneric)PartVertexInfoCreateSingle(str, 
                                            Mvf_FunctionDuplicate(mddFunction),
                                            mddId);
    }

    /* Create a table for all the combinational inputs */
    mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
    Ntk_NetworkForEachCombInput(network, gen, node) {
        st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
                  Ntk_NodeReadName(node));
    }
  
    /* Read the list of vertices on the graph */
    sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);

    /* 
     * For every function on every combinational output, compute the
     * support and create vertices in the graph when needed 
     */
    lsForEachItem(sinkList, gen, toVertex) {
        st_table *mddSupport; /* Support of the Mvf_Function */
        st_generator *stGen;  /* To iterate over the MddIds of the support */
        vertex_t *fromVertex; /* Holds the current vertex in the support */

        /* Obtain an array of mdd_t * */
        mddFunction = PartVertexReadFunction(toVertex);

        /* Compute the support of the set of mdds*/
        mddSupport = PartCreateFunctionSupportTable(mddFunction);

        /* 
         * Create one edge (and one vertex if necessary) for every element
         * in mddSupport 
         */
        st_foreach_item(mddSupport, stGen, &mddId, NULL) {
            char *name;

            /* Create vertex with the information if needed */
            if (st_lookup(PartPartitionReadMddIdToVertex(partition), 
                          (char *)mddId, &fromVertex) == 0) {
                fromVertex = g_add_vertex(partition);
        
                st_lookup(mddIdToNodeName, (char *)mddId, &name);

                /* Update the look-up tables in the graph */
                st_insert(PartPartitionReadNameToVertex(partition), 
                          name, (char *)fromVertex);
                st_insert(PartPartitionReadMddIdToVertex(partition),
                          (char *)(long) mddId, (char *)fromVertex);
        
                /* Create vertex data */
                fromVertex->user_data = 
                    (gGeneric)PartVertexInfoCreateSingle(name,
                              Mvf_FunctionCreateFromVariable(manager,mddId),
                                                         mddId);
            } /* End of if */
      
            /* 
             * Add the edge to the graph. Make sure a self loop is not added.
             * The self loop may be produced by a mdd that has in its support
             * the same variables that represent the mddId of the node.
             */
            if (fromVertex != toVertex) {
                g_add_edge(fromVertex, toVertex);
            } /* End of if */
            
        } /* End of st_foreach_item */
    
        /* Clean the support table */
        st_free_table(mddSupport);
    } /* End of lsForEachItem */

    st_free_table(mddIdToNodeName);
    lsDestroy(sinkList, (void (*)(lsGeneric))0);

    return partition;
} /* End of Part_NetworkCreatePartitionFromMvfs */

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

void
PartPartitionInputsOutputs(
  Ntk_Network_t *network,
  graph_t *partition,
  lsList  rootList,
  lsList  leaveList,
  mdd_t   *careSet)
{
  Ntk_Node_t     *node;            /* Pointer to iterate over nodes */
  Mvf_Function_t *mddFunction;     /* Pointer to a MDD */
  mdd_manager    *manager;         /* Mdd manager in the partition */
  st_table       *tableOfLeaves;   /* To store the leaves of the graph */
  st_table       *mddIdToNodeName; /* For quick lookup of node's name */
  array_t        *arrayOfMvf;      /* To store the next state functions */
  array_t        *arrayOfRoots;    /* To store the roots of the graph */
  lsList         sinkList;         /* Vertices representing comb. outputs */
  lsGen          gen;              /* To iterate over lists */
  vertex_t       *toVertex;        /* Will hold the current function vertex */
  int            i;                /* Index for loops */
  long            mddId;            /* Will hold the mddId being processed */


  manager = PartPartitionReadMddManager(partition);

  /* Take the nodes in leaveList as the leaves */
  tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
  mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
  if (leaveList == (lsList)0) {
    Ntk_NetworkForEachCombInput(network, gen, node) {
      st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
      st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
                Ntk_NodeReadName(node));
    }
  } /* End of then */ 
  else {
    lsForEachItem(leaveList, gen, node) {
      st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
      st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
                Ntk_NodeReadName(node));
    }
  } /* End of if-then-else */

  /* Take the nodes in rootList as the roots */
  if (rootList == (lsList)0) {
    arrayOfRoots = array_alloc(Ntk_Node_t *, 
                               Ntk_NetworkReadNumCombOutputs(network));
    i = 0;
    Ntk_NetworkForEachCombOutput(network, gen, node) {
      array_insert(Ntk_Node_t *, arrayOfRoots, i++, node);
    }
  } /* End of then */ 
  else {
    arrayOfRoots = array_alloc(Ntk_Node_t *, lsLength(rootList));
    i = 0;
    lsForEachItem(rootList, gen, node) {
      array_insert(Ntk_Node_t *, arrayOfRoots, i++, node);
    }
  } /* End of if-then-else */

  /* Build the next state functions as a function of the inputs */
  arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves, 
                                    careSet);

  /* Create one vertex for every component of arrayOfMvf */
  for (i=0; i < array_n(arrayOfRoots); i++) {
    node = array_fetch(Ntk_Node_t *, arrayOfRoots, i);
    
    mddId = Ntk_NodeReadMddId(node);

    /* obtain the function attached to the node */
    mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i);
    toVertex = g_add_vertex(partition);
    
    /* Update the look-up tables in the graph */
    st_insert(PartPartitionReadNameToVertex(partition),
              Ntk_NodeReadName(node), (char *)toVertex);
    if (mddId != NTK_UNASSIGNED_MDD_ID) {
      st_insert(PartPartitionReadMddIdToVertex(partition),
                (char *)(long) mddId, (char *)toVertex);
    } /* End of if */
    toVertex->user_data = 
      (gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node), 
                                           mddFunction, 
                                           mddId);
  } /* End of for */
  
  /* Read the list of vertices on the graph */
  sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);

  /* 
   * For every function on every combinational output, compute the
   * support and create vertices in the graph when needed 
   */
  lsForEachItem(sinkList, gen, toVertex) {
    st_table     *mddSupport; /* To store the support of the Mvf_Function */
    st_generator *stGen;      /* To iterate over the MddIds of the support */
    vertex_t     *fromVertex; /* Will hold the current vertex in the support */

    /* Obtain an array of mdd_t * */
    mddFunction = PartVertexReadFunction(toVertex);

    /* Compute the support of the set of mdds*/
    mddSupport = PartCreateFunctionSupportTable(mddFunction);

    /* 
     * Create one edge (and one vertex if necessary) for every element
     * in mddSupport 
     */
    st_foreach_item(mddSupport, stGen, &mddId, NULL) {
      char *name;

      /* Create vertex with the information if needed */
      if (st_lookup(PartPartitionReadMddIdToVertex(partition), 
                    (char *)mddId, &fromVertex) == 0) {
        fromVertex = g_add_vertex(partition);
        
        st_lookup(mddIdToNodeName, (char *)mddId, &name);

        /* Update the look-up tables in the graph */
        st_insert(PartPartitionReadNameToVertex(partition), 
                  name, (char *)fromVertex);
        st_insert(PartPartitionReadMddIdToVertex(partition),
                  (char *)(long) mddId, (char *)fromVertex);
        
        /* Create vertex data */
        fromVertex->user_data = 
          (gGeneric)PartVertexInfoCreateSingle(name,
                                               Mvf_FunctionCreateFromVariable(manager,mddId),
                                               mddId);
      } /* End of if */
      
      /* 
       * Add the edge to the graph. Make sure a self loop is not added. The
       * self loop may be produced by a mdd that has in its support the same
       * variables that represent the mddId of the node.
       */
      if (fromVertex != toVertex) {
        g_add_edge(fromVertex, toVertex);
      } /* End of if */
      
    } /* End of st_foreach_item */
    
    /* Clean the support table */
    st_free_table(mddSupport);
  } /* End of lsForEachItem */
  
  /* Clean up */
  st_free_table(mddIdToNodeName);
  st_free_table(tableOfLeaves);
  array_free(arrayOfRoots);
  lsDestroy(sinkList, (void (*)(lsGeneric))0);
  /* 
   * The contents of this array (array of mdds) is not deallocated because the
   * information has been transferred to the partition structure. All the
   * functions are stored now as part of the vertex information.
   */
  array_free(arrayOfMvf);
  
} /* End of PartPartitionInputsOutputs */


int
PartPartitionInOutChangeRoots(
  Ntk_Network_t *network,
  graph_t *partition,
  lsList  rootList,
  int verbosity)
{
  Ntk_Node_t     *node;            /* Pointer to iterate over nodes */
  mdd_manager    *manager;         /* Mdd manager in the partition */
  lsList         newRootList;
  lsList         vertexList;
  lsGen          gen;              /* To iterate over lists */
  vertex_t       *vertex;
  char           *vertexName;
  long           initialTime, finalTime;
  st_table       *rootNodesTable = st_init_table(st_ptrcmp, st_ptrhash);
  mdd_t          *careSet;

  int prevNumOfLatchDataInput = 0;
  int prevNumOfPrimaryOutput = 0;
  int newNumOfLatchDataInput = 0;
  int newNumOfPrimaryOutput = 0;
  int overlapNumOfLatchDataInput = 0;
  int overlapNumOfPrimaryOutPut = 0;

  initialTime = util_cpu_time();

  manager = PartPartitionReadMddManager(partition);
  vertexList = g_get_vertices(partition);

  lsForEachItem(vertexList, gen, vertex){
    vertexName = PartVertexReadName(vertex);
    node = Ntk_NetworkFindNodeByName(network, vertexName);
    if (Ntk_NodeTestIsCombOutput(node)){
      st_insert(rootNodesTable, (char *)node, (char *)(long)(-1));
      if (Ntk_NodeTestIsLatchDataInput(node)){
        prevNumOfLatchDataInput++;
      }else if (Ntk_NodeTestIsPrimaryOutput(node)){
        prevNumOfPrimaryOutput++;
      }
    }
  }

  newRootList = lsCreate();
  lsForEachItem(rootList, gen, node){
    if (!(st_is_member(rootNodesTable, (char *)node))){
      lsNewEnd(newRootList, (lsGeneric)node, LS_NH);
      if (Ntk_NodeTestIsLatchDataInput(node)){
        newNumOfLatchDataInput++;
      }else if (Ntk_NodeTestIsPrimaryOutput(node)){
        newNumOfPrimaryOutput++;
      }
    }else{
      if (Ntk_NodeTestIsLatchDataInput(node)){
        overlapNumOfLatchDataInput++;
      }else if (Ntk_NodeTestIsPrimaryOutput(node)){
        overlapNumOfPrimaryOutPut++;
      }
    }
  }

  st_free_table(rootNodesTable);

  if (lsLength(newRootList) > 0){
    careSet = mdd_one(manager);
    PartPartitionInputsOutputs(network, partition, newRootList, 
                               (lsList)0, careSet);
    mdd_free(careSet);
  }

  lsDestroy(newRootList, (void (*)(lsGeneric))0);

  finalTime = util_cpu_time();

  if (verbosity >= 2){
    fprintf(vis_stdout, "PART: Partition is changed.\n");
    fprintf(vis_stdout, "PART: Old - %d next state functions\n",
            prevNumOfLatchDataInput);
    fprintf(vis_stdout, "PART: Old - %d primary outputs\n",
            prevNumOfPrimaryOutput);
    fprintf(vis_stdout, "PART: New - %d next state functions\n",
            prevNumOfLatchDataInput + newNumOfLatchDataInput);
    fprintf(vis_stdout, "PART: New - %d primary outputs\n",
            prevNumOfPrimaryOutput + newNumOfPrimaryOutput);
    fprintf(vis_stdout, "PART: Partitioning time = %10ld\n",
                    (finalTime - initialTime) / 1000);
    Part_PartitionPrintStats(vis_stdout, partition, FALSE);
  }

  /*
   * Is partition increased?
   */
  if (newNumOfLatchDataInput + newNumOfPrimaryOutput > 0){
    return 1;
  }else{
    return 0;
  } 
} /* End of PartPartitionInOutChangeRoots */

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