source: vis_dev/vis-2.3/src/spfd/spfdProg.c @ 23

Last change on this file since 23 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 26.1 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [spfdProg.c]
4
5  PackageName [spfd]
6
7  Synopsis [Routines that perform reprogramming of LUTs (nodes) in the
8  circuit.]
9
10  Description [Routines that perform reprogramming of LUTs (nodes) in the
11  circuit. Wire removal/addition operations are also performed.]
12
13  SeeAlso     [spfdOpt.c spfdSpfd.c]
14
15  Author      [Balakrishna Kumthekar]
16
17  Copyright [This file was created at the University of Colorado at Boulder.
18  The University of Colorado at Boulder makes no warranty about the suitability
19  of this software for any purpose.  It is presented on an AS IS basis.]
20
21******************************************************************************/
22
23#include "spfdInt.h"
24
25/*---------------------------------------------------------------------------*/
26/* Constant declarations                                                     */
27/*---------------------------------------------------------------------------*/
28
29
30/*---------------------------------------------------------------------------*/
31/* Type declarations                                                         */
32/*---------------------------------------------------------------------------*/
33
34
35/*---------------------------------------------------------------------------*/
36/* Structure declarations                                                    */
37/*---------------------------------------------------------------------------*/
38
39/*---------------------------------------------------------------------------*/
40/* Variable declarations                                                     */
41/*---------------------------------------------------------------------------*/
42
43/*---------------------------------------------------------------------------*/
44/* Macro declarations                                                        */
45/*---------------------------------------------------------------------------*/
46
47
48/**AutomaticStart*************************************************************/
49
50/*---------------------------------------------------------------------------*/
51/* Static function prototypes                                                */
52/*---------------------------------------------------------------------------*/
53
54static Tbl_Table_t * BuildNewTable(Ntk_Network_t *network, Ntk_Node_t *ntkNode, mdd_t *mddFunc);
55static void TableAddCube(Tbl_Table_t *table, array_t *faninIdArray, array_t *cube, int value);
56
57/**AutomaticEnd***************************************************************/
58
59
60/*---------------------------------------------------------------------------*/
61/* Definition of exported functions                                          */
62/*---------------------------------------------------------------------------*/
63
64
65/*---------------------------------------------------------------------------*/
66/* Definition of internal functions                                          */
67/*---------------------------------------------------------------------------*/
68/**Function********************************************************************
69
70  Synopsis [Reprogram the nodes in the 'regionArray' based on an
71  alternate implementation selected from the SPFDs. The cluster nodes
72  are reprogrammed in the increasing order of their topological
73  depth. When a node is being reprogrammed all of its fanin have
74  either been reprogrammed or have retained their original
75  implementation.]
76
77  SideEffects [None]
78
79******************************************************************************/
80void
81SpfdReprogramRegionNodes(
82  Ntk_Network_t *network,
83  SpfdApplData_t *applData,
84  array_t *regionArray)
85{
86  st_table *nodeCountTable,*sinkTable;
87  st_table *regionNodes = applData->currRegionNodes;
88  st_table *currBddReq = applData->currBddReq;
89  st_table *wireTable = applData->currWireTable;
90  st_table *replaceTable = applData->currReplaceTable;
91  bdd_manager *ddManager = applData->ddManager;
92  Ntk_Node_t *fanout,*regNode,*fanin,*newFanin;
93  bdd_node *bdd1,*localAlt,*globalAlt;
94  bdd_node *ddTemp,*relNew,*relOld,*encRel;
95  bdd_node *xCube;
96  char *dummy;
97  st_generator *stGen;
98  int bound,i,j,k,piSwap;
99  int *count;
100  array_t *faninBdds,*faninNodes,*nodeArray;
101
102  /* Cube of primary inputs. */
103  xCube = applData->currXCube;
104  /* Analyze the region to find out how many times the
105     alternative/global function of an individual region node will be
106     used. This count will be used to remove those functions when no
107     longer needed, hence avoid memory peaks. */
108  nodeCountTable = st_init_table(st_ptrcmp,st_ptrhash);
109  st_foreach_item(currBddReq,stGen,&regNode,&bdd1) {
110    count = ALLOC(int,1);
111    *count = 0;
112    Ntk_NodeForEachFanout(regNode,k,fanout) {
113      if (st_lookup(regionNodes,(char *)fanout,&dummy))
114        (*count)++;
115    }
116    /* The global function implemented by regNode is used count number
117       of times */
118    assert(*count);
119    st_insert(nodeCountTable,(char *)regNode,(char *)count);
120  }
121
122  /* Reprogram region nodes */
123  arrayForEachItem(Ntk_Node_t *,regionArray,i,regNode) {
124    int numFanin;
125    boolean reenc,replaced;
126    bdd_node **orgVars,**auxVars,*orgCube;
127
128    /* Skip, if it is a PI. */
129    if (Ntk_NodeTestIsPrimaryInput(regNode))
130      continue;
131   
132    /* Determine if the localAlt really needs to be re-encoded. This
133       is true if any of the fanin nodes have been reprogrammed. If
134       any fanin node of 'regNode' has a non NULL globalAlt, then it
135       means that fanin node has been reprogrammed. */
136    faninBdds = array_alloc(bdd_node *,0);
137    faninNodes = array_alloc(Ntk_Node_t *,0);
138    reenc = FALSE;
139    replaced = FALSE;
140    if (SpfdNodeReadLocalAlt(applData,regNode) !=
141        bdd_read_logic_zero(ddManager)) {
142      Ntk_NodeForEachFanin(regNode,j,fanin) {
143
144        /* If a particular wire is redundant/replaced, make the sink node
145           independent of that node. */
146        if (!(st_lookup(wireTable,(char *)fanin,&sinkTable) &&
147              st_lookup(sinkTable,(char *)regNode,&dummy))) {
148          /* If not removed, is it replaced? */
149          if (!(st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
150                st_lookup(sinkTable,(char *)fanin,&newFanin))) {
151            globalAlt = SpfdNodeReadGlobalAlternative(applData,fanin);
152            if (globalAlt) { /* Reprogrammed? */
153              array_insert_last(bdd_node *,faninBdds,globalAlt);
154              array_insert_last(Ntk_Node_t *,faninNodes,fanin);
155              reenc = TRUE;
156            } else { /* No. So use the original global function */
157              st_lookup(currBddReq,(char *)fanin,&ddTemp);
158              array_insert_last(bdd_node *,faninBdds,ddTemp);
159              array_insert_last(Ntk_Node_t *,faninNodes,fanin);
160            }
161          } else {
162            /* The wire fanin --> regNode has been replaced by newFanin -->
163               regNode */
164            globalAlt = SpfdNodeReadGlobalAlternative(applData,newFanin);
165            assert(globalAlt);
166            array_insert_last(bdd_node *,faninBdds,globalAlt);
167            array_insert_last(Ntk_Node_t *,faninNodes,newFanin);
168            reenc = TRUE;
169            replaced = TRUE;
170          }
171        } else {
172          reenc = TRUE;
173        }
174      }
175    }
176     
177    if (reenc) { /* Reencode the localAlt */
178      /* Compute the encoding relation */
179      relNew = SpfdComputeNodeArrayRelation(applData,NIL(st_table),
180                                              faninBdds,faninNodes,
181                                              FALSE,&piSwap);
182      array_free(faninBdds);
183      array_free(faninNodes);
184      relOld = SpfdComputeNodeArrayRelation(applData,currBddReq,NIL(array_t),
185                                              Ntk_NodeReadFanins(regNode),
186                                              TRUE,&piSwap);
187      bdd_ref(encRel = bdd_bdd_and_abstract(ddManager,relNew,relOld,xCube));
188      bdd_recursive_deref(ddManager,relNew);
189      bdd_recursive_deref(ddManager,relOld);
190
191      if (piSwap) { /* If we have used alternate PI ids */
192        ddTemp = SpfdSwapPiAndAltPi(applData,encRel);
193        bdd_recursive_deref(ddManager,encRel);
194        encRel = ddTemp;
195      }
196      /* Now encRel is in terms of Y, Y'. Y variables are the node's
197         mdd ids. Y' are the auxIds of regNode's fanin nodes. One of
198         these fanin nodes could be a new node replacing an old node. */
199      /* Prepare variables for swapping and abstraction */
200      numFanin = Ntk_NodeReadNumFanins(regNode);
201      orgVars = ALLOC(bdd_node *,numFanin);
202      auxVars = ALLOC(bdd_node *,numFanin);
203      Ntk_NodeForEachFanin(regNode,k,fanin) {
204        orgVars[k] = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin));
205        auxVars[k] = bdd_bdd_ith_var(ddManager,
206                                     SpfdNodeReadAuxId(applData,fanin));
207      }
208      bdd_ref(orgCube = bdd_bdd_compute_cube(ddManager,orgVars,
209                                             NIL(int),numFanin));
210
211      /* Re-encode the localAlt function. ddTemp is in terms of Y' */
212      localAlt = SpfdNodeReadLocalAlt(applData,regNode);
213      bdd_ref(ddTemp = bdd_bdd_and_abstract(ddManager,localAlt,encRel,orgCube));
214      SpfdNodeDeleteLocalAlt(applData,regNode);
215      bdd_recursive_deref(ddManager,encRel);
216      bdd_recursive_deref(ddManager,orgCube);
217
218      /* Check if the wire is replaced. Pay attention to auxVars and
219         orgVars. */
220      /* Small caveat: Only here it is possible that the orgVar of
221         newFanin is already being used as auxId by one of the nodes
222         in the region. The situation can be as below: */
223      /* 12 -> 19, 15->24, 133->15, 18->23. During swapping, 133 will
224         be replace by 15. This will create a problem because 15->24
225         has not been done yet! A consolation is that the intersection
226         between the 'from' set and the 'two' set is only ONE. */
227      /* To avoid this problem, we do two step swap to be sure. */
228      if (replaced) {
229        bdd_node **secOrgVars,**secAuxVars;
230        int auxId,orgId,index;
231       
232        FREE(orgVars);
233        FREE(auxVars);
234        orgVars = ALLOC(bdd_node *,numFanin-1);
235        auxVars = ALLOC(bdd_node *,numFanin-1);
236        secOrgVars = ALLOC(bdd_node *,1);
237        secAuxVars = ALLOC(bdd_node *,1);
238        index = 0;
239        Ntk_NodeForEachFanin(regNode,k,fanin) {
240          if (st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
241              st_lookup(sinkTable,(char *)fanin,&newFanin)) {
242            orgId = Ntk_NodeReadMddId(newFanin);
243            auxId = SpfdNodeReadAuxId(applData,newFanin);
244            secOrgVars[0] = bdd_bdd_ith_var(ddManager,orgId);
245            secAuxVars[0] = bdd_bdd_ith_var(ddManager,auxId);
246          } else {
247            orgId = Ntk_NodeReadMddId(fanin);
248            auxId = SpfdNodeReadAuxId(applData,fanin);
249            orgVars[index] = bdd_bdd_ith_var(ddManager,orgId);
250            auxVars[index] = bdd_bdd_ith_var(ddManager,auxId);
251            index++;
252          }
253        }
254        bdd_ref(localAlt = bdd_bdd_swap_variables(ddManager,ddTemp,auxVars,
255                                                  orgVars,index));
256        bdd_recursive_deref(ddManager,ddTemp);
257        bdd_ref(ddTemp = bdd_bdd_swap_variables(ddManager,localAlt,
258                                                secAuxVars,secOrgVars,1));
259        bdd_recursive_deref(ddManager,localAlt);
260        localAlt = ddTemp;
261        FREE(secOrgVars);
262        FREE(secAuxVars);
263      } else {
264        bdd_ref(localAlt = bdd_bdd_swap_variables(ddManager,ddTemp,auxVars,
265                                                  orgVars,numFanin));
266        bdd_recursive_deref(ddManager,ddTemp);
267      }
268      FREE(orgVars);
269      FREE(auxVars);
270
271      SpfdNodeSetLocalAlt(applData,regNode,localAlt);
272    } else {
273      array_free(faninBdds);
274      array_free(faninNodes);
275    }
276
277    /* Compute the global function (only if it is needed, i.e, it is
278       present in the nodeCountTable) implemented by the alternate
279       function, localAlt, chosen from the SPFD. */
280    localAlt = SpfdNodeReadLocalAlt(applData,regNode);
281    if (st_lookup(nodeCountTable,(char *)regNode,&count) &&
282        !Ntk_NodeTestIsPrimaryInput(regNode) &&
283        !Ntk_NodeTestIsPrimaryOutput(regNode)) {
284      int size,id;
285      bdd_node **composeBdds;
286     
287      size = bdd_num_vars(ddManager);;
288      composeBdds = ALLOC(bdd_node *,size);
289      for (k = 0; k < size; k++) {
290        composeBdds[k] = bdd_bdd_ith_var(ddManager,k);
291      }
292
293      /* Here I don't have to worry about checking if a wire is redundant. The
294         localAlt of the node already is independent of source node of that
295         wire and so composing with the source node does not matter. But I do
296         need to check for wire replacement. */
297      Ntk_NodeForEachFanin(regNode,k,fanin) {
298        if (st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
299            st_lookup(sinkTable,(char *)fanin,&newFanin)) {
300          id = Ntk_NodeReadMddId(newFanin);
301          globalAlt = SpfdNodeReadGlobalAlternative(applData,newFanin);
302          composeBdds[id] = globalAlt;
303        } else {
304          id = Ntk_NodeReadMddId(fanin);
305          globalAlt = SpfdNodeReadGlobalAlternative(applData,fanin);
306          if (globalAlt) {
307            composeBdds[id] = globalAlt;
308          } else {
309            st_lookup(currBddReq,(char *)fanin,(char **)&composeBdds[id]);
310          }       
311        }
312      }
313      localAlt = SpfdNodeReadLocalAlt(applData,regNode);
314      bdd_ref(globalAlt = bdd_bdd_vector_compose(ddManager,localAlt,
315                                                 composeBdds));
316      SpfdNodeSetGlobalAlternative(applData,regNode,globalAlt);
317      FREE(composeBdds);
318    }
319
320    /* Delete the global BDDs of fanin nodes if unnecessary */
321    Ntk_NodeForEachFanin(regNode,k,fanin) {
322      int *count;
323      if (st_lookup(nodeCountTable,(char *)fanin,&count)) {
324        (*count)--;
325        if (*count == 0) {
326          st_delete(currBddReq,&fanin,&bdd1);
327          bdd_recursive_deref(ddManager,bdd1);
328          SpfdNodeDeleteGlobalAlternative(applData,fanin);
329          st_delete(nodeCountTable,&fanin,&count);
330          FREE(count);
331        }
332      }
333    }
334
335    /* Finally, delete the redundant wires */
336    nodeArray = array_dup(Ntk_NodeReadFanins(regNode));
337    arrayForEachItem(Ntk_Node_t *,nodeArray,j,fanin) {
338      /* If a particular wire is redundant, make the sink node independent of
339         the source node. */
340      if (st_lookup(wireTable,(char *)fanin,&sinkTable) &&
341          st_lookup(sinkTable,(char *)regNode,&dummy)) {
342        /* remove the wire from the wireTable */
343        st_delete(sinkTable,&regNode,&dummy);
344        if (st_count(sinkTable) == 0) {
345          st_delete(wireTable,&fanin,&sinkTable);
346          st_free_table(sinkTable);
347        }
348        SpfdNetworkRemoveWire(network,fanin,regNode);
349      } else if (st_lookup(replaceTable,(char *)regNode,&sinkTable) &&
350                 st_lookup(sinkTable,(char *)fanin,&newFanin)) {
351        /* In this case I do not clean replaceTable as was done for
352           wireTable. The table is needed later. */
353        /* Add the new wire first and then remove the old wire. This
354           way the source node of the new wire will not be deleted if
355           it initially had a fanout of 1 and was in the TFI of the
356           old wire. newsource --> fanin --> regNode. If 'fanin' has
357           only one fanout then its entire TFI will be deleted, hence,
358           possibly deleteing newsource from the network. */
359        SpfdNetworkAddWire(network,newFanin,regNode);
360        SpfdNetworkRemoveWire(network,fanin,regNode);
361      }
362    }
363    array_free(nodeArray);
364   
365    /* Reprogram the node's table data structure. */
366    localAlt = SpfdNodeReadLocalAlt(applData,regNode);
367    SpfdReprogramNode(network,applData,regNode);
368    SpfdNodeDeleteLocalAlt(applData,regNode);
369  }
370
371  /* nodeCountTable need not be empty at this time as some wire may be
372     removed and the count is not reduced appropriately in nodeCountTable.
373     So, delete them explicitly. Defensive programming. */
374  st_foreach_item(nodeCountTable,stGen,&regNode,&count) {
375    st_delete(currBddReq,&regNode,&bdd1);
376    bdd_recursive_deref(ddManager,bdd1);
377    SpfdNodeDeleteGlobalAlternative(applData,regNode);
378    FREE(count);
379  }
380  st_free_table(nodeCountTable);
381 
382  /* Just reusing variable bound */
383  bound = st_count(currBddReq);
384  assert(bound == 0);
385  st_free_table(applData->currBddReq);
386  applData->currBddReq = NIL(st_table);
387 
388  return;
389} /* End of SpfdReprogramRegionNodes */
390
391
392/**Function********************************************************************
393
394  Synopsis [Update the regNode's Table data structure based on the
395  alternate implementation chosen for it in SpfdReprogramRegionNodes.]
396
397  SideEffects        [None]
398
399******************************************************************************/
400void
401SpfdReprogramNode(
402  Ntk_Network_t *network,
403  SpfdApplData_t *applData,
404  Ntk_Node_t *regNode)
405{
406  bdd_node *localAlt;
407  bdd_node *bdd1,*bdd0;
408  bdd_manager *ddManager = applData->ddManager;
409  graph_t *partition = (graph_t *) Ntk_NetworkReadApplInfo(
410    network,PART_NETWORK_APPL_KEY);
411  Tbl_Table_t *table;
412  vertex_t *vertexPtr;
413  Mvf_Function_t *mvf;
414  mdd_t *tempMdd;
415   
416  /* Extract old local function from the partition */
417  vertexPtr = Part_PartitionFindVertexByMddId(partition,
418                                              Ntk_NodeReadMddId(regNode));
419  mvf = Part_VertexReadFunction(vertexPtr);
420  /* First delete the old mvf */
421  Mvf_FunctionFree(mvf);
422 
423  /* Steps to reprogram the node.  1. Delete the old table associated with
424   * this node. The table can be deleted because in BLIF format tables have
425   * only a single output unlike BLIF-MV.  2. Create a new table and set it
426   * in the node.  3. Update the new local function in the partition */
427  table = Ntk_NodeReadTable(regNode);
428  Tbl_TableFree(table);
429     
430  bdd_ref(localAlt = SpfdNodeReadLocalAlt(applData,regNode));
431
432  /* If pattern simulation is performed, update node's static
433     probability and transition probability */
434  if (spfdPerfSim) {
435    float prob;
436    prob = Truesim_BddNodeComputeProbability(network,localAlt);
437    Truesim_NetworkSetNodeStaticProb(network,regNode,prob);
438    Truesim_NetworkSetNodeSwitchingProb(network,regNode,2*prob*(1-prob));
439  }
440 
441  /* Create the new table */
442  tempMdd = bdd_construct_bdd_t(ddManager,localAlt);
443  table = BuildNewTable(network,regNode,tempMdd);
444  Ntk_NodeSetTable(regNode,table);
445  mdd_free(tempMdd);
446     
447  /* Compute the node's new MVF and set it in the partition. */
448  mvf = array_alloc(bdd_t *,2);
449  bdd_ref(bdd1 = SpfdNodeReadLocalAlt(applData,regNode));
450  bdd_ref(bdd0 = bdd_not_bdd_node(bdd1));
451  array_insert(bdd_t *,mvf,0,bdd_construct_bdd_t(ddManager,bdd0));
452  array_insert(bdd_t *,mvf,1,bdd_construct_bdd_t(ddManager,bdd1));
453  Part_VertexSetFunction(vertexPtr,mvf);
454
455  return;
456} /* End of SpfdReprogramNode */
457
458
459/**Function********************************************************************
460
461  Synopsis    [Remove the wire from --> to.]
462
463  SideEffects [None]
464
465******************************************************************************/
466void
467SpfdNetworkRemoveWire(
468  Ntk_Network_t *network,
469  Ntk_Node_t *from,
470  Ntk_Node_t *to)
471{
472  SpfdApplData_t *applData;
473  st_table *wiresRemoved;
474  st_table *sinkTable;
475  array_t *oldFanouts,*oldFanins;
476  array_t *newFanouts,*newFanins;
477  int i;
478  Ntk_Node_t *ntkNode;
479
480  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
481                                                        SPFD_NETWORK_APPL_KEY);
482  wiresRemoved = applData->wiresRemoved;
483 
484  assert(network == Ntk_NodeReadNetwork(from));
485  assert(network == Ntk_NodeReadNetwork(to));
486
487  oldFanouts = Ntk_NodeReadFanouts(from);
488  oldFanins = Ntk_NodeReadFanins(to);
489
490  newFanouts = array_alloc(Ntk_Node_t *,0);
491  newFanins = array_alloc(Ntk_Node_t *,0);
492
493  /* Remove 'from' from the fanins of 'to' */
494  if (spfdVerbose > 1)
495    (void) fprintf(vis_stdout,"** spfd info: Wire ");
496  arrayForEachItem(Ntk_Node_t *,oldFanins,i,ntkNode) {
497    if (ntkNode != from) {
498      array_insert_last(Ntk_Node_t *,newFanins,ntkNode);
499    } else {
500      if (spfdVerbose > 1)
501        (void) fprintf(vis_stdout,"%s --> ",Ntk_NodeReadName(from));
502    }
503  }
504  /* Remove 'to' from the fanouts of 'from' */
505  arrayForEachItem(Ntk_Node_t *,oldFanouts,i,ntkNode) {
506    if (ntkNode != to) {
507      array_insert_last(Ntk_Node_t *,newFanouts,ntkNode);
508    } else {
509      if (spfdVerbose > 1)
510        (void) fprintf(vis_stdout,"%s removed.\n",Ntk_NodeReadName(to));
511    }
512  }
513 
514  /* Insert this wire in the wiresRemoved table */
515  if (st_lookup(wiresRemoved,(char *)from,&sinkTable)) {
516    st_insert(sinkTable,(char *)to,(char *)to);
517  } else {
518    sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
519    st_insert(sinkTable,(char *)to,(char *)to);
520    st_insert(wiresRemoved,(char *)from,(char *)sinkTable);
521  }
522 
523  /* Set the new arrays */
524  Ntk_NodeSetFanins(to,newFanins);
525  Ntk_NodeSetFanouts(from,newFanouts);
526
527  /* The fanin cone is redundant if 'from' had only a single fanout and it is
528     not a primary output. */
529  if (array_n(newFanouts) == 0 &&
530      !Ntk_NodeTestIsPrimaryOutput(from)) {
531    array_t *faninArray;
532    boolean check;
533    faninArray = array_dup(Ntk_NodeReadFanins(from));
534    arrayForEachItem(Ntk_Node_t *,faninArray,i,ntkNode) {
535      SpfdNetworkRemoveWire(network,ntkNode,from);
536      /* Register the wire removed */
537      if (st_lookup(wiresRemoved,(char *)ntkNode,&sinkTable)) {
538        st_insert(sinkTable,(char *)from,(char *)from);
539      } else {
540        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
541        st_insert(sinkTable,(char *)from,(char *)from);
542        st_insert(wiresRemoved,(char *)ntkNode,(char *)sinkTable);
543      }
544    }
545    array_free(faninArray);
546    check = Ntk_NodeRemoveFromNetwork(network,from,0,1,0);
547    assert(check);
548    if (spfdVerbose > 1)
549      (void) fprintf(vis_stdout,"** spfd info: Node %s removed.\n",
550                     Ntk_NodeReadName(from));   
551    st_insert(applData->nodesRemoved,(char *)from,(char *)0);
552  }
553
554  spfdNtkChanged = TRUE;
555 
556  return;
557 
558} /* End of SpfdNetworkRemoveWire */
559
560
561/**Function********************************************************************
562
563  Synopsis    [Add a wire from --> to]
564
565  SideEffects [None]
566
567******************************************************************************/
568void
569SpfdNetworkAddWire(
570  Ntk_Network_t *network,
571  Ntk_Node_t *from,
572  Ntk_Node_t *to)
573{
574  array_t *oldFanouts,*oldFanins;
575
576  assert(network == Ntk_NodeReadNetwork(from));
577  assert(network == Ntk_NodeReadNetwork(to));
578
579  oldFanouts = Ntk_NodeReadFanouts(from);
580  oldFanins = Ntk_NodeReadFanins(to);
581
582  array_insert_last(Ntk_Node_t *,oldFanouts,to);
583  array_insert_last(Ntk_Node_t *,oldFanins,from);
584
585  if (spfdVerbose > 1)
586    (void) fprintf(vis_stdout,"** spfd info: Wire %s --> %s added\n",
587                   Ntk_NodeReadName(from),Ntk_NodeReadName(to));
588  spfdWiresAdded++;
589 
590  spfdNtkChanged = TRUE;
591 
592  return;
593 
594} /* End of SpfdNetworkAddWire */
595
596
597/*---------------------------------------------------------------------------*/
598/* Definition of static functions                                            */
599/*---------------------------------------------------------------------------*/
600
601/**Function********************************************************************
602
603  Synopsis [Update the Table data structure of ntkNode. See tbl
604  package for more details on the Table data structure.]
605
606  SideEffects        [None]
607
608******************************************************************************/
609static Tbl_Table_t *
610BuildNewTable(
611  Ntk_Network_t *network,
612  Ntk_Node_t *ntkNode,
613  mdd_t *mddFunc)
614{
615  bdd_manager *ddManager = Ntk_NetworkReadMddManager(network);
616  SpfdApplData_t *applData;
617  st_table *wiresRemoved;
618  Tbl_Table_t *table;
619  Tbl_Entry_t *entry;
620  int i,id,index;
621  Ntk_Node_t *loopNode;
622  Var_Variable_t *var;
623  array_t *faninIdArray,*cube,*nodeArray;
624  st_table *faninTable;
625  bdd_gen *ddGen;
626
627  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
628                                                        SPFD_NETWORK_APPL_KEY);
629  wiresRemoved = applData->wiresRemoved;
630
631  /* Allocaet a Table data structure */
632  table = Tbl_TableAlloc();
633
634  /* Find the true support. */
635  faninIdArray = mdd_get_support(ddManager,mddFunc);
636  faninTable = st_init_table(st_numcmp,st_numhash);
637  arrayForEachItem(int,faninIdArray,i,id) {
638    st_insert(faninTable,(char *)(long)id,(char *)(long)id);
639  }
640  array_free(faninIdArray);
641 
642  /* Delete wires that are not in the support of ntkNode. Collect
643     valid fanin ids in the same order as already present in the
644     node's original Table data structure. */
645  faninIdArray = array_alloc(int,0);
646  nodeArray = array_dup(Ntk_NodeReadFanins(ntkNode));
647  index = 0;
648  arrayForEachItem(Ntk_Node_t *,nodeArray,i,loopNode) {
649    id = Ntk_NodeReadMddId(loopNode);
650    if (!st_lookup(faninTable,(char *)(long)id,&id)) {
651      st_table *sinkTable;
652
653      if (spfdVerbose > 2)
654        (void) fprintf(vis_stdout,
655                       "** spfd info: removing wire in BuildNewTable.\n");
656      SpfdNetworkRemoveWire(network,loopNode,ntkNode);
657      /* Insert the wire removed for the purpose of statistics */
658      if (st_lookup(wiresRemoved,(char *)loopNode,&sinkTable)) {
659        st_insert(sinkTable,(char *)ntkNode,(char *)ntkNode);
660      } else {
661        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
662        st_insert(sinkTable,(char *)ntkNode,(char *)ntkNode);
663        st_insert(wiresRemoved,(char *)loopNode,(char *)sinkTable);
664      }
665    } else {
666      var = Ntk_NodeReadVariable(loopNode); 
667      array_insert_last(int,faninIdArray,id);
668      Tbl_TableSetVar(table,index,var,0);
669      index++;
670    }
671  }
672  array_free(nodeArray);
673  st_free_table(faninTable);
674 
675  /* Set the output variable */
676  var = Ntk_NodeReadVariable(ntkNode);
677  Tbl_TableSetVar(table,0,var,1/*output flag*/);
678
679  /* Set the defaults field to 0 */
680  entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
681  Tbl_EntrySetValue(entry,0,0);
682  Tbl_TableDefaultSetEntry(table,entry,0/*output index */);
683
684  /* Add rows for each cube in the function */
685  /* cube is an array of int ids. The length of cube is the size of
686     the manager */
687  ddGen = bdd_first_cube(mddFunc,&cube);
688  /* If the function is zero, just add the zero cube */
689  if (bdd_gen_read_status(ddGen) == bdd_EMPTY) {
690    array_t *zeroCube;
691    int size;
692
693    size = bdd_num_vars(ddManager);
694    zeroCube = array_alloc(int,0);
695    for (i = 0; i < size; i++) {
696      array_insert_last(int,zeroCube,2);
697    }
698    TableAddCube(table,faninIdArray,zeroCube,0);
699    array_free(zeroCube);
700  } else {
701    do {
702      TableAddCube(table,faninIdArray,cube,1);
703    } while (bdd_next_cube(ddGen,&cube));
704  } 
705  bdd_gen_free(ddGen);
706
707  array_free(faninIdArray);
708
709  return table;
710} /* End of BuildNewTable */
711
712
713/**Function********************************************************************
714
715  Synopsis [convert a cube into a row entry of the Table. See tbl
716  package for more details.]
717
718  SideEffects        [None]
719
720******************************************************************************/
721static void
722TableAddCube(
723  Tbl_Table_t *table,
724  array_t *faninIdArray,
725  array_t *cube,
726  int value)
727{
728  int rowIndex,colIndex,numFanins;
729  int mddId,phase;
730  Tbl_Entry_t *entry;
731
732  numFanins = Tbl_TableReadNumInputs(table);
733
734  /* Fill in the entries for the just added row */
735  rowIndex = Tbl_TableAddRow(table);
736  for (colIndex = 0; colIndex < numFanins; colIndex++) {
737    entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
738    mddId = array_fetch(int,faninIdArray,colIndex);
739    phase = array_fetch(int,cube,mddId);
740    if (phase == 2) {
741      Tbl_EntrySetValue(entry,0,1);
742    } else {
743      Tbl_EntrySetValue(entry,phase,phase);
744    }
745    Tbl_TableSetEntry(table,entry,rowIndex,colIndex,0/*input flag*/);
746  }
747  /* Add an entry in the output column */
748  entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
749  Tbl_EntrySetValue(entry,value,value);
750  Tbl_TableSetEntry(table,entry,rowIndex,0,1/*output flag*/);
751
752} /* End of TableAddCube */
Note: See TracBrowser for help on using the repository browser.