VIS
|
00001 00023 #include "spfdInt.h" 00024 00025 /*---------------------------------------------------------------------------*/ 00026 /* Constant declarations */ 00027 /*---------------------------------------------------------------------------*/ 00028 00029 00030 /*---------------------------------------------------------------------------*/ 00031 /* Type declarations */ 00032 /*---------------------------------------------------------------------------*/ 00033 00034 00035 /*---------------------------------------------------------------------------*/ 00036 /* Structure declarations */ 00037 /*---------------------------------------------------------------------------*/ 00038 00039 /*---------------------------------------------------------------------------*/ 00040 /* Variable declarations */ 00041 /*---------------------------------------------------------------------------*/ 00042 00043 /*---------------------------------------------------------------------------*/ 00044 /* Macro declarations */ 00045 /*---------------------------------------------------------------------------*/ 00046 00047 00050 /*---------------------------------------------------------------------------*/ 00051 /* Static function prototypes */ 00052 /*---------------------------------------------------------------------------*/ 00053 00054 static Tbl_Table_t * BuildNewTable(Ntk_Network_t *network, Ntk_Node_t *ntkNode, mdd_t *mddFunc); 00055 static void TableAddCube(Tbl_Table_t *table, array_t *faninIdArray, array_t *cube, int value); 00056 00060 /*---------------------------------------------------------------------------*/ 00061 /* Definition of exported functions */ 00062 /*---------------------------------------------------------------------------*/ 00063 00064 00065 /*---------------------------------------------------------------------------*/ 00066 /* Definition of internal functions */ 00067 /*---------------------------------------------------------------------------*/ 00080 void 00081 SpfdReprogramRegionNodes( 00082 Ntk_Network_t *network, 00083 SpfdApplData_t *applData, 00084 array_t *regionArray) 00085 { 00086 st_table *nodeCountTable,*sinkTable; 00087 st_table *regionNodes = applData->currRegionNodes; 00088 st_table *currBddReq = applData->currBddReq; 00089 st_table *wireTable = applData->currWireTable; 00090 st_table *replaceTable = applData->currReplaceTable; 00091 bdd_manager *ddManager = applData->ddManager; 00092 Ntk_Node_t *fanout,*regNode,*fanin,*newFanin; 00093 bdd_node *bdd1,*localAlt,*globalAlt; 00094 bdd_node *ddTemp,*relNew,*relOld,*encRel; 00095 bdd_node *xCube; 00096 char *dummy; 00097 st_generator *stGen; 00098 int bound,i,j,k,piSwap; 00099 int *count; 00100 array_t *faninBdds,*faninNodes,*nodeArray; 00101 00102 /* Cube of primary inputs. */ 00103 xCube = applData->currXCube; 00104 /* Analyze the region to find out how many times the 00105 alternative/global function of an individual region node will be 00106 used. This count will be used to remove those functions when no 00107 longer needed, hence avoid memory peaks. */ 00108 nodeCountTable = st_init_table(st_ptrcmp,st_ptrhash); 00109 st_foreach_item(currBddReq,stGen,®Node,&bdd1) { 00110 count = ALLOC(int,1); 00111 *count = 0; 00112 Ntk_NodeForEachFanout(regNode,k,fanout) { 00113 if (st_lookup(regionNodes,(char *)fanout,&dummy)) 00114 (*count)++; 00115 } 00116 /* The global function implemented by regNode is used count number 00117 of times */ 00118 assert(*count); 00119 st_insert(nodeCountTable,(char *)regNode,(char *)count); 00120 } 00121 00122 /* Reprogram region nodes */ 00123 arrayForEachItem(Ntk_Node_t *,regionArray,i,regNode) { 00124 int numFanin; 00125 boolean reenc,replaced; 00126 bdd_node **orgVars,**auxVars,*orgCube; 00127 00128 /* Skip, if it is a PI. */ 00129 if (Ntk_NodeTestIsPrimaryInput(regNode)) 00130 continue; 00131 00132 /* Determine if the localAlt really needs to be re-encoded. This 00133 is true if any of the fanin nodes have been reprogrammed. If 00134 any fanin node of 'regNode' has a non NULL globalAlt, then it 00135 means that fanin node has been reprogrammed. */ 00136 faninBdds = array_alloc(bdd_node *,0); 00137 faninNodes = array_alloc(Ntk_Node_t *,0); 00138 reenc = FALSE; 00139 replaced = FALSE; 00140 if (SpfdNodeReadLocalAlt(applData,regNode) != 00141 bdd_read_logic_zero(ddManager)) { 00142 Ntk_NodeForEachFanin(regNode,j,fanin) { 00143 00144 /* If a particular wire is redundant/replaced, make the sink node 00145 independent of that node. */ 00146 if (!(st_lookup(wireTable,(char *)fanin,&sinkTable) && 00147 st_lookup(sinkTable,(char *)regNode,&dummy))) { 00148 /* If not removed, is it replaced? */ 00149 if (!(st_lookup(replaceTable,(char *)regNode,&sinkTable) && 00150 st_lookup(sinkTable,(char *)fanin,&newFanin))) { 00151 globalAlt = SpfdNodeReadGlobalAlternative(applData,fanin); 00152 if (globalAlt) { /* Reprogrammed? */ 00153 array_insert_last(bdd_node *,faninBdds,globalAlt); 00154 array_insert_last(Ntk_Node_t *,faninNodes,fanin); 00155 reenc = TRUE; 00156 } else { /* No. So use the original global function */ 00157 st_lookup(currBddReq,(char *)fanin,&ddTemp); 00158 array_insert_last(bdd_node *,faninBdds,ddTemp); 00159 array_insert_last(Ntk_Node_t *,faninNodes,fanin); 00160 } 00161 } else { 00162 /* The wire fanin --> regNode has been replaced by newFanin --> 00163 regNode */ 00164 globalAlt = SpfdNodeReadGlobalAlternative(applData,newFanin); 00165 assert(globalAlt); 00166 array_insert_last(bdd_node *,faninBdds,globalAlt); 00167 array_insert_last(Ntk_Node_t *,faninNodes,newFanin); 00168 reenc = TRUE; 00169 replaced = TRUE; 00170 } 00171 } else { 00172 reenc = TRUE; 00173 } 00174 } 00175 } 00176 00177 if (reenc) { /* Reencode the localAlt */ 00178 /* Compute the encoding relation */ 00179 relNew = SpfdComputeNodeArrayRelation(applData,NIL(st_table), 00180 faninBdds,faninNodes, 00181 FALSE,&piSwap); 00182 array_free(faninBdds); 00183 array_free(faninNodes); 00184 relOld = SpfdComputeNodeArrayRelation(applData,currBddReq,NIL(array_t), 00185 Ntk_NodeReadFanins(regNode), 00186 TRUE,&piSwap); 00187 bdd_ref(encRel = bdd_bdd_and_abstract(ddManager,relNew,relOld,xCube)); 00188 bdd_recursive_deref(ddManager,relNew); 00189 bdd_recursive_deref(ddManager,relOld); 00190 00191 if (piSwap) { /* If we have used alternate PI ids */ 00192 ddTemp = SpfdSwapPiAndAltPi(applData,encRel); 00193 bdd_recursive_deref(ddManager,encRel); 00194 encRel = ddTemp; 00195 } 00196 /* Now encRel is in terms of Y, Y'. Y variables are the node's 00197 mdd ids. Y' are the auxIds of regNode's fanin nodes. One of 00198 these fanin nodes could be a new node replacing an old node. */ 00199 /* Prepare variables for swapping and abstraction */ 00200 numFanin = Ntk_NodeReadNumFanins(regNode); 00201 orgVars = ALLOC(bdd_node *,numFanin); 00202 auxVars = ALLOC(bdd_node *,numFanin); 00203 Ntk_NodeForEachFanin(regNode,k,fanin) { 00204 orgVars[k] = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin)); 00205 auxVars[k] = bdd_bdd_ith_var(ddManager, 00206 SpfdNodeReadAuxId(applData,fanin)); 00207 } 00208 bdd_ref(orgCube = bdd_bdd_compute_cube(ddManager,orgVars, 00209 NIL(int),numFanin)); 00210 00211 /* Re-encode the localAlt function. ddTemp is in terms of Y' */ 00212 localAlt = SpfdNodeReadLocalAlt(applData,regNode); 00213 bdd_ref(ddTemp = bdd_bdd_and_abstract(ddManager,localAlt,encRel,orgCube)); 00214 SpfdNodeDeleteLocalAlt(applData,regNode); 00215 bdd_recursive_deref(ddManager,encRel); 00216 bdd_recursive_deref(ddManager,orgCube); 00217 00218 /* Check if the wire is replaced. Pay attention to auxVars and 00219 orgVars. */ 00220 /* Small caveat: Only here it is possible that the orgVar of 00221 newFanin is already being used as auxId by one of the nodes 00222 in the region. The situation can be as below: */ 00223 /* 12 -> 19, 15->24, 133->15, 18->23. During swapping, 133 will 00224 be replace by 15. This will create a problem because 15->24 00225 has not been done yet! A consolation is that the intersection 00226 between the 'from' set and the 'two' set is only ONE. */ 00227 /* To avoid this problem, we do two step swap to be sure. */ 00228 if (replaced) { 00229 bdd_node **secOrgVars,**secAuxVars; 00230 int auxId,orgId,index; 00231 00232 FREE(orgVars); 00233 FREE(auxVars); 00234 orgVars = ALLOC(bdd_node *,numFanin-1); 00235 auxVars = ALLOC(bdd_node *,numFanin-1); 00236 secOrgVars = ALLOC(bdd_node *,1); 00237 secAuxVars = ALLOC(bdd_node *,1); 00238 index = 0; 00239 Ntk_NodeForEachFanin(regNode,k,fanin) { 00240 if (st_lookup(replaceTable,(char *)regNode,&sinkTable) && 00241 st_lookup(sinkTable,(char *)fanin,&newFanin)) { 00242 orgId = Ntk_NodeReadMddId(newFanin); 00243 auxId = SpfdNodeReadAuxId(applData,newFanin); 00244 secOrgVars[0] = bdd_bdd_ith_var(ddManager,orgId); 00245 secAuxVars[0] = bdd_bdd_ith_var(ddManager,auxId); 00246 } else { 00247 orgId = Ntk_NodeReadMddId(fanin); 00248 auxId = SpfdNodeReadAuxId(applData,fanin); 00249 orgVars[index] = bdd_bdd_ith_var(ddManager,orgId); 00250 auxVars[index] = bdd_bdd_ith_var(ddManager,auxId); 00251 index++; 00252 } 00253 } 00254 bdd_ref(localAlt = bdd_bdd_swap_variables(ddManager,ddTemp,auxVars, 00255 orgVars,index)); 00256 bdd_recursive_deref(ddManager,ddTemp); 00257 bdd_ref(ddTemp = bdd_bdd_swap_variables(ddManager,localAlt, 00258 secAuxVars,secOrgVars,1)); 00259 bdd_recursive_deref(ddManager,localAlt); 00260 localAlt = ddTemp; 00261 FREE(secOrgVars); 00262 FREE(secAuxVars); 00263 } else { 00264 bdd_ref(localAlt = bdd_bdd_swap_variables(ddManager,ddTemp,auxVars, 00265 orgVars,numFanin)); 00266 bdd_recursive_deref(ddManager,ddTemp); 00267 } 00268 FREE(orgVars); 00269 FREE(auxVars); 00270 00271 SpfdNodeSetLocalAlt(applData,regNode,localAlt); 00272 } else { 00273 array_free(faninBdds); 00274 array_free(faninNodes); 00275 } 00276 00277 /* Compute the global function (only if it is needed, i.e, it is 00278 present in the nodeCountTable) implemented by the alternate 00279 function, localAlt, chosen from the SPFD. */ 00280 localAlt = SpfdNodeReadLocalAlt(applData,regNode); 00281 if (st_lookup(nodeCountTable,(char *)regNode,&count) && 00282 !Ntk_NodeTestIsPrimaryInput(regNode) && 00283 !Ntk_NodeTestIsPrimaryOutput(regNode)) { 00284 int size,id; 00285 bdd_node **composeBdds; 00286 00287 size = bdd_num_vars(ddManager);; 00288 composeBdds = ALLOC(bdd_node *,size); 00289 for (k = 0; k < size; k++) { 00290 composeBdds[k] = bdd_bdd_ith_var(ddManager,k); 00291 } 00292 00293 /* Here I don't have to worry about checking if a wire is redundant. The 00294 localAlt of the node already is independent of source node of that 00295 wire and so composing with the source node does not matter. But I do 00296 need to check for wire replacement. */ 00297 Ntk_NodeForEachFanin(regNode,k,fanin) { 00298 if (st_lookup(replaceTable,(char *)regNode,&sinkTable) && 00299 st_lookup(sinkTable,(char *)fanin,&newFanin)) { 00300 id = Ntk_NodeReadMddId(newFanin); 00301 globalAlt = SpfdNodeReadGlobalAlternative(applData,newFanin); 00302 composeBdds[id] = globalAlt; 00303 } else { 00304 id = Ntk_NodeReadMddId(fanin); 00305 globalAlt = SpfdNodeReadGlobalAlternative(applData,fanin); 00306 if (globalAlt) { 00307 composeBdds[id] = globalAlt; 00308 } else { 00309 st_lookup(currBddReq,(char *)fanin,(char **)&composeBdds[id]); 00310 } 00311 } 00312 } 00313 localAlt = SpfdNodeReadLocalAlt(applData,regNode); 00314 bdd_ref(globalAlt = bdd_bdd_vector_compose(ddManager,localAlt, 00315 composeBdds)); 00316 SpfdNodeSetGlobalAlternative(applData,regNode,globalAlt); 00317 FREE(composeBdds); 00318 } 00319 00320 /* Delete the global BDDs of fanin nodes if unnecessary */ 00321 Ntk_NodeForEachFanin(regNode,k,fanin) { 00322 int *count; 00323 if (st_lookup(nodeCountTable,(char *)fanin,&count)) { 00324 (*count)--; 00325 if (*count == 0) { 00326 st_delete(currBddReq,&fanin,&bdd1); 00327 bdd_recursive_deref(ddManager,bdd1); 00328 SpfdNodeDeleteGlobalAlternative(applData,fanin); 00329 st_delete(nodeCountTable,&fanin,&count); 00330 FREE(count); 00331 } 00332 } 00333 } 00334 00335 /* Finally, delete the redundant wires */ 00336 nodeArray = array_dup(Ntk_NodeReadFanins(regNode)); 00337 arrayForEachItem(Ntk_Node_t *,nodeArray,j,fanin) { 00338 /* If a particular wire is redundant, make the sink node independent of 00339 the source node. */ 00340 if (st_lookup(wireTable,(char *)fanin,&sinkTable) && 00341 st_lookup(sinkTable,(char *)regNode,&dummy)) { 00342 /* remove the wire from the wireTable */ 00343 st_delete(sinkTable,®Node,&dummy); 00344 if (st_count(sinkTable) == 0) { 00345 st_delete(wireTable,&fanin,&sinkTable); 00346 st_free_table(sinkTable); 00347 } 00348 SpfdNetworkRemoveWire(network,fanin,regNode); 00349 } else if (st_lookup(replaceTable,(char *)regNode,&sinkTable) && 00350 st_lookup(sinkTable,(char *)fanin,&newFanin)) { 00351 /* In this case I do not clean replaceTable as was done for 00352 wireTable. The table is needed later. */ 00353 /* Add the new wire first and then remove the old wire. This 00354 way the source node of the new wire will not be deleted if 00355 it initially had a fanout of 1 and was in the TFI of the 00356 old wire. newsource --> fanin --> regNode. If 'fanin' has 00357 only one fanout then its entire TFI will be deleted, hence, 00358 possibly deleteing newsource from the network. */ 00359 SpfdNetworkAddWire(network,newFanin,regNode); 00360 SpfdNetworkRemoveWire(network,fanin,regNode); 00361 } 00362 } 00363 array_free(nodeArray); 00364 00365 /* Reprogram the node's table data structure. */ 00366 localAlt = SpfdNodeReadLocalAlt(applData,regNode); 00367 SpfdReprogramNode(network,applData,regNode); 00368 SpfdNodeDeleteLocalAlt(applData,regNode); 00369 } 00370 00371 /* nodeCountTable need not be empty at this time as some wire may be 00372 removed and the count is not reduced appropriately in nodeCountTable. 00373 So, delete them explicitly. Defensive programming. */ 00374 st_foreach_item(nodeCountTable,stGen,®Node,&count) { 00375 st_delete(currBddReq,®Node,&bdd1); 00376 bdd_recursive_deref(ddManager,bdd1); 00377 SpfdNodeDeleteGlobalAlternative(applData,regNode); 00378 FREE(count); 00379 } 00380 st_free_table(nodeCountTable); 00381 00382 /* Just reusing variable bound */ 00383 bound = st_count(currBddReq); 00384 assert(bound == 0); 00385 st_free_table(applData->currBddReq); 00386 applData->currBddReq = NIL(st_table); 00387 00388 return; 00389 } /* End of SpfdReprogramRegionNodes */ 00390 00391 00400 void 00401 SpfdReprogramNode( 00402 Ntk_Network_t *network, 00403 SpfdApplData_t *applData, 00404 Ntk_Node_t *regNode) 00405 { 00406 bdd_node *localAlt; 00407 bdd_node *bdd1,*bdd0; 00408 bdd_manager *ddManager = applData->ddManager; 00409 graph_t *partition = (graph_t *) Ntk_NetworkReadApplInfo( 00410 network,PART_NETWORK_APPL_KEY); 00411 Tbl_Table_t *table; 00412 vertex_t *vertexPtr; 00413 Mvf_Function_t *mvf; 00414 mdd_t *tempMdd; 00415 00416 /* Extract old local function from the partition */ 00417 vertexPtr = Part_PartitionFindVertexByMddId(partition, 00418 Ntk_NodeReadMddId(regNode)); 00419 mvf = Part_VertexReadFunction(vertexPtr); 00420 /* First delete the old mvf */ 00421 Mvf_FunctionFree(mvf); 00422 00423 /* Steps to reprogram the node. 1. Delete the old table associated with 00424 * this node. The table can be deleted because in BLIF format tables have 00425 * only a single output unlike BLIF-MV. 2. Create a new table and set it 00426 * in the node. 3. Update the new local function in the partition */ 00427 table = Ntk_NodeReadTable(regNode); 00428 Tbl_TableFree(table); 00429 00430 bdd_ref(localAlt = SpfdNodeReadLocalAlt(applData,regNode)); 00431 00432 /* If pattern simulation is performed, update node's static 00433 probability and transition probability */ 00434 if (spfdPerfSim) { 00435 float prob; 00436 prob = Truesim_BddNodeComputeProbability(network,localAlt); 00437 Truesim_NetworkSetNodeStaticProb(network,regNode,prob); 00438 Truesim_NetworkSetNodeSwitchingProb(network,regNode,2*prob*(1-prob)); 00439 } 00440 00441 /* Create the new table */ 00442 tempMdd = bdd_construct_bdd_t(ddManager,localAlt); 00443 table = BuildNewTable(network,regNode,tempMdd); 00444 Ntk_NodeSetTable(regNode,table); 00445 mdd_free(tempMdd); 00446 00447 /* Compute the node's new MVF and set it in the partition. */ 00448 mvf = array_alloc(bdd_t *,2); 00449 bdd_ref(bdd1 = SpfdNodeReadLocalAlt(applData,regNode)); 00450 bdd_ref(bdd0 = bdd_not_bdd_node(bdd1)); 00451 array_insert(bdd_t *,mvf,0,bdd_construct_bdd_t(ddManager,bdd0)); 00452 array_insert(bdd_t *,mvf,1,bdd_construct_bdd_t(ddManager,bdd1)); 00453 Part_VertexSetFunction(vertexPtr,mvf); 00454 00455 return; 00456 } /* End of SpfdReprogramNode */ 00457 00458 00466 void 00467 SpfdNetworkRemoveWire( 00468 Ntk_Network_t *network, 00469 Ntk_Node_t *from, 00470 Ntk_Node_t *to) 00471 { 00472 SpfdApplData_t *applData; 00473 st_table *wiresRemoved; 00474 st_table *sinkTable; 00475 array_t *oldFanouts,*oldFanins; 00476 array_t *newFanouts,*newFanins; 00477 int i; 00478 Ntk_Node_t *ntkNode; 00479 00480 applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, 00481 SPFD_NETWORK_APPL_KEY); 00482 wiresRemoved = applData->wiresRemoved; 00483 00484 assert(network == Ntk_NodeReadNetwork(from)); 00485 assert(network == Ntk_NodeReadNetwork(to)); 00486 00487 oldFanouts = Ntk_NodeReadFanouts(from); 00488 oldFanins = Ntk_NodeReadFanins(to); 00489 00490 newFanouts = array_alloc(Ntk_Node_t *,0); 00491 newFanins = array_alloc(Ntk_Node_t *,0); 00492 00493 /* Remove 'from' from the fanins of 'to' */ 00494 if (spfdVerbose > 1) 00495 (void) fprintf(vis_stdout,"** spfd info: Wire "); 00496 arrayForEachItem(Ntk_Node_t *,oldFanins,i,ntkNode) { 00497 if (ntkNode != from) { 00498 array_insert_last(Ntk_Node_t *,newFanins,ntkNode); 00499 } else { 00500 if (spfdVerbose > 1) 00501 (void) fprintf(vis_stdout,"%s --> ",Ntk_NodeReadName(from)); 00502 } 00503 } 00504 /* Remove 'to' from the fanouts of 'from' */ 00505 arrayForEachItem(Ntk_Node_t *,oldFanouts,i,ntkNode) { 00506 if (ntkNode != to) { 00507 array_insert_last(Ntk_Node_t *,newFanouts,ntkNode); 00508 } else { 00509 if (spfdVerbose > 1) 00510 (void) fprintf(vis_stdout,"%s removed.\n",Ntk_NodeReadName(to)); 00511 } 00512 } 00513 00514 /* Insert this wire in the wiresRemoved table */ 00515 if (st_lookup(wiresRemoved,(char *)from,&sinkTable)) { 00516 st_insert(sinkTable,(char *)to,(char *)to); 00517 } else { 00518 sinkTable = st_init_table(st_ptrcmp,st_ptrhash); 00519 st_insert(sinkTable,(char *)to,(char *)to); 00520 st_insert(wiresRemoved,(char *)from,(char *)sinkTable); 00521 } 00522 00523 /* Set the new arrays */ 00524 Ntk_NodeSetFanins(to,newFanins); 00525 Ntk_NodeSetFanouts(from,newFanouts); 00526 00527 /* The fanin cone is redundant if 'from' had only a single fanout and it is 00528 not a primary output. */ 00529 if (array_n(newFanouts) == 0 && 00530 !Ntk_NodeTestIsPrimaryOutput(from)) { 00531 array_t *faninArray; 00532 boolean check; 00533 faninArray = array_dup(Ntk_NodeReadFanins(from)); 00534 arrayForEachItem(Ntk_Node_t *,faninArray,i,ntkNode) { 00535 SpfdNetworkRemoveWire(network,ntkNode,from); 00536 /* Register the wire removed */ 00537 if (st_lookup(wiresRemoved,(char *)ntkNode,&sinkTable)) { 00538 st_insert(sinkTable,(char *)from,(char *)from); 00539 } else { 00540 sinkTable = st_init_table(st_ptrcmp,st_ptrhash); 00541 st_insert(sinkTable,(char *)from,(char *)from); 00542 st_insert(wiresRemoved,(char *)ntkNode,(char *)sinkTable); 00543 } 00544 } 00545 array_free(faninArray); 00546 check = Ntk_NodeRemoveFromNetwork(network,from,0,1,0); 00547 assert(check); 00548 if (spfdVerbose > 1) 00549 (void) fprintf(vis_stdout,"** spfd info: Node %s removed.\n", 00550 Ntk_NodeReadName(from)); 00551 st_insert(applData->nodesRemoved,(char *)from,(char *)0); 00552 } 00553 00554 spfdNtkChanged = TRUE; 00555 00556 return; 00557 00558 } /* End of SpfdNetworkRemoveWire */ 00559 00560 00568 void 00569 SpfdNetworkAddWire( 00570 Ntk_Network_t *network, 00571 Ntk_Node_t *from, 00572 Ntk_Node_t *to) 00573 { 00574 array_t *oldFanouts,*oldFanins; 00575 00576 assert(network == Ntk_NodeReadNetwork(from)); 00577 assert(network == Ntk_NodeReadNetwork(to)); 00578 00579 oldFanouts = Ntk_NodeReadFanouts(from); 00580 oldFanins = Ntk_NodeReadFanins(to); 00581 00582 array_insert_last(Ntk_Node_t *,oldFanouts,to); 00583 array_insert_last(Ntk_Node_t *,oldFanins,from); 00584 00585 if (spfdVerbose > 1) 00586 (void) fprintf(vis_stdout,"** spfd info: Wire %s --> %s added\n", 00587 Ntk_NodeReadName(from),Ntk_NodeReadName(to)); 00588 spfdWiresAdded++; 00589 00590 spfdNtkChanged = TRUE; 00591 00592 return; 00593 00594 } /* End of SpfdNetworkAddWire */ 00595 00596 00597 /*---------------------------------------------------------------------------*/ 00598 /* Definition of static functions */ 00599 /*---------------------------------------------------------------------------*/ 00600 00609 static Tbl_Table_t * 00610 BuildNewTable( 00611 Ntk_Network_t *network, 00612 Ntk_Node_t *ntkNode, 00613 mdd_t *mddFunc) 00614 { 00615 bdd_manager *ddManager = Ntk_NetworkReadMddManager(network); 00616 SpfdApplData_t *applData; 00617 st_table *wiresRemoved; 00618 Tbl_Table_t *table; 00619 Tbl_Entry_t *entry; 00620 int i,id,index; 00621 Ntk_Node_t *loopNode; 00622 Var_Variable_t *var; 00623 array_t *faninIdArray,*cube,*nodeArray; 00624 st_table *faninTable; 00625 bdd_gen *ddGen; 00626 00627 applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, 00628 SPFD_NETWORK_APPL_KEY); 00629 wiresRemoved = applData->wiresRemoved; 00630 00631 /* Allocaet a Table data structure */ 00632 table = Tbl_TableAlloc(); 00633 00634 /* Find the true support. */ 00635 faninIdArray = mdd_get_support(ddManager,mddFunc); 00636 faninTable = st_init_table(st_numcmp,st_numhash); 00637 arrayForEachItem(int,faninIdArray,i,id) { 00638 st_insert(faninTable,(char *)(long)id,(char *)(long)id); 00639 } 00640 array_free(faninIdArray); 00641 00642 /* Delete wires that are not in the support of ntkNode. Collect 00643 valid fanin ids in the same order as already present in the 00644 node's original Table data structure. */ 00645 faninIdArray = array_alloc(int,0); 00646 nodeArray = array_dup(Ntk_NodeReadFanins(ntkNode)); 00647 index = 0; 00648 arrayForEachItem(Ntk_Node_t *,nodeArray,i,loopNode) { 00649 id = Ntk_NodeReadMddId(loopNode); 00650 if (!st_lookup(faninTable,(char *)(long)id,&id)) { 00651 st_table *sinkTable; 00652 00653 if (spfdVerbose > 2) 00654 (void) fprintf(vis_stdout, 00655 "** spfd info: removing wire in BuildNewTable.\n"); 00656 SpfdNetworkRemoveWire(network,loopNode,ntkNode); 00657 /* Insert the wire removed for the purpose of statistics */ 00658 if (st_lookup(wiresRemoved,(char *)loopNode,&sinkTable)) { 00659 st_insert(sinkTable,(char *)ntkNode,(char *)ntkNode); 00660 } else { 00661 sinkTable = st_init_table(st_ptrcmp,st_ptrhash); 00662 st_insert(sinkTable,(char *)ntkNode,(char *)ntkNode); 00663 st_insert(wiresRemoved,(char *)loopNode,(char *)sinkTable); 00664 } 00665 } else { 00666 var = Ntk_NodeReadVariable(loopNode); 00667 array_insert_last(int,faninIdArray,id); 00668 Tbl_TableSetVar(table,index,var,0); 00669 index++; 00670 } 00671 } 00672 array_free(nodeArray); 00673 st_free_table(faninTable); 00674 00675 /* Set the output variable */ 00676 var = Ntk_NodeReadVariable(ntkNode); 00677 Tbl_TableSetVar(table,0,var,1/*output flag*/); 00678 00679 /* Set the defaults field to 0 */ 00680 entry = Tbl_EntryAlloc(Tbl_EntryNormal_c); 00681 Tbl_EntrySetValue(entry,0,0); 00682 Tbl_TableDefaultSetEntry(table,entry,0/*output index */); 00683 00684 /* Add rows for each cube in the function */ 00685 /* cube is an array of int ids. The length of cube is the size of 00686 the manager */ 00687 ddGen = bdd_first_cube(mddFunc,&cube); 00688 /* If the function is zero, just add the zero cube */ 00689 if (bdd_gen_read_status(ddGen) == bdd_EMPTY) { 00690 array_t *zeroCube; 00691 int size; 00692 00693 size = bdd_num_vars(ddManager); 00694 zeroCube = array_alloc(int,0); 00695 for (i = 0; i < size; i++) { 00696 array_insert_last(int,zeroCube,2); 00697 } 00698 TableAddCube(table,faninIdArray,zeroCube,0); 00699 array_free(zeroCube); 00700 } else { 00701 do { 00702 TableAddCube(table,faninIdArray,cube,1); 00703 } while (bdd_next_cube(ddGen,&cube)); 00704 } 00705 bdd_gen_free(ddGen); 00706 00707 array_free(faninIdArray); 00708 00709 return table; 00710 } /* End of BuildNewTable */ 00711 00712 00721 static void 00722 TableAddCube( 00723 Tbl_Table_t *table, 00724 array_t *faninIdArray, 00725 array_t *cube, 00726 int value) 00727 { 00728 int rowIndex,colIndex,numFanins; 00729 int mddId,phase; 00730 Tbl_Entry_t *entry; 00731 00732 numFanins = Tbl_TableReadNumInputs(table); 00733 00734 /* Fill in the entries for the just added row */ 00735 rowIndex = Tbl_TableAddRow(table); 00736 for (colIndex = 0; colIndex < numFanins; colIndex++) { 00737 entry = Tbl_EntryAlloc(Tbl_EntryNormal_c); 00738 mddId = array_fetch(int,faninIdArray,colIndex); 00739 phase = array_fetch(int,cube,mddId); 00740 if (phase == 2) { 00741 Tbl_EntrySetValue(entry,0,1); 00742 } else { 00743 Tbl_EntrySetValue(entry,phase,phase); 00744 } 00745 Tbl_TableSetEntry(table,entry,rowIndex,colIndex,0/*input flag*/); 00746 } 00747 /* Add an entry in the output column */ 00748 entry = Tbl_EntryAlloc(Tbl_EntryNormal_c); 00749 Tbl_EntrySetValue(entry,value,value); 00750 Tbl_TableSetEntry(table,entry,rowIndex,0,1/*output flag*/); 00751 00752 } /* End of TableAddCube */