/**CFile***********************************************************************

  FileName    [ntkSweep.c]

  PackageName [Ntk]

  Synopsis    [Utilities for Cleaning the Ntk_Network_t]

  Description []

  SeeAlso     []

  Author      [Gitanjali Swamy]

  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
  All rights reserved.

  Permission is hereby granted, without written agreement and without license
  or royalty fees, to use, copy, modify, and distribute this software and its
  documentation for any purpose, provided that the above copyright notice and
  the following two paragraphs appear in all copies of this software.

  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

******************************************************************************/

#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                                                        */
/*---------------------------------------------------------------------------*/

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* 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);

/**AutomaticEnd***************************************************************/


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


/**Function********************************************************************

  Synopsis           [Sweep given network]

  Description        [This function performs a sweep on the given
  Ntk_Network_t. It propagates all the deterministic constant nodes, and
  removes all buffer nodes. The function returns TRUE if it succeeds and
  FALSE it it does not. Note that constant nodes that have fanins may
  not be propogated right now.]

  SideEffects        []

******************************************************************************/
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 */


/**Function********************************************************************

  Synopsis           [Remove node from network]

  Description        [If force=0, the node to be removed should not be a
  fanin/fanout/latch. If force=1, the node is removed from the network no
  matter what. ]

  SideEffects        [Appropriate fields in the network are updated.]

  SeeAlso            []

******************************************************************************/
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                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis           [Delete a node from given list]

  Description        [Given a node and a list of nodes, this function deletes
  the node from the list.]

  SideEffects        []

  SeeAlso            []

******************************************************************************/
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                                            */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************

  Synopsis [Collapse given input (constant) into its fanouts.]

  Description [This routine removes a given constant node.  It also
  readjusts network parameters; i.e., removes the constant node from
  the network. Finally, it also patches the fanouts of node. If a node
  fanout is a latch, it is not possible to collapse it.  Note that the
  constant node must have no fanins.]

  SideEffects []


******************************************************************************/
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);

}


/**Function********************************************************************

  Synopsis [Collapse given identity node into its fanouts.]

  Description [This routine removes a given identity node.  It also
  readjusts network parameters; i.e., removes the identity node from
  the network. Finally, it also patches the fanins and fanouts of
  node.]

  SideEffects [The network is modified.]

  SeeAlso [NetworkCollapseConstantNode NetworkCollapseInverterNode]

******************************************************************************/
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 */


/**Function********************************************************************

  Synopsis [Collapse given inverter node into its fanouts.]

  Description [This routine collapses a given inverter node into its
  fanouts.  It also readjusts network parameters; i.e., removes the
  inverter node from the network. Finally, it also patches the fanins
  and fanouts of node.]

  SideEffects [The network is modified.]

  SeeAlso [NetworkCollapseConstantNode 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 */


/**Function********************************************************************

  Synopsis    [remove given delFanoutNode from the fanouts of given node]

  Description [Given a Ntk_Node_t* node and one of its fanouts Ntk_Node_t*
  delFanoutNode, this routine will remove the fanout from the fanouts of
  the given node.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
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);
}