source: vis_dev/vis-2.3/src/ntmaig/ntmaig.c @ 97

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

vis2.3

  • Property svn:executable set to *
File size: 20.2 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ntmaig.c]
4
5  PackageName [ntmaig]
6
7  Synopsis    [Routines to build mAigs from a network.]
8
9  Author      [Mohammad Awedh]
10
11  Copyright [ This file was created at the University of Colorado at
12  Boulder.  The University of Colorado at Boulder makes no warranty
13  about the suitability of this software for any purpose.  It is
14  presented on an AS IS basis.]
15
16******************************************************************************/
17
18#include "ntmaigInt.h"
19#include "baig.h"
20
21static char rcsid[] UNUSED = "$Id: ntmaig.c,v 1.15 2005/04/28 08:54:35 bli Exp $";
22
23/**AutomaticStart*************************************************************/
24
25/*---------------------------------------------------------------------------*/
26/* Static function prototypes                                                */
27/*---------------------------------------------------------------------------*/
28
29static MvfAig_Function_t * NodeBuildMvfAigRecursively(Ntk_Node_t * node, st_table * leaves, st_table * nodeToMvfTable, mAig_Manager_t *manager);
30static MvfAig_Function_t * NodeBuildInputMvfAig(mAig_Manager_t *manager, Ntk_Node_t * node);
31static MvfAig_Function_t * NodeBuildPseudoInputMvfAigNew(mAig_Manager_t *manager, Ntk_Node_t * node);
32/*static MvfAig_Function_t * NodeBuildPseudoInputMvfAig(mAig_Manager_t *manager, Ntk_Node_t * node);*/
33static MvfAig_Function_t * NodeBuildConstantMvfAig(Ntk_Node_t * node, int constantValue, mAig_Manager_t *manager);
34static MvfAig_Function_t * NodeBuildInternalMvfAig(Ntk_Node_t * node, st_table * leaves, st_table * nodeToMvfAigTable, mAig_Manager_t *manager);
35static MvfAig_Function_t * NodeReadMvfAig(Ntk_Node_t * node, st_table * nodeToMvfAigTable);
36static void NodeSetMvfAig(Ntk_Node_t * node, st_table * nodeToMvfAigTable, MvfAig_Function_t * MvfAig);
37static void RegionInitializeReferenceCounts(array_t *roots, st_table *leaves);
38static void NodeDecrementRefCount(Ntk_Node_t *node, st_table *nodeToMvfTable);
39
40/**AutomaticEnd***************************************************************/
41
42
43/*---------------------------------------------------------------------------*/
44/* Definition of exported functions                                          */
45/*---------------------------------------------------------------------------*/
46
47/**Function********************************************************************
48
49  Synopsis    [Builds multi-valued functions for roots, in terms of leaves.]
50
51  Description [Takes an array of root nodes and a table of leaf nodes, and
52  builds the multi-valued functions (MvfAigs) for the roots in terms of the
53  leaves. This function returns an array of MvfAig_Function_t*, in one-to-one
54  correspondence with the roots array.  It is assumed that every path, from a
55  root backwards to a combinational input, passes through a node in the leaves
56  table, and that there are no combinational cycles within the region defined
57  by the roots and leaves. Also, it is assumed that every node in the leaves
58  table already has an mAig Id.<p>
59
60  A leaf that is a primary input, latch, or combinational node, is treated as
61  a "free" input (i.e. can assume any value in its domain). A leaf that is a
62  pseudo input can assume only those values for which it was specified.<p>
63
64  The leaves table maps nodes (Ntk_Node_t*) to integers.  If the value
65  corresponding to a leaf is ntmaig_UNUSED, then the MvfAig for the leaf is built
66  as described above.  However, the value can be specified as the index of
67  some value in the domain of the variable of the leaf.  For example, if leaf
68  node x can take values (RED, GREEN, BLUE), then the value 1 refers to GREEN.
69  In this case, the MvfAig built for x is simply the constant MvfAig representing
70  This feature can be used to evaluate the MvfAigs of the roots on a minterm, or
71  partial minterm, over the leaves.<p>
72
73  nodeToMvfAigTable is a table mapping nodes to MvfAig_Function_t's (for nodes for
74  which MvfAig_Function's have already been built); Call NodeBuildMvfAigRecursively
75  on the roots. Free MvfAig's at internal nodes ASAP, so no excessive storage.]
76
77  SideEffects []
78******************************************************************************/
79array_t *
80ntmaig_NetworkBuildMvfAigs(
81  Ntk_Network_t * network,
82  array_t       * roots,
83  st_table      * leaves)
84{
85  int               i;
86  MvfAig_Function_t *MvfAig;
87  st_table          *nodeToMvfAigTable;  /* mapes each node with its mvfAig */
88  int                numRoots = array_n(roots);
89  array_t           *result   = array_alloc(MvfAig_Function_t *, numRoots);
90  mAig_Manager_t    *manager  = Ntk_NetworkReadMAigManager(network);
91  MvfAig_Function_t *tmpMvf;
92
93 
94  /*
95   * Before initializing the reference counts, verify that the leaves form a
96   * support set for the roots.
97   */
98  if (!Ntk_NetworkTestLeavesCoverSupportOfRoots(network, roots, leaves)) {
99    fail("Leaves do not cover support of roots");
100  }
101  /*
102   * Each node in the region defined by the roots and leaves is assigned a
103   * reference count equaling the number of fanouts within the region.  As a
104   * special case, the roots are initialized to MAX_INT.
105   */
106  RegionInitializeReferenceCounts(roots, leaves);
107  /*
108   * For each root, compute its MvfAig and store a duplicate copy of it in the
109   * result array. The nodeToMvfAigTable is used to keep track of intermediate
110   * computations. Intermediate MvfAigs are freed as soon as possible by using
111   * the reference count mechanism.
112   */
113  nodeToMvfAigTable = (st_table *) Ntk_NetworkReadApplInfo(network, MVFAIG_NETWORK_APPL_KEY);
114  if (nodeToMvfAigTable == NIL(st_table)){
115    nodeToMvfAigTable = st_init_table(st_ptrcmp, st_ptrhash);
116    /* Register the MvfAig Table in the network*/
117    Ntk_NetworkAddApplInfo(network, MVFAIG_NETWORK_APPL_KEY,
118                         (Ntk_ApplInfoFreeFn) ntmAig_MvfAigTableFreeCallback,
119                         (void *) nodeToMvfAigTable);
120  }
121  for (i = 0; i < numRoots; i++) {
122    Ntk_Node_t        *root   = array_fetch(Ntk_Node_t *, roots, i);
123    tmpMvf = NodeBuildMvfAigRecursively(root, leaves,
124                                     nodeToMvfAigTable, manager);
125    MvfAig = MvfAig_FunctionDuplicate(tmpMvf);
126    array_insert(MvfAig_Function_t *, result, i, MvfAig);
127  }
128
129  return result;
130}
131
132/**Function********************************************************************
133
134  Synopsis    [Call-back function to free a MvfAig Table.]
135
136  Description [This function will be stored in the network together with the
137  pointer to the MvfAig Table. Whenever the network deletes the MvfAig
138  information, this function is called and it will free the table and
139  the information attached to it.]
140
141  SideEffects []
142
143  SeeAlso     [Ntk_NetworkAddApplInfo]
144
145******************************************************************************/
146void
147ntmAig_MvfAigTableFreeCallback(
148   void *data)
149{
150  st_generator      *stGen;
151  MvfAig_Function_t *MvfAig;
152  Ntk_Node_t        *node;
153  st_table          *nodeToMvfAigTable = (st_table*) data;
154
155  st_foreach_item(nodeToMvfAigTable, stGen,  &node,  &MvfAig) {
156    MvfAig_FunctionFree(MvfAig);
157  }
158  st_free_table(nodeToMvfAigTable);
159} /* End of ntmAig_MvfAigTableFreeCallback */
160
161
162/*---------------------------------------------------------------------------*/
163/* Definition of internal functions                                          */
164/*---------------------------------------------------------------------------*/
165
166
167/*---------------------------------------------------------------------------*/
168/* Definition of static functions                                            */
169/*---------------------------------------------------------------------------*/
170
171
172/**Function********************************************************************
173
174  Synopsis    [Builds MvfAig for a node, recursively in terms of fanins.]
175
176  Description [Recursively builds MvfAig_Functions_t's. Base cases - input nodes,
177  latch nodes, constant nodes, pseudo inputs, and leaf nodes. Fail if a
178  combinational input is reached that is not in leaves.  In the case that the
179  node is combinational, and in the leaves, we treat it as an input.  When
180  it's a pseudo input, we treat it as taking only values designated in table.]
181
182  SideEffects []
183
184  SeeAlso     [NodeBuildInputMvfAig,NodeBuildPseudoInputMvfAig,NodeBuildInternalMvfAig]
185[Done]
186******************************************************************************/
187static MvfAig_Function_t *
188NodeBuildMvfAigRecursively(
189  Ntk_Node_t * node,
190  st_table * leaves,
191  st_table * nodeToMvfTable,
192  mAig_Manager_t *manager)
193{
194  MvfAig_Function_t *MvfAig = NodeReadMvfAig(node, nodeToMvfTable);
195 
196  /* If the MvfAig for this node has already been computed, then just return it. */
197
198  if (MvfAig != NIL(MvfAig_Function_t)) {
199    return MvfAig;
200  }
201  if (Ntk_NodeTestIsConstant(node)) {
202    /* Doesn't matter if constant is a leaf or not. */
203    MvfAig = NodeBuildConstantMvfAig(node, ntmaig_UNUSED, manager);
204  }
205  else {
206    int constValue;
207 
208    if (st_lookup_int(leaves,  node, &constValue)) { 
209      if (constValue == ntmaig_UNUSED) {
210        /* Node is a leaf. */
211        if ((Ntk_NodeTestIsPrimaryInput(node)) ||
212            (Ntk_NodeTestIsLatch(node)) ||
213            (Ntk_NodeTestIsCombinational(node))) {
214          /* Node can assume any value. */
215          MvfAig = NodeBuildInputMvfAig(manager, node);
216        }
217        else if (Ntk_NodeTestIsPseudoInput(node)) {
218          /* Node may assume only a subset of possible values. */
219          MvfAig = NodeBuildPseudoInputMvfAigNew(manager, node);
220        }
221        else {
222          fail("Encountered unknown type in MvfAig recursion\n");
223        }
224      }
225      else {
226        /* treat the leaf node as being a constant taking the value constValue */
227        MvfAig = NodeBuildConstantMvfAig(node, constValue, manager);
228      }
229    }
230    else {
231
232      /* Node is not a leaf.  If it is a combinational input, then fail. */
233      if (Ntk_NodeTestIsCombInput(node)) {
234        fail("Encountered combinational input not in leaves table\n");
235      }
236      else {
237        MvfAig = NodeBuildInternalMvfAig(node, leaves, nodeToMvfTable, manager);
238      }
239    }
240  }
241  NodeSetMvfAig(node, nodeToMvfTable, MvfAig);
242  return MvfAig;
243
244}
245
246
247/**Function********************************************************************
248
249  Synopsis  [Builds MvfAig for a node that is treated as a free input.]
250
251  SideEffects []
252[Done]
253******************************************************************************/
254static MvfAig_Function_t *
255NodeBuildInputMvfAig(
256  mAig_Manager_t *manager,
257  Ntk_Node_t * node)
258{
259  int mAigId = Ntk_NodeReadMAigId(node);
260
261  assert(mAigId != NTK_UNASSIGNED_MAIG_ID);
262  return MvfAig_FunctionCreateFromVariable(manager, mAigId);
263}
264
265/**Function********************************************************************
266
267  Synopsis    [Builds MvfAig for a node that is a pseudo input.]
268
269  Description [Builds MvfAig for a node that is a pseudo input.  This node has
270  a single output and no inputs. Its table has several row entries.  We build
271  an MvfAig whose components correspond exactly to possible table outputs.]
272
273  SideEffects []
274
275 Comment [Although pseudo inputs, constants, and internal nodes all have
276  tables, a single procedure cannot be used to build their MvfAig.  A pseudo
277  input MvfAig is built in terms of its mddId, whereas a constant or internal is
278  not.  A constant or pseudo input doesn't have any inputs, whereas an
279  internal does.]
280 
281  SeeAlso     [Tbl_TableBuildMvfAigForNonDetConstant]
282[Done]
283******************************************************************************/
284static MvfAig_Function_t *
285NodeBuildPseudoInputMvfAigNew(
286  mAig_Manager_t *manager,
287  Ntk_Node_t * node)
288{
289  int lIndex=0, needProcess, i;
290  mAigEdge_t  mAig, tmpAig;
291  MvfAig_Function_t *MvfAig;
292  int                columnIndex = Ntk_NodeReadOutputIndex(node);
293  Tbl_Table_t       *table       = Ntk_NodeReadTable(node);
294  int                mAigId      = Ntk_NodeReadMAigId(node);
295
296  assert(mAigId != NTK_UNASSIGNED_MAIG_ID);
297  MvfAig = Tbl_TableBuildNonDetConstantMvfAig(table, columnIndex,
298mAigId,
299                                              manager);
300  needProcess = 0;
301  tmpAig = mAig_Zero;
302  for(i=0; i<MvfAig->num; i++) {
303    mAig = array_fetch(mAigEdge_t, MvfAig, i);
304    if(mAig == tmpAig) {
305      needProcess = 1;
306    }
307    else {
308      lIndex = i;
309    }
310  }
311  if(needProcess) {
312    for(i=0; i<lIndex; i++) {
313      mAig   = array_fetch(mAigEdge_t, MvfAig, i);
314      tmpAig = mAig_Or(manager, tmpAig, mAig);
315    }
316    array_insert(mAigEdge_t, MvfAig, lIndex, mAig_Not(tmpAig));
317  }
318 
319  return MvfAig;
320}
321
322/**Function********************************************************************
323
324  Synopsis    [Builds MvfAig for a node that is a pseudo input.]
325
326  Description [Builds MvfAig for a node that is a pseudo input.  This node has a
327  single output and no inputs. Its table has several row entries.  We build an
328  MvfAig whose components correspond exactly to possible table outputs.]
329
330  SideEffects []
331
332  Comment [Although pseudo inputs, constants, and internal nodes all have
333  tables, a single procedure cannot be used to build their MvfAig.  A pseudo
334  input MvfAig is built in terms of its mddId, whereas a constant or internal is
335  not.  A constant or pseudo input doesn't have any inputs, whereas an
336  internal does.]
337 
338  SeeAlso     [Tbl_TableBuildMvfAigForNonDetConstant]
339[Done]
340******************************************************************************/
341/*static MvfAig_Function_t *
342NodeBuildPseudoInputMvfAig(
343  mAig_Manager_t *manager,
344  Ntk_Node_t * node)
345{
346  MvfAig_Function_t *MvfAig;
347  int                columnIndex = Ntk_NodeReadOutputIndex(node);
348  Tbl_Table_t       *table       = Ntk_NodeReadTable(node);
349  int                mAigId      = Ntk_NodeReadMAigId(node);
350
351  assert(mAigId != NTK_UNASSIGNED_MAIG_ID);
352  MvfAig = Tbl_TableBuildNonDetConstantMvfAig(table, columnIndex, mAigId, manager);
353  return MvfAig;
354}*/
355
356
357/**Function********************************************************************
358
359  Synopsis [Builds MvfAig for a node with no inputs, and only one row in its
360  table.]
361
362  Description [Builds MvfAig for a constant.  If constantValue is ntmaig_UNUSED,
363  then constantValue should be a legal index in the domain of the variable of
364  node. In this case, regardless of the type of the node, an MvfAig is built
365  where the component indexed by constantValue is one (i.e. the tautology) and
366  all other components are zero.<p>
367
368  If constantValue is not ntmaig_UNUSED, then node should be a constant,
369  combinational node.  In this case, an MvfAig is built with a single component
370  (indexed by the value of node) is one, and all other components are zero.]
371
372  SideEffects []
373[Done]
374******************************************************************************/
375static MvfAig_Function_t *
376NodeBuildConstantMvfAig(
377  Ntk_Node_t * node,
378  int constantValue,
379  mAig_Manager_t *manager)
380{
381  int             value        = 0; /* initialized to stop lint complaining */
382  Var_Variable_t *variable     = Ntk_NodeReadVariable(node);
383  int             numVarValues = Var_VariableReadNumValues(variable);
384  MvfAig_Function_t *MvfAig    = MvfAig_FunctionAlloc(numVarValues);
385
386  if (constantValue != ntmaig_UNUSED) {
387    /* Use the given value. */
388    assert((constantValue >= 0) && (constantValue < numVarValues));
389    value = constantValue;
390  }
391  else {
392    int          outputIndex = Ntk_NodeReadOutputIndex(node);
393    Tbl_Table_t *table       = Ntk_NodeReadTable(node);
394
395    assert(Ntk_NodeTestIsConstant(node));
396    value = Tbl_TableReadConstValue(table, outputIndex);
397    assert(value != -1);
398  }
399 
400  MvfAig_FunctionAddMintermsToComponent(manager, MvfAig, value, bAig_One);
401  return MvfAig;
402}
403
404
405/**Function********************************************************************
406
407  Synopsis [Builds MvfAig for an internal node in terms of its fanin's MvfAigs.]
408
409  Description [Builds MvfAig for an internal node in terms of its fanin's
410  MvfAigs. An internal node is a node that is in the transitive fanin of a root,
411  but is not a leaf.]
412
413  SideEffects []
414[Done]
415******************************************************************************/
416static MvfAig_Function_t *
417NodeBuildInternalMvfAig(
418  Ntk_Node_t * node,
419  st_table   * leaves,
420  st_table   * nodeToMvfAigTable,
421  mAig_Manager_t *manager)
422{
423  int               i;
424  MvfAig_Function_t *resultMvfAig;
425  Ntk_Node_t        *faninNode;
426  array_t           *faninMvfAigs = array_alloc(MvfAig_Function_t *, Ntk_NodeReadNumFanins(node));
427  int               outputIndex   = Ntk_NodeReadOutputIndex(node);
428  Tbl_Table_t       *table        = Ntk_NodeReadTable(node);
429
430  Ntk_NodeForEachFanin(node, i, faninNode) {
431    MvfAig_Function_t *tmpMvfAig = NodeBuildMvfAigRecursively(faninNode, leaves,
432                                                              nodeToMvfAigTable, manager);
433    array_insert(MvfAig_Function_t *, faninMvfAigs, i, tmpMvfAig);
434  }
435  resultMvfAig = Tbl_TableBuildMvfAigFromFanins(table, outputIndex, faninMvfAigs, manager); 
436  Ntk_NodeForEachFanin(node, i, faninNode) {
437    NodeDecrementRefCount(faninNode, nodeToMvfAigTable);
438  }
439  /* Don't free the MvfAigs themselves, but just free the array. */
440  array_free(faninMvfAigs);
441  return resultMvfAig;
442}
443
444
445/**Function********************************************************************
446
447  Synopsis [Returns MvfAig corresponding to a node; returns NIL if node not in
448  table.]
449
450  SideEffects []
451[Done]
452******************************************************************************/
453static MvfAig_Function_t *
454NodeReadMvfAig(
455  Ntk_Node_t * node,
456  st_table   * nodeToMvfAigTable)
457{
458  MvfAig_Function_t *result = NIL(MvfAig_Function_t);
459  st_lookup(nodeToMvfAigTable,  node,  &result);
460
461  return result;
462}
463
464
465/**Function********************************************************************
466
467  Synopsis    [Inserts node and corresponding MvfAig into table.]
468
469  SideEffects []
470[Done]
471******************************************************************************/
472static void
473NodeSetMvfAig(
474  Ntk_Node_t * node,
475  st_table   * nodeToMvfAigTable,
476  MvfAig_Function_t * MvfAig)
477{
478  st_insert(nodeToMvfAigTable,  node,  MvfAig);
479}
480
481/**Function********************************************************************
482
483  Synopsis    [Initializes the reference counts in a region.]
484
485  Description [Initializes the reference counts in the region defined by the
486  roots and leaves.  This region includes the roots, and all nodes in the
487  transitive fanin of the roots up to and including the leaves.  The reference
488  count for a node in the region is set to be the number of fanouts of that
489  node in the region (fanouts to leaf nodes and constant nodes are excluded).
490  Root nodes are set to MAXINT, so that even after some decrements, their ref
491  count won't fall to zero.]
492
493  SideEffects [Uses the undef field of node.]
494
495******************************************************************************/
496static void
497RegionInitializeReferenceCounts(
498  array_t *roots, 
499  st_table *leaves)
500{
501  int           i;
502  Ntk_Node_t   *node;
503  st_generator *stGen;
504  st_table     *regionNodes = Ntk_RegionFindNodes(roots, leaves);
505
506  st_foreach_item(regionNodes, stGen,  &node, NIL(char *)) {
507    Ntk_Node_t *fanoutNode;
508    long        refCount = 0;
509
510    Ntk_NodeForEachFanout(node, i, fanoutNode) {
511      if (st_is_member(regionNodes,  fanoutNode)
512          && !st_is_member(leaves,  fanoutNode)
513          && !Ntk_NodeTestIsConstant(fanoutNode)) {
514        refCount++;
515      }
516    }
517    Ntk_NodeSetUndef(node, (void *) refCount);
518  }
519
520  for(i = 0; i < array_n(roots); i++) {
521    node = array_fetch(Ntk_Node_t *, roots, i);
522    Ntk_NodeSetUndef(node, (char *) MAXINT);
523  }
524
525  st_free_table(regionNodes);
526}
527
528/**Function********************************************************************
529
530  Synopsis    [Decrements the ref count of a node.]
531
532  Description [Decrements the ref count of a node.  If the ref count becomes
533  zero, then remove node from nodeToMvfTable and free the MVF corresponding to
534  node.]
535
536  SideEffects []
537
538******************************************************************************/
539static void
540NodeDecrementRefCount(
541  Ntk_Node_t *node, 
542  st_table *nodeToMvfTable)
543{
544  long              refCount = (long) Ntk_NodeReadUndef(node);
545
546  assert(refCount != 0);
547
548  refCount--;
549  /* 
550    Want to keep the entry of this node, so we may get the MvfAig of this node
551    whenever we need it.  The pointer to the nodeToMvfTable is stored in the network
552    information.
553   */
554  /* 
555  if (refCount == 0) {
556    st_delete(nodeToMvfTable, (char **) &node, (char **) &mvf);
557    MvfAig_FunctionFree(mvf);
558  }
559  */
560  Ntk_NodeSetUndef(node, (void *) refCount);
561}
562
563
564
565
566
567
568
569
570
571
572
573
Note: See TracBrowser for help on using the repository browser.