#include "ntkInt.h"
Include dependency graph for ntkSweep.c:
Go to the source code of this file.
Functions | |
| 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) |
| void | Ntk_NetworkSweep (Ntk_Network_t *network, int verbosity) |
| boolean | Ntk_NodeRemoveFromNetwork (Ntk_Network_t *network, Ntk_Node_t *node, int force, boolean removeFromNodeList, int verbosity) |
| boolean | NtkNodeDeleteFromList (lsList nodeList, Ntk_Node_t *node) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: ntkSweep.c,v 1.18 2010/04/09 23:44:05 fabio Exp $" |
Function Documentation
| static void NetworkCollapseConstantNode | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | node | ||
| ) | [static] |
AutomaticStart
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 []
Definition at line 333 of file ntkSweep.c.
{
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);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void NetworkCollapseIdentityNode | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | node | ||
| ) | [static] |
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]
Definition at line 399 of file ntkSweep.c.
{
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 */
Here is the call graph for this function:
Here is the caller graph for this function:
| static void NetworkCollapseInverterNode | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | node | ||
| ) | [static] |
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]
Definition at line 449 of file ntkSweep.c.
{
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 */
Here is the call graph for this function:
Here is the caller graph for this function:
| static int NodeRemoveFanout | ( | Ntk_Node_t * | node, |
| Ntk_Node_t * | delFanoutNode | ||
| ) | [static] |
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 []
Definition at line 516 of file ntkSweep.c.
{
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);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void Ntk_NetworkSweep | ( | Ntk_Network_t * | network, |
| int | verbosity | ||
| ) |
AutomaticEnd 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 []
Definition at line 99 of file ntkSweep.c.
{
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 */
Here is the call graph for this function:
Here is the caller graph for this function:
| boolean Ntk_NodeRemoveFromNetwork | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | node, | ||
| int | force, | ||
| boolean | removeFromNodeList, | ||
| int | verbosity | ||
| ) |
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 []
Definition at line 195 of file ntkSweep.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| boolean NtkNodeDeleteFromList | ( | lsList | nodeList, |
| Ntk_Node_t * | node | ||
| ) |
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 []
Definition at line 284 of file ntkSweep.c.
{
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;
}
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: ntkSweep.c,v 1.18 2010/04/09 23:44:05 fabio Exp $" [static] |
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.]
Definition at line 38 of file ntkSweep.c.
