src/ntk/ntkSweep.c

Go to the documentation of this file.

#include "ntkInt.h"

static char rcsid[] UNUSED = "$Id: ntkSweep.c,v 1.18 2010/04/09 23:44:05 fabio Exp $";

/*comment */

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void NetworkCollapseConstantNode(Ntk_Network_t *network, Ntk_Node_t *node);
static void NetworkCollapseIdentityNode(Ntk_Network_t *network, Ntk_Node_t *node);
static void NetworkCollapseInverterNode(Ntk_Network_t *network, Ntk_Node_t *node);
static int NodeRemoveFanout(Ntk_Node_t *node, Ntk_Node_t *delFanoutNode);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


void
Ntk_NetworkSweep(Ntk_Network_t *network, int verbosity)
{
  lsList nodeList;
  Ntk_Node_t *node;
  lsGen gen;
  array_t *rootArray = array_alloc(Ntk_Node_t *,
                                   Ntk_NetworkReadNumCombOutputs(network));
  st_table *leafNodesTable = st_init_table(st_ptrcmp, st_ptrhash);
  int count = 0;

  /* Get a topologically sorted list of all nodes so that one pass
     through the network is enough to remove all constant nodes. */
  Ntk_NetworkForEachNode(network, gen, node) {
    if (Ntk_NodeTestIsPrimaryOutput(node)
        || Ntk_NodeTestIsLatchDataInput(node)
        || Ntk_NodeReadNumFanouts(node) == 0)
      array_insert_last(Ntk_Node_t *, rootArray, node);
    if (Ntk_NodeTestIsInput(node) || Ntk_NodeReadNumFanins(node) == 0)
      st_insert(leafNodesTable, node, NIL(char));
  }
  nodeList = Ntk_NetworkComputeTopologicalOrder(network, rootArray,
                                                leafNodesTable);
  /* Check that all nodes are included. */
  assert(lsLength(nodeList) == lsLength(network->nodes));
  array_free(rootArray);
  st_free_table(leafNodesTable);

  /* Check for constants, identities and inverters. */
  lsForEachItem(nodeList, gen, node) {
    char *name = Ntk_NodeReadName(node);
    /* Try to remove only nodes created by vl2mv. */
    if (name[0] != '_' && strstr(name, "._") == NIL(char) &&
        strstr(name, "$") == NIL(char)) continue;
    if (Ntk_NodeTestIsConstant(node) == TRUE) {
      if (Ntk_NodeReadNumFanins(node) == 0) {
        NetworkCollapseConstantNode(network, node);
        if (Ntk_NodeReadNumFanouts(node) == 0) {
          if (Ntk_NodeRemoveFromNetwork(network,node,0,0,verbosity) == TRUE) {
            lsDelBefore(gen, &node);
            Ntk_NodeFree(node);
            count++;
          }
        }
      }
    } else if (Ntk_NodeTestIsCombinational(node)) {
      if (!Ntk_NodeTestIsCombOutput(node)) {
        Tbl_Table_t *table = Ntk_NodeReadTable(node);
        if (Tbl_TableIsIdentity(table)) {
          NetworkCollapseIdentityNode(network, node);
          if (Ntk_NodeRemoveFromNetwork(network,node,1,0,verbosity) == TRUE) {
            lsDelBefore(gen, &node);
            Ntk_NodeFree(node);
            count++;
          }
        } else if (Tbl_TableIsInverter(table)) {
          NetworkCollapseInverterNode(network, node);
          if (Ntk_NodeReadNumFanins(node) == 0) {
            if (Ntk_NodeRemoveFromNetwork(network,node,0,0,verbosity) == TRUE) {
              lsDelBefore(gen, &node);
              Ntk_NodeFree(node);
              count++;
            }
          }
        }
      }
    }
  }

  if (verbosity > 0) {
    fprintf(vis_stderr,"Removed %d node%s\n", count, count == 1 ? "" : "s");
  }

  (void) lsDestroy(network->nodes,(void (*) (lsGeneric)) NULL);
  network->nodes = nodeList;

  if (verbosity > 0) {
    Ntk_NetworkWriteBlifMv(vis_stdout, network, TRUE);
  }

} /* Ntk_NetworkSweep */


boolean
Ntk_NodeRemoveFromNetwork(Ntk_Network_t *network, Ntk_Node_t *node,
                          int force, boolean removeFromNodeList, int verbosity)
{
  if (!force) {
    assert(Ntk_NodeReadNumFanins(node) == 0);
    assert(Ntk_NodeReadNumFanouts(node) == 0);

    if (Ntk_NodeTestIsPrimaryOutput(node)==TRUE) {
      return FALSE;
    }
    if (Ntk_NodeTestIsLatch(node)==TRUE) {
      return FALSE;
    }
    if (Ntk_NodeTestIsPrimaryInput(node)==TRUE) {
      return FALSE;
    }
  }

  if (verbosity) {
    fprintf(vis_stdout, "** ntk info: Node Removed %s\n", node->name);
  }

  node->network = NIL(Ntk_Network_t);
  if (Ntk_NodeTestIsCombOutput(node)) {
    NtkNodeDeleteFromList(network->combOutputs, node);
    st_delete(network->combOutputsTable, &node, NULL);
  }
  if (Ntk_NodeTestIsCombInput(node)) {
    NtkNodeDeleteFromList(network->combInputs, node);
  }

  st_delete(network->actualNameToNode, &(node->name), NIL(char *));
  /* BALA: I don't understand why the following line was not present
     earlier. */
  /* When this function is called by Ntk_NetworkSweep, it is not
     necessary to remove the node from the network's node list because
     the node list is re-generated regardless.  In addition, it may
     get very expensive.
   */
  if (removeFromNodeList)
    NtkNodeDeleteFromList(network->nodes, node);

  switch(node->type) {
    case NtkShadow_c:
      break;
    case NtkPseudoInput_c:
      NtkNodeDeleteFromList(network->inputs, node);
      NtkNodeDeleteFromList(network->pseudoInputs, node);
      break;
    case NtkCombinational_c:
      break;
    case NtkUnassigned_c:
      break;
    case NtkLatch_c:
      NtkNodeDeleteFromList(network->latches, node);
      break;
  case NtkPrimaryInput_c:
      NtkNodeDeleteFromList(network->primaryInputs, node);
      break;
      /*
    default:
    fail("Type cannot be deleted");*/
  }

  /* for PO */
  if (Ntk_NodeTestIsPrimaryOutput(node)==TRUE)
      NtkNodeDeleteFromList(network->primaryOutputs, node);

  return TRUE;
}


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

boolean
NtkNodeDeleteFromList(
  lsList nodeList,
  Ntk_Node_t *node)
{

  lsGen gen;
  lsGeneric data;
  Ntk_Node_t *listnode;
  Ntk_Node_t *delNode;
  boolean check;
  int i;

  check = FALSE;
  i = 0;
  lsForEachItem(nodeList, gen, listnode) {
    if (node == listnode) {
      if (i > 0)
        lsDelBefore(gen, &data);
      else
        lsDelBegin(nodeList, &data);
      check = TRUE;
    }
    i++;
  }
  delNode = (Ntk_Node_t*)data;

  assert(delNode == node);
  assert(check);
  return check;
}

/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/
static void
NetworkCollapseConstantNode(Ntk_Network_t *network, Ntk_Node_t *node)
{
  Tbl_Table_t *table, *newtable;
  Ntk_Node_t *fanout, *fanin;
  int i,j,index;
  array_t *newFaninArray;
  array_t *tmpFanoutArray;

  table = Ntk_NodeReadTable(node);

  tmpFanoutArray = array_dup(Ntk_NodeReadFanouts(node));
  arrayForEachItem(Ntk_Node_t *, tmpFanoutArray, i, fanout) {
    if (fanout->type == NtkCombinational_c) {
      index = Ntk_NodeReadFaninIndex(fanout,node);
      while (index != NTK_UNDEFINED_FANIN_INDEX) {
        Tbl_Table_t *fantable = Ntk_NodeReadTable(fanout);

        NodeRemoveFanout(node,fanout);
        newtable = Tbl_TableCollapse(fantable,table,index);
        Tbl_TableFree(fantable);
        Ntk_NodeSetTable(fanout, newtable);

        if (Tbl_TableTestIsConstant(fanout->table, 0)) {
          fanout->constant = TRUE;
        }

        newFaninArray = array_alloc(Ntk_Node_t*, 0);
        Ntk_NodeForEachFanin(fanout, j, fanin) {
          if (j != index) {
            array_insert_last(Ntk_Node_t*, newFaninArray, fanin);
          }
        }
        array_free(fanout->fanins);
        fanout->fanins = newFaninArray;

        index = Ntk_NodeReadFaninIndex(fanout, node);
      }
    }
  }
  array_free(tmpFanoutArray);

  Ntk_NodeForEachFanin(node, i, fanin) {
    NodeRemoveFanout(fanin, node);
  }

  array_free(node->fanins);
  node->fanins = array_alloc(Ntk_Node_t*, 0);

}


static void
NetworkCollapseIdentityNode(Ntk_Network_t *network, Ntk_Node_t *node)
{
  Ntk_Node_t *fanout, *fanin;
  Var_Variable_t *invar, *outvar;
  int i;

  fanin = Ntk_NodeReadFaninNode(node, 0);
  invar = Ntk_NodeReadVariable(fanin);
  outvar = Ntk_NodeReadVariable(node);
  NodeRemoveFanout(fanin, node);
  /* array_remove_last(Ntk_NodeReadFanins(node)); */

  Ntk_NodeForEachFanout(node, i, fanout) {
    int index = Ntk_NodeReadFaninIndex(fanout,node);
    /* Since a node may be connected to another node multiple times,
     * we iterate until node is not found any more.
     */
    while (index != NTK_UNDEFINED_FANIN_INDEX) {
      if (fanout->type == NtkCombinational_c) {
        Tbl_Table_t *fantable = Ntk_NodeReadTable(fanout);
        Tbl_TableSubstituteVar(fantable, outvar, invar);
      }
      /* NodeRemoveFanout(node,fanout); */

      /* Replace node with its input node in the fanins of fanout. */
      array_insert(Ntk_Node_t *, Ntk_NodeReadFanins(fanout), index, fanin);
      array_insert_last(Ntk_Node_t*, Ntk_NodeReadFanouts(fanin), fanout);

      index = Ntk_NodeReadFaninIndex(fanout, node);
    }
  }

} /* NetworkCollapseIdentityNode */


static void
NetworkCollapseInverterNode(Ntk_Network_t *network, Ntk_Node_t *node)
{
  Ntk_Node_t *fanout, *fanin;
  Var_Variable_t *invar, *outvar;
  int i;
  boolean failure = FALSE;
  array_t *dupFanoutArray;

  assert(Ntk_NodeReadNumFanins(node) == 1);
  fanin = Ntk_NodeReadFaninNode(node, 0);
  invar = Ntk_NodeReadVariable(fanin);
  outvar = Ntk_NodeReadVariable(node);

  dupFanoutArray = array_dup(Ntk_NodeReadFanouts(node));
  arrayForEachItem(Ntk_Node_t *, dupFanoutArray, i, fanout) {
    if (fanout->type == NtkCombinational_c) {
      int index = Ntk_NodeReadFaninIndex(fanout,node);
      /* Since a node may be connected to another node multiple times,
       * we iterate until node is not found any more.
       */
      while (index != NTK_UNDEFINED_FANIN_INDEX) {
        Tbl_Table_t *fantable = Ntk_NodeReadTable(fanout);
        Tbl_Table_t *newTable =
          Tbl_TableInvertBinaryInputColumn(fantable, index);
        if (newTable != NIL(Tbl_Table_t)) {
          Tbl_TableFree(fantable);
          Tbl_TableSubstituteVar(newTable, outvar, invar);
          Ntk_NodeSetTable(fanout, newTable);
          NodeRemoveFanout(node, fanout);

          /* Replace node with its input node in the fanins of fanout. */
          array_insert(Ntk_Node_t *, Ntk_NodeReadFanins(fanout), index, fanin);
          array_insert_last(Ntk_Node_t*, Ntk_NodeReadFanouts(fanin), fanout);
        } else {
          failure = TRUE;
          /* Test: */ fprintf(vis_stdout, "achtung!\n");
        }
        index = Ntk_NodeReadFaninIndex(fanout, node);
      }
    } else {
      failure = TRUE;
    }
  }
  array_free(dupFanoutArray);

  if (!failure) {
    NodeRemoveFanout(fanin, node);
    array_remove_last(Ntk_NodeReadFanins(node));
  }

} /* NetworkCollapseInverterNode */


static int
NodeRemoveFanout(
  Ntk_Node_t *node,
  Ntk_Node_t *delFanoutNode)
{
  array_t *newFanoutArray;
  Ntk_Node_t *fanout, *fanin;
  int j;

  if (node == NIL(Ntk_Node_t))
    return(0);

  newFanoutArray = array_alloc(Ntk_Node_t*, 0);
  Ntk_NodeForEachFanout(node, j, fanout) {
    if (fanout != delFanoutNode) {
      array_insert_last(Ntk_Node_t*, newFanoutArray, fanout);
    }
  }
  array_free(node->fanouts);
  node->fanouts = newFanoutArray;

  Ntk_NodeForEachFanin(delFanoutNode, j, fanin) {
    if (fanin == node) {
      array_insert(Ntk_Node_t*, delFanoutNode->fanins, j, NIL(Ntk_Node_t));
      /* to break not to delete another fanin if any */
      j = Ntk_NodeReadNumFanins(delFanoutNode);
    }
  }

  return(1);
}