source: vis_dev/vis-2.3/src/ntm/ntm.c @ 99

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

vis2.3

File size: 24.6 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ntm.c]
4
5  PackageName [ntm]
6
7  Synopsis    [Routines to build MDDs from a network.]
8
9  Author      [Adnan Aziz and Tom Shiple]
10
11  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
12  All rights reserved.
13
14  Permission is hereby granted, without written agreement and without license
15  or royalty fees, to use, copy, modify, and distribute this software and its
16  documentation for any purpose, provided that the above copyright notice and
17  the following two paragraphs appear in all copies of this software.
18
19  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
20  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
21  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22
23  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
24  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
25  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
26  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
27  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
28
29******************************************************************************/
30
31#include "ntmInt.h"
32
33static char rcsid[] UNUSED = "$Id: ntm.c,v 1.11 2009/04/11 01:45:44 fabio Exp $";
34
35/**AutomaticStart*************************************************************/
36
37/*---------------------------------------------------------------------------*/
38/* Static function prototypes                                                */
39/*---------------------------------------------------------------------------*/
40
41static Mvf_Function_t * NodeBuildMvfRecursively(Ntk_Node_t * node, st_table * leaves, st_table * nodeToMvfTable, mdd_manager *mddMgr, mdd_t *careSet);
42static Mvf_Function_t * NodeBuildInputMvf(Ntk_Node_t * node, mdd_manager *mddMgr);
43#if 0
44static Mvf_Function_t * NodeBuildPseudoInputMvf(Ntk_Node_t * node, mdd_manager * mddMgr);
45#endif
46static Mvf_Function_t * NodeBuildPseudoInputMvfNew(Ntk_Node_t * node, mdd_manager * mddMgr);
47static Mvf_Function_t * NodeBuildConstantMvf(Ntk_Node_t * node, int constantValue, mdd_manager *mddMgr);
48static Mvf_Function_t * NodeBuildInternalMvf(Ntk_Node_t * node, st_table * leaves, st_table * nodeToMvfTable, mdd_manager *mddMgr, mdd_t *careSet);
49static Mvf_Function_t * NodeReadMvf(Ntk_Node_t * node, st_table * nodeToMvfTable);
50static void NodeSetMvf(Ntk_Node_t * node, st_table * nodeToMvfTable, Mvf_Function_t * mvf);
51static int CommandNtmTest(Hrc_Manager_t ** hmgr, int argc, char ** argv);
52static void MvfSanityCheck(array_t *roots, array_t *mvfs);
53static void RegionInitializeReferenceCounts(array_t *roots, st_table *leaves);
54static void NodeDecrementRefCount(Ntk_Node_t *node, st_table *nodeToMvfTable);
55static boolean TableTestIsContainedInArray(st_table *table1, array_t *nodeArrary);
56
57/**AutomaticEnd***************************************************************/
58
59
60/*---------------------------------------------------------------------------*/
61/* Definition of exported functions                                          */
62/*---------------------------------------------------------------------------*/
63
64/**Function********************************************************************
65
66  Synopsis    [Initializes the network to MDD package.]
67
68  SideEffects []
69
70  SeeAlso     [Ntm_End]
71
72******************************************************************************/
73void
74Ntm_Init(void)
75{
76  Cmd_CommandAdd("_ntm_test", CommandNtmTest, /* doesn't changes_network */ 0);
77}
78
79
80/**Function********************************************************************
81
82  Synopsis    [Ends the network to MDD package.]
83
84  SideEffects []
85
86  SeeAlso     [Ntm_Init]
87
88******************************************************************************/
89void
90Ntm_End(void)
91{
92}
93
94
95/**Function********************************************************************
96
97  Synopsis    [Builds multi-valued functions for roots, in terms of leaves.]
98
99  Description [Takes an array of root nodes and a table of leaf nodes, and
100  builds the multi-valued functions (MVFs) for the roots in terms of the
101  leaves. This function returns an array of Mvf_Function_t*, in one-to-one
102  correspondence with the roots array.  It is assumed that every path, from a
103  root backwards to a combinational input, passes through a node in the leaves
104  table, and that there are no combinational cycles within the region defined
105  by the roots and leaves. Also, it is assumed that every node in the leaves
106  table already has an MDD id.<p>
107
108  A leaf that is a primary input, latch, or combinational node, is treated as
109  a "free" input (i.e. can assume any value in its domain). A leaf that is a
110  pseudo input can assume only those values for which it was specified.<p>
111
112  The leaves table maps nodes (Ntk_Node_t*) to integers.  If the value
113  corresponding to a leaf is NTM_UNUSED, then the MVF for the leaf is built
114  as described above.  However, the value can be specified as the index of
115  some value in the domain of the variable of the leaf.  For example, if leaf
116  node x can take values (RED, GREEN, BLUE), then the value 1 refers to GREEN.
117  In this case, the MVF built for x is simply the constant MVF representing
118  GREEN. This feature can be used to evaluate the MVFs of the roots on a
119  minterm, or partial minterm, over the leaves.<p>
120
121  This function also takes the MDD careSet as an input.  If this argument is
122  NULL, then it is ignored.  However, if it is not NULL, then all intermediate
123  and final MDDs constructed are minimized with respect to the careSet.  Thus,
124  the MVFs returned by the function may take an arbitrary value outside of the
125  careSet.  This can be useful to keep the MDDs small.]
126
127  Comment [We create a table mapping nodes to Mvf_Function_t's (for nodes for
128  which Mvf_Function's have already been built); Call NodeBuildMvfRecursively
129  on the roots. Free MVF's at internal nodes ASAP, so no excessive storage.]
130
131  SideEffects []
132
133******************************************************************************/
134array_t *
135Ntm_NetworkBuildMvfs(
136  Ntk_Network_t * network,
137  array_t * roots,
138  st_table * leaves,
139  mdd_t *careSet)
140{
141  int             i;
142  st_generator   *stGen;
143  Mvf_Function_t *mvf;
144  Ntk_Node_t     *node;
145  st_table       *nodeToMvfTable;
146  Mvf_Function_t *tmpMvf;
147  int             numRoots = array_n(roots);
148  array_t        *result   = array_alloc(Mvf_Function_t *, numRoots);
149  mdd_manager    *mddMgr   = Ntk_NetworkReadMddManager(network);
150
151  /*
152   * Before initializing the reference counts, verify that the leaves form a
153   * support set for the roots.
154   */
155  if (!Ntk_NetworkTestLeavesCoverSupportOfRoots(network, roots, leaves)) {
156    (void)fprintf(vis_stderr,"%s",error_string());
157    fflush(vis_stderr);
158    fail("Leaves do not cover support of roots");
159  }
160
161  /*
162   * Each node in the region defined by the roots and leaves is assigned a
163   * reference count equaling the number of fanouts within the region.  As a
164   * special case, the roots are initialized to MAX_INT.
165   */
166  RegionInitializeReferenceCounts(roots, leaves);
167
168  /*
169   * For each root, compute its MVF and store a duplicate copy of it in the
170   * result array. The nodeToMvfTable is used to keep track of intermediate
171   * computations. Intermediate MVFs are freed as soon as possible by using
172   * the reference count mechanism.
173   */
174  nodeToMvfTable = st_init_table(st_ptrcmp, st_ptrhash);
175  for (i = 0; i < numRoots; i++) {
176    Ntk_Node_t     *root   = array_fetch(Ntk_Node_t *, roots, i);
177
178    tmpMvf = NodeBuildMvfRecursively(root, leaves,
179                                                     nodeToMvfTable, mddMgr,
180                                                     careSet);
181
182    mvf = Mvf_FunctionDuplicate(tmpMvf);
183    array_insert(Mvf_Function_t *, result, i, mvf);
184  }
185
186  /*
187   * Because of the use of reference counting, the only nodes left in
188   * nodeToMvfTable should be the roots.
189   */
190  assert(TableTestIsContainedInArray(nodeToMvfTable, roots));
191
192  /*
193   * Free the remaining MVFs (corresponding to the roots) from the
194   * nodeToMvfTable.
195   */
196  st_foreach_item(nodeToMvfTable, stGen, &node, &mvf) {
197    Mvf_FunctionFree(mvf);
198  }
199  st_free_table(nodeToMvfTable);
200
201  return result;
202}
203
204/*---------------------------------------------------------------------------*/
205/* Definition of internal functions                                          */
206/*---------------------------------------------------------------------------*/
207
208
209/*---------------------------------------------------------------------------*/
210/* Definition of static functions                                            */
211/*---------------------------------------------------------------------------*/
212
213
214/**Function********************************************************************
215
216  Synopsis    [Builds MVF for a node, recursively in terms of fanins.]
217
218  Description [Recursively builds Mvf_Functions_t's. Base cases - input nodes,
219  latch nodes, constant nodes, pseudo inputs, and leaf nodes. Fail if a
220  combinational input is reached that is not in leaves.  In the case that the
221  node is combinational, and in the leaves, we treat it as an input.  When
222  it's a pseudo input, we treat it as taking only values designated in table.]
223
224  SideEffects []
225
226  SeeAlso     [NodeBuildInputMvf,NodeBuildPseudoInputMvf,NodeBuildInternalMvf]
227
228******************************************************************************/
229static Mvf_Function_t *
230NodeBuildMvfRecursively(
231  Ntk_Node_t * node,
232  st_table * leaves,
233  st_table * nodeToMvfTable,
234  mdd_manager *mddMgr,
235  mdd_t *careSet)
236{
237  Mvf_Function_t *mvf = NodeReadMvf(node, nodeToMvfTable);
238
239
240  /* If the MVF for this node has already been computed, then just return it. */
241  if (mvf != NIL(Mvf_Function_t)) {
242    return mvf;
243  }
244
245
246  if (Ntk_NodeTestIsConstant(node)) {
247    /* Doesn't matter if constant is a leaf or not. */
248    mvf = NodeBuildConstantMvf(node, NTM_UNUSED, mddMgr);
249  }
250
251  else {
252    int constValue;
253    if (st_lookup_int(leaves, (char *) node, &constValue)) {
254
255      if (constValue == NTM_UNUSED) {
256
257        /* Node is a leaf. */
258        if ((Ntk_NodeTestIsPrimaryInput(node)) ||
259            (Ntk_NodeTestIsLatch(node)) ||
260            (Ntk_NodeTestIsCombinational(node))) {
261          /* Node can assume any value. */
262          mvf = NodeBuildInputMvf(node, mddMgr);
263        }
264        else if (Ntk_NodeTestIsPseudoInput(node)) {
265          /* Node may assume only a subset of possible values. */
266          mvf = NodeBuildPseudoInputMvfNew(node, mddMgr);
267        }
268        else {
269          fail("Encountered unknown type in MVF recursion\n");
270        }
271      }
272      else {
273        /* treat the leaf node as being a constant taking the value constValue */
274        mvf = NodeBuildConstantMvf(node, constValue, mddMgr);
275      }
276    }
277    else {
278
279      /* Node is not a leaf.  If it is a combinational input, then fail. */
280      if (Ntk_NodeTestIsCombInput(node)) {
281        fail("Encountered combinational input not in leaves table\n");
282      }
283      else {
284        mvf = NodeBuildInternalMvf(node, leaves, nodeToMvfTable, mddMgr,
285                                   careSet);
286      }
287    }
288  }
289
290  /* Minimize mvf wrt careSet, if careSet is not NULL. */
291  if (careSet != NIL(mdd_t)) {
292    Mvf_Function_t *tempMvf = mvf;
293
294    mvf = Mvf_FunctionMinimize(tempMvf, careSet);
295    Mvf_FunctionFree(tempMvf);
296  }
297  NodeSetMvf(node, nodeToMvfTable, mvf);
298  return mvf;
299
300}
301
302
303/**Function********************************************************************
304
305  Synopsis  [Builds MVF for a node that is treated as a free input.]
306
307  SideEffects []
308
309******************************************************************************/
310static Mvf_Function_t *
311NodeBuildInputMvf(
312  Ntk_Node_t * node,
313  mdd_manager *mddMgr)
314{
315  int mddId = Ntk_NodeReadMddId(node);
316
317  assert(mddId != NTK_UNASSIGNED_MDD_ID);
318  return Mvf_FunctionCreateFromVariable(mddMgr, mddId);
319}
320
321
322/**Function********************************************************************
323
324  Synopsis    [Builds MVF for a node that is a pseudo input.]
325
326  Description [Builds MVF 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  MVF 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 MVF.  A pseudo
334  input MVF 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_TableBuildMvfForNonDetConstant]
339
340******************************************************************************/
341static Mvf_Function_t *
342NodeBuildPseudoInputMvfNew(
343  Ntk_Node_t * node,
344  mdd_manager * mddMgr)
345{
346  mdd_t *vMdd, *tMdd, *rMdd;
347  int lIndex, needProcess, i;
348  Mvf_Function_t *mvf;
349  int             columnIndex = Ntk_NodeReadOutputIndex(node);
350  Tbl_Table_t    *table       = Ntk_NodeReadTable(node);
351  int             mddId       = Ntk_NodeReadMddId(node);
352
353  assert(mddId != NTK_UNASSIGNED_MDD_ID);
354  mvf = Tbl_TableBuildNonDetConstantMvf(table, columnIndex, mddId, mddMgr);
355
356  rMdd = mdd_zero(mddMgr);
357  needProcess = 0;
358  lIndex = 0;
359  for(i=0; i<mvf->num; i++) {
360    vMdd = array_fetch(mdd_t *, mvf, i);
361    if(mdd_equal(vMdd, rMdd)) {
362      needProcess = 1;
363    }
364    else {
365      lIndex = i;
366    }
367  }
368  if(needProcess) {
369    for(i=0; i<lIndex; i++) {
370      vMdd = array_fetch(mdd_t *, mvf, i);
371      tMdd = mdd_or(vMdd, rMdd, 1, 1);
372      mdd_free(rMdd);
373      rMdd = tMdd;
374    }
375    vMdd = array_fetch(mdd_t *, mvf, lIndex);
376    mdd_free(vMdd);
377    tMdd = mdd_not(rMdd);
378    mdd_free(rMdd);
379    array_insert(mdd_t *, mvf, lIndex, tMdd);
380  }
381  else {
382    mdd_free(rMdd);
383  }
384  return mvf;
385}
386
387#if 0
388static Mvf_Function_t *
389NodeBuildPseudoInputMvf(
390  Ntk_Node_t * node,
391  mdd_manager * mddMgr)
392{
393  Mvf_Function_t *mvf;
394  int             columnIndex = Ntk_NodeReadOutputIndex(node);
395  Tbl_Table_t    *table       = Ntk_NodeReadTable(node);
396  int             mddId       = Ntk_NodeReadMddId(node);
397
398  assert(mddId != NTK_UNASSIGNED_MDD_ID);
399  mvf = Tbl_TableBuildNonDetConstantMvf(table, columnIndex, mddId, mddMgr);
400
401  return mvf;
402}
403#endif
404
405
406/**Function********************************************************************
407
408  Synopsis [Builds MVF for a node with no inputs, and only one row in its
409  table.]
410
411  Description [Builds MVF for a constant.  If constantValue is NTM_UNUSED,
412  then constantValue should be a legal index in the domain of the variable of
413  node. In this case, regardless of the type of the node, an MVF is built
414  where the component indexed by constantValue is one (i.e. the tautology) and
415  all other components are zero.<p>
416
417  If constantValue is not NTM_UNUSED, then node should be a constant,
418  combinational node.  In this case, an MVF is built with a single component
419  (indexed by the value of node) is one, and all other components are zero.]
420
421  SideEffects []
422
423******************************************************************************/
424static Mvf_Function_t *
425NodeBuildConstantMvf(
426  Ntk_Node_t * node,
427  int constantValue,
428  mdd_manager *mddMgr)
429{
430  int             value        = 0; /* initialized to stop lint complaining */
431  mdd_t          *oneMdd       = mdd_one(mddMgr);
432  Var_Variable_t *variable     = Ntk_NodeReadVariable(node);
433  int             numVarValues = Var_VariableReadNumValues(variable);
434  Mvf_Function_t *mvf          = Mvf_FunctionAlloc(mddMgr, numVarValues);
435
436
437  if (constantValue != NTM_UNUSED) {
438    /* Use the given value. */
439    assert((constantValue >= 0) && (constantValue < numVarValues));
440    value = constantValue;
441  }
442  else {
443    int          outputIndex = Ntk_NodeReadOutputIndex(node);
444    Tbl_Table_t *table       = Ntk_NodeReadTable(node);
445
446    assert(Ntk_NodeTestIsConstant(node));
447    value = Tbl_TableReadConstValue(table, outputIndex);
448    assert(value != -1);
449  }
450
451  Mvf_FunctionAddMintermsToComponent(mvf, value, oneMdd);
452  mdd_free(oneMdd);
453  return mvf;
454}
455
456
457/**Function********************************************************************
458
459  Synopsis [Builds MVF for an internal node in terms of its fanin's MVFs.]
460
461  Description [Builds MVF for an internal node in terms of its fanin's
462  MVFs. An internal node is a node that is in the transitive fanin of a root,
463  but is not a leaf.]
464
465  SideEffects []
466
467******************************************************************************/
468static Mvf_Function_t *
469NodeBuildInternalMvf(
470  Ntk_Node_t * node,
471  st_table * leaves,
472  st_table * nodeToMvfTable,
473  mdd_manager *mddMgr,
474  mdd_t *careSet)
475{
476  int             i;
477  Mvf_Function_t *resultMvf;
478  Ntk_Node_t     *faninNode;
479  array_t        *faninMvfs   = array_alloc(Mvf_Function_t *, Ntk_NodeReadNumFanins(node));
480  int             outputIndex = Ntk_NodeReadOutputIndex(node);
481  Tbl_Table_t    *table       = Ntk_NodeReadTable(node);
482
483
484  Ntk_NodeForEachFanin(node, i, faninNode) {
485    Mvf_Function_t *tmpMvf = NodeBuildMvfRecursively(faninNode, leaves,
486                                                     nodeToMvfTable, mddMgr,
487                                                     careSet);
488    array_insert(Mvf_Function_t *, faninMvfs, i, tmpMvf);
489  }
490  resultMvf = Tbl_TableBuildMvfFromFanins(table, outputIndex, faninMvfs, mddMgr);
491
492  /* Mc_CheckValdityOfMvf(Ntk_NodeReadNetwork(node), mddMgr, node, resultMvf); */
493
494  Ntk_NodeForEachFanin(node, i, faninNode) {
495    NodeDecrementRefCount(faninNode, nodeToMvfTable);
496  }
497
498  /* Don't free the MVFs themselves, but just free the array. */
499  array_free(faninMvfs);
500
501  return resultMvf;
502}
503
504
505/**Function********************************************************************
506
507  Synopsis [Returns MVF corresponding to a node; returns NIL if node not in
508  table.]
509
510  SideEffects []
511
512******************************************************************************/
513static Mvf_Function_t *
514NodeReadMvf(
515  Ntk_Node_t * node,
516  st_table * nodeToMvfTable)
517{
518  Mvf_Function_t *result = NIL(Mvf_Function_t);
519  st_lookup(nodeToMvfTable, node, &result);
520
521  return result;
522}
523
524
525/**Function********************************************************************
526
527  Synopsis    [Inserts node and corresponding MVF into table.]
528
529  SideEffects []
530
531******************************************************************************/
532static void
533NodeSetMvf(
534  Ntk_Node_t * node,
535  st_table * nodeToMvfTable,
536  Mvf_Function_t * mvf)
537{
538  st_insert(nodeToMvfTable, (char *) node, (char *) mvf);
539}
540
541
542/**Function********************************************************************
543
544  Synopsis    [Hacked test for the ntm package.]
545
546  CommandName [_ntm_test]
547
548  CommandSynopsis [test the ntm package]
549
550  CommandArguments [\[-h\] \[-v\]]
551
552  CommandDescription [Test the ntm package.  This package is responsible for
553  building the multi-valued functions (represented as MDDs) of the flattened
554  network.  This command builds the multi-valued functions of the
555  combinational outputs in terms of the combinational inputs.  The
556  multi-valued functions are then deleted. <p>
557
558  Command options:<p>
559
560  <dl>
561
562  <dt> -h
563  <dd> Print the command usage.
564
565  <dt> -v
566  <dd> Print the sizes of the MDDs built.
567
568  </dl>
569  ]
570
571  SideEffects []
572
573******************************************************************************/
574static int
575CommandNtmTest(
576  Hrc_Manager_t ** hmgr,
577  int  argc,
578  char ** argv)
579{
580  int            c;
581  Ntk_Node_t    *node;
582  lsGen          gen;
583  array_t       *result; /* array of Mvf_Function_t* */
584  array_t       *roots;
585  st_table      *leaves;
586  boolean        verbose = FALSE;              /* default */
587  Ntk_Network_t *network = Ntk_HrcManagerReadCurrentNetwork(*hmgr);
588
589  /*
590   * Parse the command line.
591   */
592  util_getopt_reset();
593  while ((c = util_getopt(argc, argv, "vh")) != EOF) {
594    switch (c) {
595      case 'v':
596        verbose = 1;
597        break;
598      case 'h':
599        goto usage;
600      default:
601        goto usage;
602    }
603  }
604
605  if (network == NIL(Ntk_Network_t)) {
606    return 1;
607  }
608
609  if (Ord_NetworkTestAreVariablesOrdered(network, Ord_InputAndLatch_c) == FALSE) {
610    (void) fprintf(vis_stderr, "The MDD variables have not been ordered. ");
611    (void) fprintf(vis_stderr, "Use static_order.\n");
612    return 1;
613  }
614
615  roots = array_alloc(Ntk_Node_t *, 0);
616  Ntk_NetworkForEachCombOutput(network, gen, node) {
617    array_insert_last(Ntk_Node_t *, roots, node);
618  }
619
620  leaves = st_init_table(st_ptrcmp, st_ptrhash);
621  Ntk_NetworkForEachCombInput(network, gen, node) {
622    st_insert(leaves, (char *) node, (char *) NTM_UNUSED);
623  }
624
625  result = Ntm_NetworkBuildMvfs(network, roots, leaves, NIL(mdd_t));
626
627  if (verbose) {
628    MvfSanityCheck(roots, result);
629  }
630
631  array_free(roots);
632  st_free_table(leaves);
633
634  /*
635   * Free the array of MVFs.
636   */
637  Mvf_FunctionArrayFree(result);
638
639  return 0;
640
641usage:
642  (void) fprintf(vis_stderr, "usage: _ntm_test [-h] [-v]\n");
643  (void) fprintf(vis_stderr, "   -h print the command usage\n");
644  (void) fprintf(vis_stderr, "   -v verbose\n");
645  return 1;             /* error exit */
646}
647
648
649/**Function********************************************************************
650
651  Synopsis    [Checks that MDD sizes are meaningful.]
652
653  SideEffects []
654
655******************************************************************************/
656static void
657MvfSanityCheck(
658  array_t *roots /* of Ntk_Node_t* */,
659  array_t *mvfs  /* of Mvf_Function_t* */)
660{
661  int i;
662
663  assert(array_n(roots) == array_n(mvfs));
664
665  for (i = 0; i < array_n(roots); i ++) {
666    int             value;
667    mdd_t          *valueMdd;
668    Ntk_Node_t     *root = array_fetch(Ntk_Node_t *, roots, i);
669    Mvf_Function_t *mvf  = array_fetch(Mvf_Function_t *, mvfs, i);
670
671    (void) fprintf(vis_stdout, "\nMDD stats for node %s:\n", Ntk_NodeReadName(root));
672
673    Mvf_FunctionForEachComponent(mvf, value, valueMdd) {
674      (void) fprintf(vis_stdout, "\tSize of MDD for value %d is %d\n", i,
675                     mdd_size(valueMdd));
676    }
677  }
678}
679
680
681/**Function********************************************************************
682
683  Synopsis    [Initializes the reference counts in a region.]
684
685  Description [Initializes the reference counts in the region defined by the
686  roots and leaves.  This region includes the roots, and all nodes in the
687  transitive fanin of the roots up to and including the leaves.  The reference
688  count for a node in the region is set to be the number of fanouts of that
689  node in the region (fanouts to leaf nodes and constant nodes are excluded).
690  Root nodes are set to MAXINT, so that even after some decrements, their ref
691  count won't fall to zero.]
692
693  SideEffects [Uses the undef field of node.]
694
695******************************************************************************/
696static void
697RegionInitializeReferenceCounts(
698  array_t *roots,
699  st_table *leaves)
700{
701  int           i;
702  Ntk_Node_t   *node;
703  st_generator *stGen;
704  st_table     *regionNodes = Ntk_RegionFindNodes(roots, leaves);
705
706  st_foreach_item(regionNodes, stGen, &node, NULL) {
707    Ntk_Node_t *fanoutNode;
708    long        refCount = 0;
709
710    Ntk_NodeForEachFanout(node, i, fanoutNode) {
711      if (st_is_member(regionNodes, (char *) fanoutNode)
712          && !st_is_member(leaves, (char *) fanoutNode)
713          && !Ntk_NodeTestIsConstant(fanoutNode)) {
714        refCount++;
715      }
716    }
717    Ntk_NodeSetUndef(node, (void *) refCount);
718  }
719
720  for(i = 0; i < array_n(roots); i++) {
721    node = array_fetch(Ntk_Node_t *, roots, i);
722    Ntk_NodeSetUndef(node, (void *) MAXINT);
723  }
724
725  st_free_table(regionNodes);
726}
727
728/**Function********************************************************************
729
730  Synopsis    [Decrements the ref count of a node.]
731
732  Description [Decrements the ref count of a node.  If the ref count becomes
733  zero, then remove node from nodeToMvfTable and free the MVF corresponding to
734  node.]
735
736  SideEffects []
737
738******************************************************************************/
739static void
740NodeDecrementRefCount(
741  Ntk_Node_t *node,
742  st_table *nodeToMvfTable)
743{
744  Mvf_Function_t *mvf;
745  long            refCount = (long) Ntk_NodeReadUndef(node);
746
747  assert(refCount != 0);
748
749  refCount--;
750
751  if (refCount == 0) {
752    st_delete(nodeToMvfTable, &node, &mvf);
753    Mvf_FunctionFree(mvf);
754  }
755
756  Ntk_NodeSetUndef(node, (void *) refCount);
757}
758
759/**Function********************************************************************
760
761  Synopsis    [Returns TRUE if table1 is contained in nodeArray; else FALSE.]
762
763  Description [Table1 is a hash table where the keys are nodes. NodeArray is
764  an array of nodes.  This function returns TRUE if the set of key nodes in
765  table1 is contained in the set of nodes in nodeArray.  It returns FALSE upon
766  finding the first key node in table1 that is not in nodeArray.]
767
768  SideEffects []
769
770******************************************************************************/
771static boolean
772TableTestIsContainedInArray(
773  st_table *table1,
774  array_t *nodeArrary)
775{
776  int             i;
777  st_generator   *stGen;
778  Ntk_Node_t     *node;
779  Mvf_Function_t *mvf;
780  st_table       *table2 = st_init_table(st_ptrcmp, st_ptrhash);
781
782  /* Create a hash table from the array. */
783  arrayForEachItem(Ntk_Node_t *, nodeArrary, i, node) {
784    st_insert(table2, (char *) node, NIL(char));
785  }
786
787  st_foreach_item(table1, stGen, &node, &mvf) {
788    if (!st_is_member(table2, node)) {
789      st_free_table(table2);
790      return FALSE;
791    }
792  }
793
794  st_free_table(table2);
795  return TRUE;
796}
Note: See TracBrowser for help on using the repository browser.