source: vis_dev/vis-2.3/src/ntk/ntkSweep.c @ 84

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

vis2.3
File size: 17.3 KB
RevLine 
[14]1/**CFile***********************************************************************
2
3  FileName    [ntkSweep.c]
4
5  PackageName [Ntk]
6
7  Synopsis    [Utilities for Cleaning the Ntk_Network_t]
8
9  Description []
10
11  SeeAlso     []
12
13  Author      [Gitanjali Swamy]
14
15  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
16  All rights reserved.
17
18  Permission is hereby granted, without written agreement and without license
19  or royalty fees, to use, copy, modify, and distribute this software and its
20  documentation for any purpose, provided that the above copyright notice and
21  the following two paragraphs appear in all copies of this software.
22
23  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
24  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
25  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
26  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
29  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
30  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
31  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
32  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
33
34******************************************************************************/
35
36#include "ntkInt.h"
37
38static char rcsid[] UNUSED = "$Id: ntkSweep.c,v 1.18 2010/04/09 23:44:05 fabio Exp $";
39
40/*comment */
41
42/*---------------------------------------------------------------------------*/
43/* Constant declarations                                                     */
44/*---------------------------------------------------------------------------*/
45
46
47/*---------------------------------------------------------------------------*/
48/* Type declarations                                                         */
49/*---------------------------------------------------------------------------*/
50
51
52/*---------------------------------------------------------------------------*/
53/* Structure declarations                                                    */
54/*---------------------------------------------------------------------------*/
55
56
57/*---------------------------------------------------------------------------*/
58/* Variable declarations                                                     */
59/*---------------------------------------------------------------------------*/
60
61
62/*---------------------------------------------------------------------------*/
63/* Macro declarations                                                        */
64/*---------------------------------------------------------------------------*/
65
66/**AutomaticStart*************************************************************/
67
68/*---------------------------------------------------------------------------*/
69/* Static function prototypes                                                */
70/*---------------------------------------------------------------------------*/
71
72static void NetworkCollapseConstantNode(Ntk_Network_t *network, Ntk_Node_t *node);
73static void NetworkCollapseIdentityNode(Ntk_Network_t *network, Ntk_Node_t *node);
74static void NetworkCollapseInverterNode(Ntk_Network_t *network, Ntk_Node_t *node);
75static int NodeRemoveFanout(Ntk_Node_t *node, Ntk_Node_t *delFanoutNode);
76
77/**AutomaticEnd***************************************************************/
78
79
80/*---------------------------------------------------------------------------*/
81/* Definition of exported functions                                          */
82/*---------------------------------------------------------------------------*/
83
84
85/**Function********************************************************************
86
87  Synopsis           [Sweep given network]
88
89  Description        [This function performs a sweep on the given
90  Ntk_Network_t. It propagates all the deterministic constant nodes, and
91  removes all buffer nodes. The function returns TRUE if it succeeds and
92  FALSE it it does not. Note that constant nodes that have fanins may
93  not be propogated right now.]
94
95  SideEffects        []
96
97******************************************************************************/
98void
99Ntk_NetworkSweep(Ntk_Network_t *network, int verbosity)
100{
101  lsList nodeList;
102  Ntk_Node_t *node;
103  lsGen gen;
104  array_t *rootArray = array_alloc(Ntk_Node_t *,
105                                   Ntk_NetworkReadNumCombOutputs(network));
106  st_table *leafNodesTable = st_init_table(st_ptrcmp, st_ptrhash);
107  int count = 0;
108
109  /* Get a topologically sorted list of all nodes so that one pass
110     through the network is enough to remove all constant nodes. */
111  Ntk_NetworkForEachNode(network, gen, node) {
112    if (Ntk_NodeTestIsPrimaryOutput(node)
113        || Ntk_NodeTestIsLatchDataInput(node)
114        || Ntk_NodeReadNumFanouts(node) == 0)
115      array_insert_last(Ntk_Node_t *, rootArray, node);
116    if (Ntk_NodeTestIsInput(node) || Ntk_NodeReadNumFanins(node) == 0)
117      st_insert(leafNodesTable, node, NIL(char));
118  }
119  nodeList = Ntk_NetworkComputeTopologicalOrder(network, rootArray,
120                                                leafNodesTable);
121  /* Check that all nodes are included. */
122  assert(lsLength(nodeList) == lsLength(network->nodes));
123  array_free(rootArray);
124  st_free_table(leafNodesTable);
125
126  /* Check for constants, identities and inverters. */
127  lsForEachItem(nodeList, gen, node) {
128    char *name = Ntk_NodeReadName(node);
129    /* Try to remove only nodes created by vl2mv. */
130    if (name[0] != '_' && strstr(name, "._") == NIL(char) &&
131        strstr(name, "$") == NIL(char)) continue;
132    if (Ntk_NodeTestIsConstant(node) == TRUE) {
133      if (Ntk_NodeReadNumFanins(node) == 0) {
134        NetworkCollapseConstantNode(network, node);
135        if (Ntk_NodeReadNumFanouts(node) == 0) {
136          if (Ntk_NodeRemoveFromNetwork(network,node,0,0,verbosity) == TRUE) {
137            lsDelBefore(gen, &node);
138            Ntk_NodeFree(node);
139            count++;
140          }
141        }
142      }
143    } else if (Ntk_NodeTestIsCombinational(node)) {
144      if (!Ntk_NodeTestIsCombOutput(node)) {
145        Tbl_Table_t *table = Ntk_NodeReadTable(node);
146        if (Tbl_TableIsIdentity(table)) {
147          NetworkCollapseIdentityNode(network, node);
148          if (Ntk_NodeRemoveFromNetwork(network,node,1,0,verbosity) == TRUE) {
149            lsDelBefore(gen, &node);
150            Ntk_NodeFree(node);
151            count++;
152          }
153        } else if (Tbl_TableIsInverter(table)) {
154          NetworkCollapseInverterNode(network, node);
155          if (Ntk_NodeReadNumFanins(node) == 0) {
156            if (Ntk_NodeRemoveFromNetwork(network,node,0,0,verbosity) == TRUE) {
157              lsDelBefore(gen, &node);
158              Ntk_NodeFree(node);
159              count++;
160            }
161          }
162        }
163      }
164    }
165  }
166
167  if (verbosity > 0) {
168    fprintf(vis_stderr,"Removed %d node%s\n", count, count == 1 ? "" : "s");
169  }
170
171  (void) lsDestroy(network->nodes,(void (*) (lsGeneric)) NULL);
172  network->nodes = nodeList;
173
174  if (verbosity > 0) {
175    Ntk_NetworkWriteBlifMv(vis_stdout, network, TRUE);
176  }
177
178} /* Ntk_NetworkSweep */
179
180
181/**Function********************************************************************
182
183  Synopsis           [Remove node from network]
184
185  Description        [If force=0, the node to be removed should not be a
186  fanin/fanout/latch. If force=1, the node is removed from the network no
187  matter what. ]
188
189  SideEffects        [Appropriate fields in the network are updated.]
190
191  SeeAlso            []
192
193******************************************************************************/
194boolean
195Ntk_NodeRemoveFromNetwork(Ntk_Network_t *network, Ntk_Node_t *node,
196                          int force, boolean removeFromNodeList, int verbosity)
197{
198  if (!force) {
199    assert(Ntk_NodeReadNumFanins(node) == 0);
200    assert(Ntk_NodeReadNumFanouts(node) == 0);
201
202    if (Ntk_NodeTestIsPrimaryOutput(node)==TRUE) {
203      return FALSE;
204    }
205    if (Ntk_NodeTestIsLatch(node)==TRUE) {
206      return FALSE;
207    }
208    if (Ntk_NodeTestIsPrimaryInput(node)==TRUE) {
209      return FALSE;
210    }
211  }
212
213  if (verbosity) {
214    fprintf(vis_stdout, "** ntk info: Node Removed %s\n", node->name);
215  }
216
217  node->network = NIL(Ntk_Network_t);
218  if (Ntk_NodeTestIsCombOutput(node)) {
219    NtkNodeDeleteFromList(network->combOutputs, node);
220    st_delete(network->combOutputsTable, &node, NULL);
221  }
222  if (Ntk_NodeTestIsCombInput(node)) {
223    NtkNodeDeleteFromList(network->combInputs, node);
224  }
225
226  st_delete(network->actualNameToNode, &(node->name), NIL(char *));
227  /* BALA: I don't understand why the following line was not present
228     earlier. */
229  /* When this function is called by Ntk_NetworkSweep, it is not
230     necessary to remove the node from the network's node list because
231     the node list is re-generated regardless.  In addition, it may
232     get very expensive.
233   */
234  if (removeFromNodeList)
235    NtkNodeDeleteFromList(network->nodes, node);
236
237  switch(node->type) {
238    case NtkShadow_c:
239      break;
240    case NtkPseudoInput_c:
241      NtkNodeDeleteFromList(network->inputs, node);
242      NtkNodeDeleteFromList(network->pseudoInputs, node);
243      break;
244    case NtkCombinational_c:
245      break;
246    case NtkUnassigned_c:
247      break;
248    case NtkLatch_c:
249      NtkNodeDeleteFromList(network->latches, node);
250      break;
251  case NtkPrimaryInput_c:
252      NtkNodeDeleteFromList(network->primaryInputs, node);
253      break;
254      /*
255    default:
256    fail("Type cannot be deleted");*/
257  }
258
259  /* for PO */
260  if (Ntk_NodeTestIsPrimaryOutput(node)==TRUE)
261      NtkNodeDeleteFromList(network->primaryOutputs, node);
262
263  return TRUE;
264}
265
266
267/*---------------------------------------------------------------------------*/
268/* Definition of internal functions                                          */
269/*---------------------------------------------------------------------------*/
270
271/**Function********************************************************************
272
273  Synopsis           [Delete a node from given list]
274
275  Description        [Given a node and a list of nodes, this function deletes
276  the node from the list.]
277
278  SideEffects        []
279
280  SeeAlso            []
281
282******************************************************************************/
283boolean
284NtkNodeDeleteFromList(
285  lsList nodeList,
286  Ntk_Node_t *node)
287{
288
289  lsGen gen;
290  lsGeneric data;
291  Ntk_Node_t *listnode;
292  Ntk_Node_t *delNode;
293  boolean check;
294  int i;
295
296  check = FALSE;
297  i = 0;
298  lsForEachItem(nodeList, gen, listnode) {
299    if (node == listnode) {
300      if (i > 0)
301        lsDelBefore(gen, &data);
302      else
303        lsDelBegin(nodeList, &data);
304      check = TRUE;
305    }
306    i++;
307  }
308  delNode = (Ntk_Node_t*)data;
309
310  assert(delNode == node);
311  assert(check);
312  return check;
313}
314
315/*---------------------------------------------------------------------------*/
316/* Definition of static functions                                            */
317/*---------------------------------------------------------------------------*/
318/**Function********************************************************************
319
320  Synopsis [Collapse given input (constant) into its fanouts.]
321
322  Description [This routine removes a given constant node.  It also
323  readjusts network parameters; i.e., removes the constant node from
324  the network. Finally, it also patches the fanouts of node. If a node
325  fanout is a latch, it is not possible to collapse it.  Note that the
326  constant node must have no fanins.]
327
328  SideEffects []
329
330
331******************************************************************************/
332static void
333NetworkCollapseConstantNode(Ntk_Network_t *network, Ntk_Node_t *node)
334{
335  Tbl_Table_t *table, *newtable;
336  Ntk_Node_t *fanout, *fanin;
337  int i,j,index;
338  array_t *newFaninArray;
339  array_t *tmpFanoutArray;
340
341  table = Ntk_NodeReadTable(node);
342
343  tmpFanoutArray = array_dup(Ntk_NodeReadFanouts(node));
344  arrayForEachItem(Ntk_Node_t *, tmpFanoutArray, i, fanout) {
345    if (fanout->type == NtkCombinational_c) {
346      index = Ntk_NodeReadFaninIndex(fanout,node);
347      while (index != NTK_UNDEFINED_FANIN_INDEX) {
348        Tbl_Table_t *fantable = Ntk_NodeReadTable(fanout);
349
350        NodeRemoveFanout(node,fanout);
351        newtable = Tbl_TableCollapse(fantable,table,index);
352        Tbl_TableFree(fantable);
353        Ntk_NodeSetTable(fanout, newtable);
354
355        if (Tbl_TableTestIsConstant(fanout->table, 0)) {
356          fanout->constant = TRUE;
357        }
358
359        newFaninArray = array_alloc(Ntk_Node_t*, 0);
360        Ntk_NodeForEachFanin(fanout, j, fanin) {
361          if (j != index) {
362            array_insert_last(Ntk_Node_t*, newFaninArray, fanin);
363          }
364        }
365        array_free(fanout->fanins);
366        fanout->fanins = newFaninArray;
367
368        index = Ntk_NodeReadFaninIndex(fanout, node);
369      }
370    }
371  }
372  array_free(tmpFanoutArray);
373
374  Ntk_NodeForEachFanin(node, i, fanin) {
375    NodeRemoveFanout(fanin, node);
376  }
377
378  array_free(node->fanins);
379  node->fanins = array_alloc(Ntk_Node_t*, 0);
380
381}
382
383
384/**Function********************************************************************
385
386  Synopsis [Collapse given identity node into its fanouts.]
387
388  Description [This routine removes a given identity node.  It also
389  readjusts network parameters; i.e., removes the identity node from
390  the network. Finally, it also patches the fanins and fanouts of
391  node.]
392
393  SideEffects [The network is modified.]
394
395  SeeAlso [NetworkCollapseConstantNode NetworkCollapseInverterNode]
396
397******************************************************************************/
398static void
399NetworkCollapseIdentityNode(Ntk_Network_t *network, Ntk_Node_t *node)
400{
401  Ntk_Node_t *fanout, *fanin;
402  Var_Variable_t *invar, *outvar;
403  int i;
404
405  fanin = Ntk_NodeReadFaninNode(node, 0);
406  invar = Ntk_NodeReadVariable(fanin);
407  outvar = Ntk_NodeReadVariable(node);
408  NodeRemoveFanout(fanin, node);
409  /* array_remove_last(Ntk_NodeReadFanins(node)); */
410
411  Ntk_NodeForEachFanout(node, i, fanout) {
412    int index = Ntk_NodeReadFaninIndex(fanout,node);
413    /* Since a node may be connected to another node multiple times,
414     * we iterate until node is not found any more.
415     */
416    while (index != NTK_UNDEFINED_FANIN_INDEX) {
417      if (fanout->type == NtkCombinational_c) {
418        Tbl_Table_t *fantable = Ntk_NodeReadTable(fanout);
419        Tbl_TableSubstituteVar(fantable, outvar, invar);
420      }
421      /* NodeRemoveFanout(node,fanout); */
422
423      /* Replace node with its input node in the fanins of fanout. */
424      array_insert(Ntk_Node_t *, Ntk_NodeReadFanins(fanout), index, fanin);
425      array_insert_last(Ntk_Node_t*, Ntk_NodeReadFanouts(fanin), fanout);
426
427      index = Ntk_NodeReadFaninIndex(fanout, node);
428    }
429  }
430
431} /* NetworkCollapseIdentityNode */
432
433
434/**Function********************************************************************
435
436  Synopsis [Collapse given inverter node into its fanouts.]
437
438  Description [This routine collapses a given inverter node into its
439  fanouts.  It also readjusts network parameters; i.e., removes the
440  inverter node from the network. Finally, it also patches the fanins
441  and fanouts of node.]
442
443  SideEffects [The network is modified.]
444
445  SeeAlso [NetworkCollapseConstantNode NetworkCollapseIdentityNode]
446
447******************************************************************************/
448static void
449NetworkCollapseInverterNode(Ntk_Network_t *network, Ntk_Node_t *node)
450{
451  Ntk_Node_t *fanout, *fanin;
452  Var_Variable_t *invar, *outvar;
453  int i;
454  boolean failure = FALSE;
455  array_t *dupFanoutArray;
456
457  assert(Ntk_NodeReadNumFanins(node) == 1);
458  fanin = Ntk_NodeReadFaninNode(node, 0);
459  invar = Ntk_NodeReadVariable(fanin);
460  outvar = Ntk_NodeReadVariable(node);
461
462  dupFanoutArray = array_dup(Ntk_NodeReadFanouts(node));
463  arrayForEachItem(Ntk_Node_t *, dupFanoutArray, i, fanout) {
464    if (fanout->type == NtkCombinational_c) {
465      int index = Ntk_NodeReadFaninIndex(fanout,node);
466      /* Since a node may be connected to another node multiple times,
467       * we iterate until node is not found any more.
468       */
469      while (index != NTK_UNDEFINED_FANIN_INDEX) {
470        Tbl_Table_t *fantable = Ntk_NodeReadTable(fanout);
471        Tbl_Table_t *newTable =
472          Tbl_TableInvertBinaryInputColumn(fantable, index);
473        if (newTable != NIL(Tbl_Table_t)) {
474          Tbl_TableFree(fantable);
475          Tbl_TableSubstituteVar(newTable, outvar, invar);
476          Ntk_NodeSetTable(fanout, newTable);
477          NodeRemoveFanout(node, fanout);
478
479          /* Replace node with its input node in the fanins of fanout. */
480          array_insert(Ntk_Node_t *, Ntk_NodeReadFanins(fanout), index, fanin);
481          array_insert_last(Ntk_Node_t*, Ntk_NodeReadFanouts(fanin), fanout);
482        } else {
483          failure = TRUE;
484          /* Test: */ fprintf(vis_stdout, "achtung!\n");
485        }
486        index = Ntk_NodeReadFaninIndex(fanout, node);
487      }
488    } else {
489      failure = TRUE;
490    }
491  }
492  array_free(dupFanoutArray);
493
494  if (!failure) {
495    NodeRemoveFanout(fanin, node);
496    array_remove_last(Ntk_NodeReadFanins(node));
497  }
498
499} /* NetworkCollapseInverterNode */
500
501
502/**Function********************************************************************
503
504  Synopsis    [remove given delFanoutNode from the fanouts of given node]
505
506  Description [Given a Ntk_Node_t* node and one of its fanouts Ntk_Node_t*
507  delFanoutNode, this routine will remove the fanout from the fanouts of
508  the given node.]
509
510  SideEffects []
511
512  SeeAlso     []
513
514******************************************************************************/
515static int
516NodeRemoveFanout(
517  Ntk_Node_t *node,
518  Ntk_Node_t *delFanoutNode)
519{
520  array_t *newFanoutArray;
521  Ntk_Node_t *fanout, *fanin;
522  int j;
523
524  if (node == NIL(Ntk_Node_t))
525    return(0);
526
527  newFanoutArray = array_alloc(Ntk_Node_t*, 0);
528  Ntk_NodeForEachFanout(node, j, fanout) {
529    if (fanout != delFanoutNode) {
530      array_insert_last(Ntk_Node_t*, newFanoutArray, fanout);
531    }
532  }
533  array_free(node->fanouts);
534  node->fanouts = newFanoutArray;
535
536  Ntk_NodeForEachFanin(delFanoutNode, j, fanin) {
537    if (fanin == node) {
538      array_insert(Ntk_Node_t*, delFanoutNode->fanins, j, NIL(Ntk_Node_t));
539      /* to break not to delete another fanin if any */
540      j = Ntk_NodeReadNumFanins(delFanoutNode);
541    }
542  }
543
544  return(1);
545}
Note: See TracBrowser for help on using the repository browser.