summaryrefslogtreecommitdiffstats
path: root/src/base/abci/abcSweep.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/base/abci/abcSweep.c')
-rw-r--r--src/base/abci/abcSweep.c586
1 files changed, 465 insertions, 121 deletions
diff --git a/src/base/abci/abcSweep.c b/src/base/abci/abcSweep.c
index 7000ecad..1ae8745b 100644
--- a/src/base/abci/abcSweep.c
+++ b/src/base/abci/abcSweep.c
@@ -25,20 +25,20 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-extern Fraig_Man_t * Abc_NtkToFraig( Abc_Ntk_t * pNtk, Fraig_Params_t * pParams, int fAllNodes );
-
-static stmm_table * Abc_NtkFraigEquiv( Fraig_Man_t * p, Abc_Ntk_t * pNtk, int fUseInv, bool fVerbose );
+static void Abc_NtkFraigSweepUsingExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk );
+static stmm_table * Abc_NtkFraigEquiv( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose, int fVeryVerbose );
static void Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv, bool fVerbose );
-static void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fVerbose, int fUseInv );
-static void Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fVerbose, int fUseInv );
+static void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose );
+static void Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose );
static int Abc_NodeDroppingCost( Abc_Obj_t * pNode );
+static int Abc_NtkReduceNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes );
static void Abc_NodeSweep( Abc_Obj_t * pNode, int fVerbose );
static void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, bool fConst0 );
static void Abc_NodeComplementInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin );
////////////////////////////////////////////////////////////////////////
-/// FUNCTION DEFITIONS ///
+/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
@@ -54,22 +54,57 @@ static void Abc_NodeComplementInput( Abc_Obj_t * pNode, Abc_Obj_t * pF
SeeAlso []
***********************************************************************/
-bool Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose )
+bool Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fExdc, int fVerbose, int fVeryVerbose )
{
Fraig_Params_t Params;
Abc_Ntk_t * pNtkAig;
Fraig_Man_t * pMan;
stmm_table * tEquiv;
+ Abc_Obj_t * pObj;
+ int i, fUseTrick;
assert( !Abc_NtkIsStrash(pNtk) );
+ // save gate assignments
+ fUseTrick = 0;
+ if ( Abc_NtkIsMappedLogic(pNtk) )
+ {
+ fUseTrick = 1;
+ Abc_NtkForEachNode( pNtk, pObj, i )
+ pObj->pNext = pObj->pData;
+ }
// derive the AIG
- pNtkAig = Abc_NtkStrash( pNtk, 0, 1 );
+ pNtkAig = Abc_NtkStrash( pNtk, 0, 1, 0 );
+ // reconstruct gate assignments
+ if ( fUseTrick )
+ {
+ extern void * Abc_FrameReadLibGen();
+ Hop_ManStop( pNtk->pManFunc );
+ pNtk->pManFunc = Abc_FrameReadLibGen();
+ pNtk->ntkFunc = ABC_FUNC_MAP;
+ Abc_NtkForEachNode( pNtk, pObj, i )
+ pObj->pData = pObj->pNext, pObj->pNext = NULL;
+ }
+
// perform fraiging of the AIG
Fraig_ParamsSetDefault( &Params );
- pMan = Abc_NtkToFraig( pNtkAig, &Params, 0 );
+ pMan = Abc_NtkToFraig( pNtkAig, &Params, 0, 0 );
+ // cannot use EXDC with FRAIG because it can create classes of equivalent FRAIG nodes
+ // with representative nodes that do not correspond to the nodes with the current network
+
+ // update FRAIG using EXDC
+ if ( fExdc )
+ {
+ if ( pNtk->pExdc == NULL )
+ printf( "Warning: Networks has no EXDC.\n" );
+ else
+ Abc_NtkFraigSweepUsingExdc( pMan, pNtk );
+ }
+ // assign levels to the nodes of the network
+ Abc_NtkLevel( pNtk );
+
// collect the classes of equivalent nets
- tEquiv = Abc_NtkFraigEquiv( pMan, pNtk, fUseInv, fVerbose );
+ tEquiv = Abc_NtkFraigEquiv( pNtk, fUseInv, fVerbose, fVeryVerbose );
// transform the network into the equivalent one
Abc_NtkFraigTransform( pNtk, tEquiv, fUseInv, fVerbose );
@@ -80,7 +115,11 @@ bool Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose )
Abc_NtkDelete( pNtkAig );
// cleanup the dangling nodes
- Abc_NtkCleanup( pNtk, fVerbose );
+ if ( Abc_NtkHasMapping(pNtk) )
+ Abc_NtkCleanup( pNtk, fVerbose );
+ else
+ Abc_NtkSweep( pNtk, fVerbose );
+
// check
if ( !Abc_NtkCheck( pNtk ) )
{
@@ -92,6 +131,47 @@ bool Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose )
/**Function*************************************************************
+ Synopsis [Sweep the network using EXDC.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Abc_NtkFraigSweepUsingExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk )
+{
+ Fraig_Node_t * gNodeExdc, * gNode, * gNodeRes;
+ Abc_Obj_t * pNode, * pNodeAig;
+ int i;
+ extern Fraig_Node_t * Abc_NtkToFraigExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkExdc );
+
+ assert( pNtk->pExdc );
+ // derive FRAIG node representing don't-cares in the EXDC network
+ gNodeExdc = Abc_NtkToFraigExdc( pMan, pNtk, pNtk->pExdc );
+ // update the node pointers
+ Abc_NtkForEachNode( pNtk, pNode, i )
+ {
+ // skip the constant input nodes
+ if ( Abc_ObjFaninNum(pNode) == 0 )
+ continue;
+ // get the strashed node
+ pNodeAig = pNode->pCopy;
+ // skip the dangling nodes
+ if ( pNodeAig == NULL )
+ continue;
+ // get the FRAIG node
+ gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, Abc_ObjIsComplement(pNodeAig) );
+ // perform ANDing with EXDC
+ gNodeRes = Fraig_NodeAnd( pMan, gNode, Fraig_Not(gNodeExdc) );
+ // write the node back
+ Abc_ObjRegular(pNodeAig)->pCopy = (Abc_Obj_t *)Fraig_NotCond( gNodeRes, Abc_ObjIsComplement(pNodeAig) );
+ }
+}
+
+/**Function*************************************************************
+
Synopsis [Collects equivalence classses of node in the network.]
Description []
@@ -101,7 +181,7 @@ bool Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose )
SeeAlso []
***********************************************************************/
-stmm_table * Abc_NtkFraigEquiv( Fraig_Man_t * p, Abc_Ntk_t * pNtk, int fUseInv, bool fVerbose )
+stmm_table * Abc_NtkFraigEquiv( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose, int fVeryVerbose )
{
Abc_Obj_t * pList, * pNode, * pNodeAig;
Fraig_Node_t * gNode;
@@ -115,16 +195,16 @@ stmm_table * Abc_NtkFraigEquiv( Fraig_Man_t * p, Abc_Ntk_t * pNtk, int fUseInv,
tStrash2Net = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
Abc_NtkForEachNode( pNtk, pNode, c )
{
+ // skip the constant input nodes
+ if ( Abc_ObjFaninNum(pNode) == 0 )
+ continue;
// get the strashed node
pNodeAig = pNode->pCopy;
// skip the dangling nodes
if ( pNodeAig == NULL )
continue;
- // skip the constant input nodes
- if ( Abc_ObjFaninNum(pNode) == 0 )
- continue;
- // skip the nodes that fanout into POs
- if ( Abc_NodeHasUniqueCoFanout(pNode) )
+ // skip the nodes that fanout into COs
+ if ( Abc_NodeFindCoFanout(pNode) )
continue;
// get the FRAIG node
gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, Abc_ObjIsComplement(pNodeAig) );
@@ -151,22 +231,22 @@ stmm_table * Abc_NtkFraigEquiv( Fraig_Man_t * p, Abc_Ntk_t * pNtk, int fUseInv,
// count nodes in the non-trival classes
for ( pNode = pList; pNode; pNode = pNode->pNext )
Counter++;
-/*
- if ( fVerbose )
+
+ if ( fVeryVerbose )
{
printf( "Class %2d : {", c );
for ( pNode = pList; pNode; pNode = pNode->pNext )
{
pNode->pCopy = NULL;
printf( " %s", Abc_ObjName(pNode) );
- if ( pNode->fPhase ) printf( "(*)" );
+ printf( "(%c)", pNode->fPhase? '-' : '+' );
+ printf( "(%d)", pNode->Level );
}
printf( " }\n" );
c++;
}
-*/
}
- if ( fVerbose )
+ if ( fVerbose || fVeryVerbose )
{
printf( "Sweeping stats for network \"%s\":\n", pNtk->pName );
printf( "Internal nodes = %d. Different functions (up to compl) = %d.\n", Abc_NtkNodeNum(pNtk), stmm_count(tStrash2Net) );
@@ -194,8 +274,6 @@ void Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv,
Abc_Obj_t * pList;
if ( stmm_count(tEquiv) == 0 )
return;
- // assign levels to the nodes of the network
- Abc_NtkGetLevelNum( pNtk );
// merge nodes in the classes
if ( Abc_NtkHasMapping( pNtk ) )
{
@@ -257,8 +335,8 @@ void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUs
{
Arrival1 = Abc_NodeReadArrival(pNodeMin)->Worst;
Arrival2 = Abc_NodeReadArrival(pNode )->Worst;
- assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
- assert( Abc_ObjIsCi(pNode) || Arrival2 > 0 );
+// assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
+// assert( Abc_ObjIsCi(pNode) || Arrival2 > 0 );
if ( Arrival1 > Arrival2 ||
Arrival1 == Arrival2 && pNodeMin->Level > pNode->Level ||
Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level &&
@@ -277,8 +355,8 @@ void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUs
{
Arrival1 = Abc_NodeReadArrival(pNodeMin)->Worst;
Arrival2 = Abc_NodeReadArrival(pNode )->Worst;
- assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
- assert( Abc_ObjIsCi(pNode) || Arrival2 > 0 );
+// assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
+// assert( Abc_ObjIsCi(pNode) || Arrival2 > 0 );
if ( Arrival1 > Arrival2 ||
Arrival1 == Arrival2 && pNodeMin->Level > pNode->Level ||
Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level &&
@@ -352,7 +430,7 @@ void Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv,
return;
// add the invertor
- pNodeMinInv = Abc_NodeCreateInv( pNtk, pNodeMin );
+ pNodeMinInv = Abc_NtkCreateNodeInv( pNtk, pNodeMin );
// move the fanouts of the inverted nodes
for ( pNode = pListInv; pNode; pNode = pNode->pNext )
@@ -394,19 +472,36 @@ int Abc_NodeDroppingCost( Abc_Obj_t * pNode )
int Abc_NtkCleanup( Abc_Ntk_t * pNtk, int fVerbose )
{
Vec_Ptr_t * vNodes;
+ int Counter;
+ assert( Abc_NtkIsLogic(pNtk) );
+ // mark the nodes reachable from the POs
+ vNodes = Abc_NtkDfs( pNtk, 0 );
+ Counter = Abc_NtkReduceNodes( pNtk, vNodes );
+ if ( fVerbose )
+ printf( "Cleanup removed %d dangling nodes.\n", Counter );
+ Vec_PtrFree( vNodes );
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Preserves the nodes collected in the array.]
+
+ Description [Returns the number of nodes removed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NtkReduceNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes )
+{
Abc_Obj_t * pNode;
int i, Counter;
+ assert( Abc_NtkIsLogic(pNtk) );
// mark the nodes reachable from the POs
- vNodes = Abc_NtkDfs( pNtk, 0 );
- for ( i = 0; i < vNodes->nSize; i++ )
- {
- pNode = vNodes->pArray[i];
+ Vec_PtrForEachEntry( vNodes, pNode, i )
pNode->fMarkA = 1;
- }
- Vec_PtrFree( vNodes );
- // if it is an AIG, also mark the constant 1 node
- if ( Abc_NtkIsStrash(pNtk) )
- Abc_AigConst1(pNtk->pManFunc)->fMarkA = 1;
// remove the non-marked nodes
Counter = 0;
Abc_NtkForEachNode( pNtk, pNode, i )
@@ -416,16 +511,11 @@ int Abc_NtkCleanup( Abc_Ntk_t * pNtk, int fVerbose )
Counter++;
}
// unmark the remaining nodes
- Abc_NtkForEachNode( pNtk, pNode, i )
+ Vec_PtrForEachEntry( vNodes, pNode, i )
pNode->fMarkA = 0;
- if ( fVerbose )
- printf( "Cleanup removed %d dangling nodes.\n", Counter );
// check
if ( !Abc_NtkCheck( pNtk ) )
- {
printf( "Abc_NtkCleanup: The network check has failed.\n" );
- return -1;
- }
return Counter;
}
@@ -445,85 +535,40 @@ int Abc_NtkCleanup( Abc_Ntk_t * pNtk, int fVerbose )
***********************************************************************/
int Abc_NtkSweep( Abc_Ntk_t * pNtk, int fVerbose )
{
- Abc_Obj_t * pNode;
- int i, fConvert, nSwept, nSweptNew;
- assert( Abc_NtkIsSopLogic(pNtk) || Abc_NtkIsBddLogic(pNtk) );
- // convert to the BDD representation
- fConvert = 0;
- if ( Abc_NtkIsSopLogic(pNtk) )
- Abc_NtkSopToBdd(pNtk), fConvert = 1;
- // perform cleanup to get rid of dangling nodes
- nSwept = Abc_NtkCleanup( pNtk, 0 );
- // make the network minimum base
- Abc_NtkRemoveDupFanins(pNtk);
- Abc_NtkMinimumBase(pNtk);
- do
- {
- // sweep constants and single-input nodes
- Abc_NtkForEachNode( pNtk, pNode, i )
- if ( Abc_ObjFaninNum(pNode) < 2 )
- Abc_NodeSweep( pNode, fVerbose );
- // make the network minimum base
- Abc_NtkRemoveDupFanins(pNtk);
- Abc_NtkMinimumBase(pNtk);
- // perform final clean up (in case new danglies are created)
- nSweptNew = Abc_NtkCleanup( pNtk, 0 );
- nSwept += nSweptNew;
- }
- while ( nSweptNew );
- // conver back to BDD
- if ( fConvert )
- Abc_NtkBddToSop(pNtk);
- // report
- if ( fVerbose )
- printf( "Sweep removed %d nodes.\n", nSwept );
- // check
- if ( !Abc_NtkCheck( pNtk ) )
+ Vec_Ptr_t * vNodes;
+ Abc_Obj_t * pNode, * pFanout, * pDriver;
+ int i, nNodesOld;
+ assert( Abc_NtkIsLogic(pNtk) );
+ // convert network to BDD representation
+ if ( !Abc_NtkToBdd(pNtk) )
{
- printf( "Abc_NtkSweep: The network check has failed.\n" );
- return -1;
+ fprintf( stdout, "Converting to BDD has failed.\n" );
+ return 1;
}
- return nSwept;
-}
-
-/**Function*************************************************************
-
- Synopsis [Tranditional sweep of the network.]
-
- Description [Propagates constant and single-input node, removes dangling nodes.]
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Abc_NodeSweep( Abc_Obj_t * pNode, int fVerbose )
-{
- Vec_Ptr_t * vFanout = pNode->pNtk->vPtrTemp;
- Abc_Obj_t * pFanout, * pDriver;
- int i;
- assert( Abc_ObjFaninNum(pNode) < 2 );
- assert( Abc_ObjFanoutNum(pNode) > 0 );
- // iterate through the fanouts
- Abc_NodeCollectFanouts( pNode, vFanout );
- Vec_PtrForEachEntry( vFanout, pFanout, i )
+ // perform cleanup
+ nNodesOld = Abc_NtkNodeNum(pNtk);
+ Abc_NtkCleanup( pNtk, 0 );
+ // prepare nodes for sweeping
+ Abc_NtkRemoveDupFanins(pNtk);
+ Abc_NtkMinimumBase(pNtk);
+ // collect sweepable nodes
+ vNodes = Vec_PtrAlloc( 100 );
+ Abc_NtkForEachNode( pNtk, pNode, i )
+ if ( Abc_ObjFaninNum(pNode) < 2 )
+ Vec_PtrPush( vNodes, pNode );
+ // sweep the nodes
+ while ( Vec_PtrSize(vNodes) > 0 )
{
- if ( Abc_ObjIsCo(pFanout) )
- {
- if ( Abc_ObjFaninNum(pNode) == 1 )
- {
- pDriver = Abc_ObjFanin0(pNode);
- if ( Abc_ObjIsCi(pDriver) || Abc_ObjFanoutNum(pDriver) > 1 || Abc_ObjFanoutNum(pNode) > 1 )
- continue;
- // the driver is a node and its only fanout is this node
- if ( Abc_NodeIsInv(pNode) )
- pDriver->pData = Cudd_Not(pDriver->pData);
- // replace the fanin of the fanout
- Abc_ObjPatchFanin( pFanout, pNode, pDriver );
- }
+ // get any sweepable node
+ pNode = Vec_PtrPop(vNodes);
+ if ( !Abc_ObjIsNode(pNode) )
continue;
- }
- // the fanout is a regular node
+ // get any non-CO fanout of this node
+ pFanout = Abc_NodeFindNonCoFanout(pNode);
+ if ( pFanout == NULL )
+ continue;
+ assert( Abc_ObjIsNode(pFanout) );
+ // transform the function of the fanout
if ( Abc_ObjFaninNum(pNode) == 0 )
Abc_NodeConstantInput( pFanout, pNode, Abc_NodeIsConst0(pNode) );
else
@@ -534,9 +579,44 @@ void Abc_NodeSweep( Abc_Obj_t * pNode, int fVerbose )
Abc_NodeComplementInput( pFanout, pNode );
Abc_ObjPatchFanin( pFanout, pNode, pDriver );
}
+ Abc_NodeRemoveDupFanins( pFanout );
+ Abc_NodeMinimumBase( pFanout );
+ // check if the fanout should be added
+ if ( Abc_ObjFaninNum(pFanout) < 2 )
+ Vec_PtrPush( vNodes, pFanout );
+ // check if the node has other fanouts
+ if ( Abc_ObjFanoutNum(pNode) > 0 )
+ Vec_PtrPush( vNodes, pNode );
+ else
+ Abc_NtkDeleteObj_rec( pNode, 1 );
+ }
+ Vec_PtrFree( vNodes );
+ // sweep a node into its CO fanout if all of this is true:
+ // (a) this node is a single-input node
+ // (b) the driver of the node has only one fanout (this node)
+ // (c) the driver is a node
+ Abc_NtkForEachCo( pNtk, pFanout, i )
+ {
+ pNode = Abc_ObjFanin0(pFanout);
+ if ( Abc_ObjFaninNum(pNode) != 1 )
+ continue;
+ pDriver = Abc_ObjFanin0(pNode);
+ if ( !(Abc_ObjFanoutNum(pDriver) == 1 && Abc_ObjIsNode(pDriver)) )
+ continue;
+ // trasform this CO
+ if ( Abc_NodeIsInv(pNode) )
+ pDriver->pData = Cudd_Not(pDriver->pData);
+ Abc_ObjPatchFanin( pFanout, pNode, pDriver );
}
+ // perform cleanup
+ Abc_NtkCleanup( pNtk, 0 );
+ // report
+ if ( fVerbose )
+ printf( "Sweep removed %d nodes.\n", nNodesOld - Abc_NtkNodeNum(pNtk) );
+ return nNodesOld - Abc_NtkNodeNum(pNtk);
}
+
/**Function*************************************************************
Synopsis [Replaces the local function by its cofactor.]
@@ -554,7 +634,7 @@ void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, bool fConst0
DdNode * bVar, * bTemp;
int iFanin;
assert( Abc_NtkIsBddLogic(pNode->pNtk) );
- if ( (iFanin = Vec_FanFindEntry( &pNode->vFanins, pFanin->Id )) == -1 )
+ if ( (iFanin = Vec_IntFind( &pNode->vFanins, pFanin->Id )) == -1 )
{
printf( "Node %s should be among", Abc_ObjName(pFanin) );
printf( " the fanins of node %s...\n", Abc_ObjName(pNode) );
@@ -582,7 +662,7 @@ void Abc_NodeComplementInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
DdNode * bVar, * bCof0, * bCof1;
int iFanin;
assert( Abc_NtkIsBddLogic(pNode->pNtk) );
- if ( (iFanin = Vec_FanFindEntry( &pNode->vFanins, pFanin->Id )) == -1 )
+ if ( (iFanin = Vec_IntFind( &pNode->vFanins, pFanin->Id )) == -1 )
{
printf( "Node %s should be among", Abc_ObjName(pFanin) );
printf( " the fanins of node %s...\n", Abc_ObjName(pNode) );
@@ -597,6 +677,270 @@ void Abc_NodeComplementInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
Cudd_RecursiveDeref( dd, bCof1 );
}
+
+
+/**Function*************************************************************
+
+ Synopsis [Removes all objects whose trav ID is not current.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NodeRemoveNonCurrentObjects( Abc_Ntk_t * pNtk )
+{
+ Abc_Obj_t * pObj;
+ int Counter, i;
+ int fVerbose = 0;
+
+ // report on the nodes to be deleted
+ if ( fVerbose )
+ {
+ printf( "These nodes will be deleted: \n" );
+ Abc_NtkForEachObj( pNtk, pObj, i )
+ if ( !Abc_NodeIsTravIdCurrent( pObj ) )
+ {
+ printf( " " );
+ Abc_ObjPrint( stdout, pObj );
+ }
+ }
+
+ // delete the nodes
+ Counter = 0;
+ Abc_NtkForEachObj( pNtk, pObj, i )
+ if ( !Abc_NodeIsTravIdCurrent( pObj ) )
+ {
+ Abc_NtkDeleteObj( pObj );
+ Counter++;
+ }
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Check if the fanin of this latch is a constant.]
+
+ Description [Returns 0/1 if constant; -1 if not a constant.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Abc_NtkSetTravId_rec( Abc_Obj_t * pObj )
+{
+ Abc_NodeSetTravIdCurrent(pObj);
+ if ( Abc_ObjFaninNum(pObj) == 0 )
+ return;
+ assert( Abc_ObjFaninNum(pObj) == 1 );
+ Abc_NtkSetTravId_rec( Abc_ObjFanin0(pObj) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Check if the fanin of this latch is a constant.]
+
+ Description [Returns 0/1 if constant; -1 if not a constant.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NtkCheckConstant_rec( Abc_Obj_t * pObj )
+{
+ if ( Abc_ObjFaninNum(pObj) == 0 )
+ {
+ if ( !Abc_ObjIsNode(pObj) )
+ return -1;
+ if ( Abc_NodeIsConst0(pObj) )
+ return 0;
+ if ( Abc_NodeIsConst1(pObj) )
+ return 1;
+ assert( 0 );
+ return -1;
+ }
+ if ( Abc_ObjIsLatch(pObj) || Abc_ObjFaninNum(pObj) > 1 )
+ return -1;
+ if ( !Abc_ObjIsNode(pObj) || Abc_NodeIsBuf(pObj) )
+ return Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
+ if ( Abc_NodeIsInv(pObj) )
+ {
+ int RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
+ if ( RetValue == 0 )
+ return 1;
+ if ( RetValue == 1 )
+ return 0;
+ return RetValue;
+ }
+ assert( 0 );
+ return -1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Removes redundant latches.]
+
+ Description [The redundant latches are of two types:
+ - Latches fed by a constant which matches the init value of the latch.
+ - Latches fed by a constant which does not match the init value of the latch
+ can be all replaced by one latch.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NtkLatchSweep( Abc_Ntk_t * pNtk )
+{
+ Abc_Obj_t * pFanin, * pLatch, * pLatchPivot = NULL;
+ int Counter, RetValue, i;
+ Counter = 0;
+ // go through the latches
+ Abc_NtkForEachLatch( pNtk, pLatch, i )
+ {
+ // check if the latch has constant input
+ RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pLatch) );
+ if ( RetValue == -1 )
+ continue;
+ // found a latch with constant fanin
+ if ( (RetValue == 1 && Abc_LatchIsInit0(pLatch)) ||
+ (RetValue == 0 && Abc_LatchIsInit1(pLatch)) )
+ {
+ // fanin constant differs from the latch init value
+ if ( pLatchPivot == NULL )
+ {
+ pLatchPivot = pLatch;
+ continue;
+ }
+ if ( Abc_LatchInit(pLatch) != Abc_LatchInit(pLatchPivot) ) // add inverter
+ pFanin = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanout0(pLatchPivot) );
+ else
+ pFanin = Abc_ObjFanout0(pLatchPivot);
+ }
+ else
+ pFanin = Abc_ObjFanin0(Abc_ObjFanin0(pLatch));
+ // replace latch
+ Abc_ObjTransferFanout( Abc_ObjFanout0(pLatch), pFanin );
+ // delete the extra nodes
+ Abc_NtkDeleteObj_rec( Abc_ObjFanout0(pLatch), 0 );
+ Counter++;
+ }
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Replaces autonumnous logic by free inputs.]
+
+ Description [Assumes that non-autonomous logic is marked with
+ the current ID.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NtkReplaceAutonomousLogic( Abc_Ntk_t * pNtk )
+{
+ Abc_Obj_t * pNode, * pFanin;
+ Vec_Ptr_t * vNodes;
+ int i, k, Counter;
+ // collect the nodes that feed into the reachable logic
+ vNodes = Vec_PtrAlloc( 100 );
+ Abc_NtkForEachObj( pNtk, pNode, i )
+ {
+ // skip non-visited fanins
+ if ( !Abc_NodeIsTravIdCurrent(pNode) )
+ continue;
+ // look for non-visited fanins
+ Abc_ObjForEachFanin( pNode, pFanin, k )
+ {
+ // skip visited fanins
+ if ( Abc_NodeIsTravIdCurrent(pFanin) )
+ continue;
+ // skip constants and latches fed by constants
+ if ( Abc_NtkCheckConstant_rec(pFanin) != -1 ||
+ (Abc_ObjIsBo(pFanin) && Abc_NtkCheckConstant_rec(Abc_ObjFanin0(Abc_ObjFanin0(pFanin))) != -1) )
+ {
+ Abc_NtkSetTravId_rec( pFanin );
+ continue;
+ }
+ assert( !Abc_ObjIsLatch(pFanin) );
+ Vec_PtrPush( vNodes, pFanin );
+ }
+ }
+ Vec_PtrUniqify( vNodes, Abc_ObjPointerCompare );
+ // replace these nodes by the PIs
+ Vec_PtrForEachEntry( vNodes, pNode, i )
+ {
+ pFanin = Abc_NtkCreatePi(pNtk);
+ Abc_ObjAssignName( pFanin, Abc_ObjName(pFanin), NULL );
+ Abc_NodeSetTravIdCurrent( pFanin );
+ Abc_ObjTransferFanout( pNode, pFanin );
+ }
+ Counter = Vec_PtrSize(vNodes);
+ Vec_PtrFree( vNodes );
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sequential cleanup.]
+
+ Description [Performs three tasks:
+ - Removes logic that does not feed into POs.
+ - Removes latches driven by constant values equal to the initial state.
+ - Replaces the autonomous components by additional PI variables.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NtkCleanupSeq( Abc_Ntk_t * pNtk, int fLatchSweep, int fAutoSweep, int fVerbose )
+{
+ Vec_Ptr_t * vNodes;
+ int Counter;
+ assert( Abc_NtkIsLogic(pNtk) );
+ // mark the nodes reachable from the POs
+ vNodes = Abc_NtkDfsSeq( pNtk );
+ Vec_PtrFree( vNodes );
+ // remove the non-marked nodes
+ Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
+ if ( fVerbose )
+ printf( "Cleanup removed %4d dangling objects.\n", Counter );
+ // check if some of the latches can be removed
+ if ( fLatchSweep )
+ {
+ Counter = Abc_NtkLatchSweep( pNtk );
+ if ( fVerbose )
+ printf( "Cleanup removed %4d redundant latches.\n", Counter );
+ }
+ // detect the autonomous components
+ if ( fAutoSweep )
+ {
+ vNodes = Abc_NtkDfsSeqReverse( pNtk );
+ Vec_PtrFree( vNodes );
+ // replace them by PIs
+ Counter = Abc_NtkReplaceAutonomousLogic( pNtk );
+ if ( fVerbose )
+ printf( "Cleanup added %4d additional PIs.\n", Counter );
+ // remove the non-marked nodes
+ Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
+ if ( fVerbose )
+ printf( "Cleanup removed %4d autonomous objects.\n", Counter );
+ }
+ // check
+ if ( !Abc_NtkCheck( pNtk ) )
+ printf( "Abc_NtkCleanupSeq: The network check has failed.\n" );
+ return 1;
+}
+
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////