d5/d95/partPartial_8c_source.html

00001
00027 #include "partInt.h"
00028
00029 static char rcsid[] UNUSED = "$Id: partPartial.c,v 1.10 2005/04/16 14:52:45 fabio Exp $";
00030
00031 /*---------------------------------------------------------------------------*/
00032 /* Constant declarations                                                     */
00033 /*---------------------------------------------------------------------------*/
00034
00035
00036 /*---------------------------------------------------------------------------*/
00037 /* Structure declarations                                                    */
00038 /*---------------------------------------------------------------------------*/
00039
00040
00041 /*---------------------------------------------------------------------------*/
00042 /* Type declarations                                                         */
00043 /*---------------------------------------------------------------------------*/
00044
00045
00046 /*---------------------------------------------------------------------------*/
00047 /* Variable declarations                                                     */
00048 /*---------------------------------------------------------------------------*/
00049
00050
00051 /*---------------------------------------------------------------------------*/
00052 /* Macro declarations                                                        */
00053 /*---------------------------------------------------------------------------*/
00054
00055
00058 /*---------------------------------------------------------------------------*/
00059 /* Static function prototypes                                                */
00060 /*---------------------------------------------------------------------------*/
00061
00062
00066 /*---------------------------------------------------------------------------*/
00067 /* Definition of exported functions                                          */
00068 /*---------------------------------------------------------------------------*/
00069
00070
00071 /*---------------------------------------------------------------------------*/
00072 /* Definition of internal functions                                          */
00073 /*---------------------------------------------------------------------------*/
00074
00075
00086 void
00087 PartPartitionPartial(
00088   Ntk_Network_t *network,
00089   graph_t       *partition,
00090   lsList        rootList,
00091   lsList        leaveList,
00092   mdd_t         *careSet,
00093   lsList        nodeList,
00094   int           inTermsOfCombInputs)
00095 {
00096   Ntk_Node_t     *node;            /* Pointer to iterate over nodes */
00097   Mvf_Function_t *mddFunction;     /* Pointer to a MDD */
00098   mdd_manager    *manager;         /* Mdd manager in the partition */
00099   st_table       *tableOfLeaves;   /* To store the leaves of the graph */
00100   st_table       *mddIdToNodeName; /* For quick lookup of node's name */
00101   array_t        *arrayOfMvf;      /* To store the next state functions */
00102   array_t        *arrayOfRoots;    /* To store the roots of the graph */
00103   lsList         sinkList;         /* Vertices representing comb. outputs */
00104   lsGen          gen;              /* To iterate over lists */
00105   vertex_t       *toVertex;        /* Will hold the current function vertex */
00106   int            i;                /* Index for loops */
00107   long           mddId;            /* Will hold the mddId being processed */
00108   st_table       *mddSupport;      /* To store the support of the Mvf_Function */
00109   st_generator   *stGen;           /* To iterate over the MddIds of the support */
00110   vertex_t       *fromVertex;      /* Will hold the current vertex in the support */
00111   char           *nodeName;
00112   array_t        *singletonMvfArray;
00113   array_t        *singletonArrayOfRoots;
00114   array_t        *tmpArrayOfMvf;
00115   Mvf_Function_t *nodeMvf;
00116   lsList         sortedListOfNodes;
00117   array_t        *sortedArrayOfPartitionNodes;
00118   array_t        *unsortedArrayOfPartitionNodes;
00119   st_table       *tableOfPartitionNodes;
00120   array_t        *validNodeArray;
00121   array_t        *invalidNodeArray;
00122   int            chars_printed;
00123
00124   assert(rootList == (lsList)0);
00125   assert(leaveList == (lsList)0);
00126   manager = PartPartitionReadMddManager(partition);
00127   invalidNodeArray = array_alloc(char *, 0);
00128   validNodeArray = array_alloc(char *, 0);
00129
00130   /* check that nodes in nodeList are valid ones */
00131   lsForEachItem(nodeList, gen, nodeName){
00132     node = Ntk_NetworkFindNodeByName(network, nodeName);
00133     if(node == NIL(Ntk_Node_t)){
00134       array_insert_last(char *, invalidNodeArray, nodeName);
00135     }
00136     else{
00137       array_insert_last(char *, validNodeArray, nodeName);
00138     }
00139   }
00140   if(array_n(invalidNodeArray) > 0){
00141     fprintf(stdout, "The following node(s) are being ignored in the partition:\n");
00142     chars_printed = 0;
00143     for(i = 0; i < array_n(invalidNodeArray); i++){
00144       fprintf(stdout, "%s ", array_fetch(char *, invalidNodeArray, i));
00145       chars_printed += strlen(array_fetch(char *, invalidNodeArray, i));
00146       if(chars_printed >60){
00147         chars_printed = 0;
00148         fprintf(stdout, "\n");
00149       }
00150     }
00151     fprintf(stdout, "\nThey are either invalid names or have been swept away at \n");
00152     fprintf(stdout, "the end of the flatten_network command. Use <flatten_network -s> \n");
00153     fprintf(stdout, "to avoid performing a sweep after the flatten command, \n");
00154   }
00155   array_free(invalidNodeArray);
00156
00157
00158   /* Make the combinational input  nodes into leaves */
00159   tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
00160   mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
00161   Ntk_NetworkForEachCombInput(network, gen, node) {
00162     st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
00163     st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
00164               Ntk_NodeReadName(node));
00165   }
00166
00167   /* create temporary array and table of partition nodes */
00168   unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);
00169   tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash);
00170   for(i = 0; i < array_n(validNodeArray); i++){
00171     nodeName = array_fetch(char *, validNodeArray, i);
00172     node = Ntk_NetworkFindNodeByName(network, nodeName);
00173     assert(!Ntk_NodeTestIsShadow(node));
00174     /* make sure that the node is not a CI or CO */
00175     if(!Ntk_NodeTestIsCombInput(node) && !Ntk_NodeTestIsCombOutput(node)){
00176       array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node);
00177       st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1));
00178     }
00179   }
00180   array_free(validNodeArray);
00181
00182   /* create sorted array of partition nodes */
00183   sortedListOfNodes = Ntk_NetworkComputeTopologicalOrder(network, unsortedArrayOfPartitionNodes, tableOfLeaves);
00184   sortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);
00185   lsForEachItem(sortedListOfNodes, gen, node){
00186     /* sortedListOfNodes includes many internal nodes, need to filter them out */
00187     if(st_is_member(tableOfPartitionNodes, (char *) node)){
00188       array_insert_last(Ntk_Node_t *, sortedArrayOfPartitionNodes, node);
00189     }
00190   }
00191   array_free(unsortedArrayOfPartitionNodes);
00192   lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0);
00193   st_free_table(tableOfPartitionNodes);
00194
00195
00196   /* Create mvfs for nodes in sortedArrayOfPartitionNodes */
00197   tmpArrayOfMvf = array_alloc(Mvf_Function_t *, 0);
00198   for(i=0; i < array_n(sortedArrayOfPartitionNodes); i++){
00199     node = array_fetch(Ntk_Node_t *, sortedArrayOfPartitionNodes, i);
00200     singletonArrayOfRoots = array_alloc(Ntk_Node_t *, 0);
00201     array_insert_last(Ntk_Node_t *, singletonArrayOfRoots, node);
00202     singletonMvfArray = Ntm_NetworkBuildMvfs(network, singletonArrayOfRoots,
00203                                              tableOfLeaves, careSet);
00204     nodeMvf = array_fetch(Mvf_Function_t *, singletonMvfArray, 0);
00205     array_insert_last(Mvf_Function_t *, tmpArrayOfMvf, nodeMvf);
00206     array_free(singletonMvfArray);
00207     array_free(singletonArrayOfRoots);
00208
00209     /* now create an mddId for this node, and make it a leaf */
00210     if(inTermsOfCombInputs == 0){
00211       if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID){
00212         Ord_NetworkAssignMddIdForNode(network, node);
00213       }
00214       st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
00215       st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
00216                 Ntk_NodeReadName(node));
00217     }
00218   }
00219
00220   /* Make the combinational output nodes into roots */
00221   arrayOfRoots = array_alloc(Ntk_Node_t *, 0);
00222   Ntk_NetworkForEachCombOutput(network, gen, node) {
00223     array_insert_last(Ntk_Node_t *, arrayOfRoots, node);
00224   }
00225
00226   /* build mvfs of nodes in arrayOfMvf in terms of partition nodes and comb inputs */
00227   arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves,
00228                                     careSet);
00229   array_append(arrayOfRoots, sortedArrayOfPartitionNodes);
00230   array_append(arrayOfMvf, tmpArrayOfMvf);
00231   array_free(sortedArrayOfPartitionNodes);
00232   array_free(tmpArrayOfMvf);
00233
00234   /* Create one vertex for every component of arrayOfMvf */
00235   for (i=0; i < array_n(arrayOfRoots); i++) {
00236     node = array_fetch(Ntk_Node_t *, arrayOfRoots, i);
00237     mddId = (long) Ntk_NodeReadMddId(node);
00238
00239     /* obtain the function attached to the node */
00240     mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i);
00241     toVertex = g_add_vertex(partition);
00242
00243     /* Update the look-up tables in the graph */
00244     st_insert(PartPartitionReadNameToVertex(partition),
00245               Ntk_NodeReadName(node), (char *)toVertex);
00246     if (mddId != -1) {
00247       st_insert(PartPartitionReadMddIdToVertex(partition),
00248                 (char *)mddId, (char *)toVertex);
00249     }
00250     toVertex->user_data =
00251       (gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node),
00252                                            mddFunction,
00253                                            (int) mddId);
00254   }
00255
00256   /* Read the list of vertices on the graph */
00257   sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);
00258
00259   /*
00260    * For every function on every combinational output, compute the
00261    * support and create vertices in the graph when needed
00262    */
00263   lsForEachItem(sinkList, gen, toVertex) {
00264     mddFunction = PartVertexReadFunction(toVertex);
00265     mddSupport = PartCreateFunctionSupportTable(mddFunction);
00266
00267     /*
00268      * Create one edge (and one vertex if necessary) for every element
00269      * in mddSupport
00270      */
00271     st_foreach_item(mddSupport, stGen, &mddId, NULL) {
00272       char *name;
00273
00274       /* Create vertex with the information if needed */
00275       if (st_lookup(PartPartitionReadMddIdToVertex(partition),
00276                     (char *)mddId, &fromVertex) == 0) {
00277         fromVertex = g_add_vertex(partition);
00278
00279         st_lookup(mddIdToNodeName, (char *)mddId, &name);
00280
00281         /* Update the look-up tables in the graph */
00282         st_insert(PartPartitionReadNameToVertex(partition),
00283                   name, (char *)fromVertex);
00284         st_insert(PartPartitionReadMddIdToVertex(partition),
00285                   (char *) mddId, (char *)fromVertex);
00286
00287         /* Create vertex data */
00288         fromVertex->user_data =
00289           (gGeneric)PartVertexInfoCreateSingle(name,
00290                                                Mvf_FunctionCreateFromVariable(manager, (int) mddId),
00291                                                (int) mddId);
00292       }
00293
00294       /*
00295        * Add the edge to the graph. Make sure a self loop is not added. The
00296        * self loop may be produced by a mdd that has in its support the same
00297        * variables that represent the mddId of the node.
00298        */
00299       if (fromVertex != toVertex) {
00300         g_add_edge(fromVertex, toVertex);
00301       } /* End of if */
00302
00303     } /* End of st_foreach_item */
00304
00305     /* Clean the support table */
00306     st_free_table(mddSupport);
00307   } /* End of lsForEachItem */
00308
00309   /* Clean up */
00310   st_free_table(mddIdToNodeName);
00311   st_free_table(tableOfLeaves);
00312   array_free(arrayOfRoots);
00313   lsDestroy(sinkList, (void (*)(lsGeneric))0);
00314   /*
00315    * The contents of this array (array of mdds) is not deallocated because the
00316    * information has been transferred to the partition structure. All the
00317    * functions are stored now as part of the vertex information.
00318    */
00319   array_free(arrayOfMvf);
00320
00321 } /* End of PartPartitionPartial */
00322
00323 /*---------------------------------------------------------------------------*/
00324 /* Definition of static functions                                            */
00325 /*---------------------------------------------------------------------------*/