/**CFile****************************************************************
FileName [abcRr.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Redundancy removal.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: abcRr.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "base/abc/abc.h"
#include "proof/fraig/fraig.h"
#include "opt/sim/sim.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
typedef struct Abc_RRMan_t_ Abc_RRMan_t;
struct Abc_RRMan_t_
{
// the parameters
Abc_Ntk_t * pNtk; // the network
int nFaninLevels; // the number of fanin levels
int nFanoutLevels; // the number of fanout levels
// the node/fanin/fanout
Abc_Obj_t * pNode; // the node
Abc_Obj_t * pFanin; // the fanin
Abc_Obj_t * pFanout; // the fanout
// the intermediate cones
Vec_Ptr_t * vFaninLeaves; // the leaves of the fanin cone
Vec_Ptr_t * vFanoutRoots; // the roots of the fanout cone
// the window
Vec_Ptr_t * vLeaves; // the leaves of the window
Vec_Ptr_t * vCone; // the internal nodes of the window
Vec_Ptr_t * vRoots; // the roots of the window
Abc_Ntk_t * pWnd; // the window derived for the edge
// the miter
Abc_Ntk_t * pMiter; // the miter derived from the window
Prove_Params_t * pParams; // the miter proving parameters
// statistical variables
int nNodesOld; // the old number of nodes
int nLevelsOld; // the old number of levels
int nEdgesTried; // the number of nodes tried
int nEdgesRemoved; // the number of nodes proved
abctime timeWindow; // the time to construct the window
abctime timeMiter; // the time to construct the miter
abctime timeProve; // the time to prove the miter
abctime timeUpdate; // the network update time
abctime timeTotal; // the total runtime
};
static Abc_RRMan_t * Abc_RRManStart();
static void Abc_RRManStop( Abc_RRMan_t * p );
static void Abc_RRManPrintStats( Abc_RRMan_t * p );
static void Abc_RRManClean( Abc_RRMan_t * p );
static int Abc_NtkRRProve( Abc_RRMan_t * p );
static int Abc_NtkRRUpdate( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, Abc_Obj_t * pFanin, Abc_Obj_t * pFanout );
static int Abc_NtkRRWindow( Abc_RRMan_t * p );
static int Abc_NtkRRTfi_int( Vec_Ptr_t * vLeaves, int LevelLimit );
static int Abc_NtkRRTfo_int( Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, int LevelLimit, Abc_Obj_t * pEdgeFanin, Abc_Obj_t * pEdgeFanout );
static int Abc_NtkRRTfo_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vRoots, int LevelLimit );
static void Abc_NtkRRTfi_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, int LevelLimit );
static Abc_Ntk_t * Abc_NtkWindow( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Vec_Ptr_t * vRoots );
static void Abc_NtkRRSimulateStart( Abc_Ntk_t * pNtk );
static void Abc_NtkRRSimulateStop( Abc_Ntk_t * pNtk );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Removes stuck-at redundancies.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRR( Abc_Ntk_t * pNtk, int nFaninLevels, int nFanoutLevels, int fUseFanouts, int fVerbose )
{
ProgressBar * pProgress;
Abc_RRMan_t * p;
Abc_Obj_t * pNode, * pFanin, * pFanout;
int i, k, m, nNodes, RetValue;
abctime clk, clkTotal = Abc_Clock();
// start the manager
p = Abc_RRManStart();
p->pNtk = pNtk;
p->nFaninLevels = nFaninLevels;
p->nFanoutLevels = nFanoutLevels;
p->nNodesOld = Abc_NtkNodeNum(pNtk);
p->nLevelsOld = Abc_AigLevel(pNtk);
// remember latch values
// Abc_NtkForEachLatch( pNtk, pNode, i )
// pNode->pNext = pNode->pData;
// go through the nodes
Abc_NtkCleanCopy(pNtk);
nNodes = Abc_NtkObjNumMax(pNtk);
Abc_NtkRRSimulateStart(pNtk);
pProgress = Extra_ProgressBarStart( stdout, nNodes );
Abc_NtkForEachNode( pNtk, pNode, i )
{
Extra_ProgressBarUpdate( pProgress, i, NULL );
// stop if all nodes have been tried once
if ( i >= nNodes )
break;
// skip the constant node
// if ( Abc_NodeIsConst(pNode) )
// continue;
// skip persistant nodes
if ( Abc_NodeIsPersistant(pNode) )
continue;
// skip the nodes with many fanouts
if ( Abc_ObjFanoutNum(pNode) > 1000 )
continue;
// construct the window
if ( !fUseFanouts )
{
Abc_ObjForEachFanin( pNode, pFanin, k )
{
// skip the nodes with only one fanout (tree nodes)
if ( Abc_ObjFanoutNum(pFanin) == 1 )
continue;
/*
if ( pFanin->Id == 228 && pNode->Id == 2649 )
{
int k = 0;
}
*/
p->nEdgesTried++;
Abc_RRManClean( p );
p->pNode = pNode;
p->pFanin = pFanin;
p->pFanout = NULL;
clk = Abc_Clock();
RetValue = Abc_NtkRRWindow( p );
p->timeWindow += Abc_Clock() - clk;
if ( !RetValue )
continue;
/*
if ( pFanin->Id == 228 && pNode->Id == 2649 )
{
Abc_NtkShowAig( p->pWnd, 0 );
}
*/
clk = Abc_Clock();
RetValue = Abc_NtkRRProve( p );
p->timeMiter += Abc_Clock() - clk;
if ( !RetValue )
continue;
//printf( "%d -> %d (%d)\n", pFanin->Id, pNode->Id, k );
clk = Abc_Clock();
Abc_NtkRRUpdate( pNtk, p->pNode, p->pFanin, p->pFanout );
p->timeUpdate += Abc_Clock() - clk;
p->nEdgesRemoved++;
break;
}
continue;
}
// use the fanouts
Abc_ObjForEachFanin( pNode, pFanin, k )
Abc_ObjForEachFanout( pNode, pFanout, m )
{
// skip the nodes with only one fanout (tree nodes)
// if ( Abc_ObjFanoutNum(pFanin) == 1 && Abc_ObjFanoutNum(pNode) == 1 )
// continue;
p->nEdgesTried++;
Abc_RRManClean( p );
p->pNode = pNode;
p->pFanin = pFanin;
p->pFanout = pFanout;
clk = Abc_Clock();
RetValue = Abc_NtkRRWindow( p );
p->timeWindow += Abc_Clock() - clk;
if ( !RetValue )
continue;
clk = Abc_Clock();
RetValue = Abc_NtkRRProve( p );
p->timeMiter += Abc_Clock() - clk;
if ( !RetValue )
continue;
clk = Abc_Clock();
Abc_NtkRRUpdate( pNtk, p->pNode, p->pFanin, p->pFanout );
p->timeUpdate += Abc_Clock() - clk;
p->nEdgesRemoved++;
break;
}
}
Abc_NtkRRSimulateStop(pNtk);
Extra_ProgressBarStop( pProgress );
p->timeTotal = Abc_Clock() - clkTotal;
if ( fVerbose )
Abc_RRManPrintStats( p );
Abc_RRManStop( p );
// restore latch values
// Abc_NtkForEachLatch( pNtk, pNode, i )
// pNode->pData = pNode->pNext, pNode->pNext = NULL;
// put the nodes into the DFS order and reassign their IDs
Abc_NtkReassignIds( pNtk );
Abc_NtkLevel( pNtk );
// check
if ( !Abc_NtkCheck( pNtk ) )
{
printf( "Abc_NtkRR: The network check has failed.\n" );
return 0;
}
return 1;
}
/**Function*************************************************************
Synopsis [Start the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_RRMan_t * Abc_RRManStart()
{
Abc_RRMan_t * p;
p = ABC_ALLOC( Abc_RRMan_t, 1 );
memset( p, 0, sizeof(Abc_RRMan_t) );
p->vFaninLeaves = Vec_PtrAlloc( 100 ); // the leaves of the fanin cone
p->vFanoutRoots = Vec_PtrAlloc( 100 ); // the roots of the fanout cone
p->vLeaves = Vec_PtrAlloc( 100 ); // the leaves of the window
p->vCone = Vec_PtrAlloc( 100 ); // the internal nodes of the window
p->vRoots = Vec_PtrAlloc( 100 ); // the roots of the window
p->pParams = ABC_ALLOC( Prove_Params_t, 1 );
memset( p->pParams, 0, sizeof(Prove_Params_t) );
Prove_ParamsSetDefault( p->pParams );
return p;
}
/**Function*************************************************************
Synopsis [Stop the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_RRManStop( Abc_RRMan_t * p )
{
Abc_RRManClean( p );
Vec_PtrFree( p->vFaninLeaves );
Vec_PtrFree( p->vFanoutRoots );
Vec_PtrFree( p->vLeaves );
Vec_PtrFree( p->vCone );
Vec_PtrFree( p->vRoots );
ABC_FREE( p->pParams );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Stop the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_RRManPrintStats( Abc_RRMan_t * p )
{
double Ratio = 100.0*(p->nNodesOld - Abc_NtkNodeNum(p->pNtk))/p->nNodesOld;
printf( "Redundancy removal statistics:\n" );
printf( "Edges tried = %6d.\n", p->nEdgesTried );
printf( "Edges removed = %6d. (%5.2f %%)\n", p->nEdgesRemoved, 100.0*p->nEdgesRemoved/p->nEdgesTried );
printf( "Node gain = %6d. (%5.2f %%)\n", p->nNodesOld - Abc_NtkNodeNum(p->pNtk), Ratio );
printf( "Level gain = %6d.\n", p->nLevelsOld - Abc_AigLevel(p->pNtk) );
ABC_PRT( "Windowing ", p->timeWindow );
ABC_PRT( "Miter ", p->timeMiter );
ABC_PRT( " Construct ", p->timeMiter - p->timeProve );
ABC_PRT( " Prove ", p->timeProve );
ABC_PRT( "Update ", p->timeUpdate );
ABC_PRT( "TOTAL ", p->timeTotal );
}
/**Function*************************************************************
Synopsis [Clean the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_RRManClean( Abc_RRMan_t * p )
{
p->pNode = NULL;
p->pFanin = NULL;
p->pFanout = NULL;
Vec_PtrClear( p->vFaninLeaves );
Vec_PtrClear( p->vFanoutRoots );
Vec_PtrClear( p->vLeaves );
Vec_PtrClear( p->vCone );
Vec_PtrClear( p->vRoots );
if ( p->pWnd ) Abc_NtkDelete( p->pWnd );
if ( p->pMiter ) Abc_NtkDelete( p->pMiter );
p->pWnd = NULL;
p->pMiter = NULL;
}
/**Function*************************************************************
Synopsis [Returns 1 if the miter is constant 0.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRRProve( Abc_RRMan_t * p )
{
Abc_Ntk_t * pWndCopy;
int RetValue;
abctime clk;
// Abc_NtkShowAig( p->pWnd, 0 );
pWndCopy = Abc_NtkDup( p->pWnd );
Abc_NtkRRUpdate( pWndCopy, p->pNode->pCopy->pCopy, p->pFanin->pCopy->pCopy, p->pFanout? p->pFanout->pCopy->pCopy : NULL );
if ( !Abc_NtkIsDfsOrdered(pWndCopy) )
Abc_NtkReassignIds(pWndCopy);
p->pMiter = Abc_NtkMiter( p->pWnd, pWndCopy, 1, 0, 0, 0 );
Abc_NtkDelete( pWndCopy );
clk = Abc_Clock();
RetValue = Abc_NtkMiterProve( &p->pMiter, p->pParams );
p->timeProve += Abc_Clock() - clk;
if ( RetValue == 1 )
return 1;
return 0;
}
/**Function*************************************************************
Synopsis [Updates the network after redundancy removal.]
Description [This procedure assumes that non-control value of the fanin
was proved redundant. It is okay to concentrate on non-control values
because the control values can be seen as redundancy of the fanout edge.]
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRRUpdate( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, Abc_Obj_t * pFanin, Abc_Obj_t * pFanout )
{
Abc_Obj_t * pNodeNew, * pFanoutNew;
assert( pFanout == NULL );
assert( !Abc_ObjIsComplement(pNode) );
assert( !Abc_ObjIsComplement(pFanin) );
assert( !Abc_ObjIsComplement(pFanout) );
// find the node after redundancy removal
if ( pFanin == Abc_ObjFanin0(pNode) )
pNodeNew = Abc_ObjChild1(pNode);
else if ( pFanin == Abc_ObjFanin1(pNode) )
pNodeNew = Abc_ObjChild0(pNode);
else assert( 0 );
// replace
if ( pFanout == NULL )
{
Abc_AigReplace( (Abc_Aig_t *)pNtk->pManFunc, pNode, pNodeNew, 1 );
return 1;
}
// find the fanout after redundancy removal
if ( pNode == Abc_ObjFanin0(pFanout) )
pFanoutNew = Abc_AigAnd( (Abc_Aig_t *)pNtk->pManFunc, Abc_ObjNotCond(pNodeNew,Abc_ObjFaninC0(pFanout)), Abc_ObjChild1(pFanout) );
else if ( pNode == Abc_ObjFanin1(pFanout) )
pFanoutNew = Abc_AigAnd( (Abc_Aig_t *)pNtk->pManFunc, Abc_ObjNotCond(pNodeNew,Abc_ObjFaninC1(pFanout)), Abc_ObjChild0(pFanout) );
else assert( 0 );
// replace
Abc_AigReplace( (Abc_Aig_t *)pNtk->pManFunc, pFanout, pFanoutNew, 1 );
return 1;
}
/**Function*************************************************************
Synopsis [Constructs window for checking RR.]
Description [If the window (p->pWnd) with the given scope (p->nFaninLevels,
p->nFanoutLevels) cannot be constructed, returns 0. Otherwise, returns 1.
The levels are measured from the fanin node (pFanin) and the fanout node
(pEdgeFanout), respectively.]
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRRWindow( Abc_RRMan_t * p )
{
Abc_Obj_t * pObj, * pEdgeFanin, * pEdgeFanout;
int i, LevelMin, LevelMax, RetValue;
// get the edge
pEdgeFanout = p->pFanout? p->pFanout : p->pNode;
pEdgeFanin = p->pFanout? p->pNode : p->pFanin;
// get the minimum and maximum levels of the window
LevelMin = Abc_MaxInt( 0, ((int)p->pFanin->Level) - p->nFaninLevels );
LevelMax = (int)pEdgeFanout->Level + p->nFanoutLevels;
// start the TFI leaves with the fanin
Abc_NtkIncrementTravId( p->pNtk );
Abc_NodeSetTravIdCurrent( p->pFanin );
Vec_PtrPush( p->vFaninLeaves, p->pFanin );
// mark the TFI cone and collect the leaves down to the given level
while ( Abc_NtkRRTfi_int(p->vFaninLeaves, LevelMin) );
// mark the leaves with the new TravId
Abc_NtkIncrementTravId( p->pNtk );
Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninLeaves, pObj, i )
Abc_NodeSetTravIdCurrent( pObj );
// traverse the TFO cone of the leaves (while skipping the edge)
// (a) mark the nodes in the cone using the current TravId
// (b) collect the nodes that have external fanouts into p->vFanoutRoots
while ( Abc_NtkRRTfo_int(p->vFaninLeaves, p->vFanoutRoots, LevelMax, pEdgeFanin, pEdgeFanout) );
// mark the fanout roots
Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanoutRoots, pObj, i )
pObj->fMarkA = 1;
// collect roots reachable from the fanout (p->vRoots)
RetValue = Abc_NtkRRTfo_rec( pEdgeFanout, p->vRoots, LevelMax + 1 );
// unmark the fanout roots
Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanoutRoots, pObj, i )
pObj->fMarkA = 0;
// return if the window is infeasible
if ( RetValue == 0 )
return 0;
// collect the DFS-ordered new cone (p->vCone) and new leaves (p->vLeaves)
// using the previous marks coming from the TFO cone
Abc_NtkIncrementTravId( p->pNtk );
Vec_PtrForEachEntry( Abc_Obj_t *, p->vRoots, pObj, i )
Abc_NtkRRTfi_rec( pObj, p->vLeaves, p->vCone, LevelMin );
// create a new network
p->pWnd = Abc_NtkWindow( p->pNtk, p->vLeaves, p->vCone, p->vRoots );
return 1;
}
/**Function*************************************************************
Synopsis [Marks the nodes in the TFI and collects their leaves.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRRTfi_int( Vec_Ptr_t * vLeaves, int LevelLimit )
{
Abc_Obj_t * pObj, * pNext;
int i, k, LevelMax, nSize;
assert( LevelLimit >= 0 );
// find the maximum level of leaves
LevelMax = 0;
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
if ( LevelMax < (int)pObj->Level )
LevelMax = pObj->Level;
// if the nodes are all PIs, LevelMax == 0
if ( LevelMax <= LevelLimit )
return 0;
// expand the nodes with the minimum level
nSize = Vec_PtrSize(vLeaves);
Vec_PtrForEachEntryStop( Abc_Obj_t *, vLeaves, pObj, i, nSize )
{
if ( LevelMax != (int)pObj->Level )
continue;
Abc_ObjForEachFanin( pObj, pNext, k )
{
if ( Abc_NodeIsTravIdCurrent(pNext) )
continue;
Abc_NodeSetTravIdCurrent( pNext );
Vec_PtrPush( vLeaves, pNext );
}
}
// remove old nodes (cannot remove a PI)
k = 0;
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
{
if ( LevelMax == (int)pObj->Level )
continue;
Vec_PtrWriteEntry( vLeaves, k++, pObj );
}
Vec_PtrShrink( vLeaves, k );
if ( Vec_PtrSize(vLeaves) > 2000 )
return 0;
return 1;
}
/**Function*************************************************************
Synopsis [Marks the nodes in the TFO and collects their roots.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRRTfo_int( Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, int LevelLimit, Abc_Obj_t * pEdgeFanin, Abc_Obj_t * pEdgeFanout )
{
Abc_Obj_t * pObj, * pNext;
int i, k, LevelMin, nSize, fObjIsRoot;
// find the minimum level of leaves
LevelMin = ABC_INFINITY;
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
if ( LevelMin > (int)pObj->Level )
LevelMin = pObj->Level;
// if the minimum level exceed the limit, we are done
if ( LevelMin > LevelLimit )
return 0;
// expand the nodes with the minimum level
nSize = Vec_PtrSize(vLeaves);
Vec_PtrForEachEntryStop( Abc_Obj_t *, vLeaves, pObj, i, nSize )
{
if ( LevelMin != (int)pObj->Level )
continue;
fObjIsRoot = 0;
Abc_ObjForEachFanout( pObj, pNext, k )
{
// check if the fanout is outside of the cone
if ( Abc_ObjIsCo(pNext) || pNext->Level > (unsigned)LevelLimit )
{
fObjIsRoot = 1;
continue;
}
// skip the edge under check
if ( pObj == pEdgeFanin && pNext == pEdgeFanout )
continue;
// skip the visited fanouts
if ( Abc_NodeIsTravIdCurrent(pNext) )
continue;
Abc_NodeSetTravIdCurrent( pNext );
Vec_PtrPush( vLeaves, pNext );
}
if ( fObjIsRoot )
Vec_PtrPush( vRoots, pObj );
}
// remove old nodes
k = 0;
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
{
if ( LevelMin == (int)pObj->Level )
continue;
Vec_PtrWriteEntry( vLeaves, k++, pObj );
}
Vec_PtrShrink( vLeaves, k );
if ( Vec_PtrSize(vLeaves) > 2000 )
return 0;
return 1;
}
/**Function*************************************************************
Synopsis [Collects the roots in the TFO of the node.]
Description [Note that this procedure can be improved by
marking and skipping the visited nodes.]
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRRTfo_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vRoots, int LevelLimit )
{
Abc_Obj_t * pFanout;
int i;
// if we encountered a node outside of the TFO cone of the fanins, quit
if ( Abc_ObjIsCo(pNode) || pNode->Level > (unsigned)LevelLimit )
return 0;
// if we encountered a node on the boundary, add it to the roots
if ( pNode->fMarkA )
{
Vec_PtrPushUnique( vRoots, pNode );
return 1;
}
// mark the node with the current TravId (needed to have all internal nodes marked)
Abc_NodeSetTravIdCurrent( pNode );
// traverse the fanouts
Abc_ObjForEachFanout( pNode, pFanout, i )
if ( !Abc_NtkRRTfo_rec( pFanout, vRoots, LevelLimit ) )
return 0;
return 1;
}
/**Function*************************************************************
Synopsis [Collects the leaves and cone of the roots.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRRTfi_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, int LevelLimit )
{
Abc_Obj_t * pFanin;
int i;
// skip visited nodes
if ( Abc_NodeIsTravIdCurrent(pNode) )
return;
// add node to leaves if it is not in TFI cone of the leaves (marked before) or below the limit
if ( !Abc_NodeIsTravIdPrevious(pNode) || (int)pNode->Level <= LevelLimit )
{
Abc_NodeSetTravIdCurrent( pNode );
Vec_PtrPush( vLeaves, pNode );
return;
}
// mark the node as visited
Abc_NodeSetTravIdCurrent( pNode );
// call for the node's fanins
Abc_ObjForEachFanin( pNode, pFanin, i )
Abc_NtkRRTfi_rec( pFanin, vLeaves, vCone, LevelLimit );
// add the node to the cone in topological order
Vec_PtrPush( vCone, pNode );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Ntk_t * Abc_NtkWindow( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Vec_Ptr_t * vRoots )
{
Abc_Ntk_t * pNtkNew;
Abc_Obj_t * pObj;
int fCheck = 1;
int i;
assert( Abc_NtkIsStrash(pNtk) );
// start the network
pNtkNew = Abc_NtkAlloc( pNtk->ntkType, pNtk->ntkFunc, 1 );
// duplicate the name and the spec
pNtkNew->pName = Extra_UtilStrsav( "temp" );
// map the constant nodes
Abc_AigConst1(pNtk)->pCopy = Abc_AigConst1(pNtkNew);
// create and map the PIs
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
pObj->pCopy = Abc_NtkCreatePi(pNtkNew);
// copy the AND gates
Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, i )
pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pNtkNew->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
// compare the number of nodes before and after
if ( Vec_PtrSize(vCone) != Abc_NtkNodeNum(pNtkNew) )
printf( "Warning: Structural hashing during windowing reduced %d nodes (this is a bug).\n",
Vec_PtrSize(vCone) - Abc_NtkNodeNum(pNtkNew) );
// create the POs
Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
{
assert( !Abc_ObjIsComplement(pObj->pCopy) );
Abc_ObjAddFanin( Abc_NtkCreatePo(pNtkNew), pObj->pCopy );
}
// add the PI/PO names
Abc_NtkAddDummyPiNames( pNtkNew );
Abc_NtkAddDummyPoNames( pNtkNew );
// check
if ( fCheck && !Abc_NtkCheck( pNtkNew ) )
{
printf( "Abc_NtkWindow: The network check has failed.\n" );
return NULL;
}
return pNtkNew;
}
/**Function*************************************************************
Synopsis [Starts simulation to detect non-redundant edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRRSimulateStart( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
unsigned uData, uData0, uData1;
int i;
Abc_AigConst1(pNtk)->pData = (void *)~((unsigned)0);
Abc_NtkForEachCi( pNtk, pObj, i )
pObj->pData = (void *)(ABC_PTRUINT_T)SIM_RANDOM_UNSIGNED;
Abc_NtkForEachNode( pNtk, pObj, i )
{
if ( i == 0 ) continue;
uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData;
uData = Abc_ObjFaninC0(pObj)? ~uData0 : uData0;
uData &= Abc_ObjFaninC1(pObj)? ~uData1 : uData1;
assert( pObj->pData == NULL );
pObj->pData = (void *)(ABC_PTRUINT_T)uData;
}
}
/**Function*************************************************************
Synopsis [Stops simulation to detect non-redundant edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRRSimulateStop( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
int i;
Abc_NtkForEachObj( pNtk, pObj, i )
pObj->pData = NULL;
}
static void Sim_TraverseNodes_rec( Abc_Obj_t * pRoot, Vec_Str_t * vTargets, Vec_Ptr_t * vNodes );
static void Sim_CollectNodes_rec( Abc_Obj_t * pRoot, Vec_Ptr_t * vField );
static void Sim_SimulateCollected( Vec_Str_t * vTargets, Vec_Ptr_t * vNodes, Vec_Ptr_t * vField );
/**Function*************************************************************
Synopsis [Simulation to detect non-redundant edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Str_t * Abc_NtkRRSimulate( Abc_Ntk_t * pNtk )
{
Vec_Ptr_t * vNodes, * vField;
Vec_Str_t * vTargets;
Abc_Obj_t * pObj;
unsigned uData, uData0, uData1;
int PrevCi, Phase, i, k;
// start the candidates
vTargets = Vec_StrStart( Abc_NtkObjNumMax(pNtk) + 1 );
Abc_NtkForEachNode( pNtk, pObj, i )
{
Phase = ((Abc_ObjFanoutNum(Abc_ObjFanin1(pObj)) > 1) << 1);
Phase |= (Abc_ObjFanoutNum(Abc_ObjFanin0(pObj)) > 1);
Vec_StrWriteEntry( vTargets, pObj->Id, (char)Phase );
}
// simulate patters and store them in copy
Abc_AigConst1(pNtk)->pCopy = (Abc_Obj_t *)~((unsigned)0);
Abc_NtkForEachCi( pNtk, pObj, i )
pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)SIM_RANDOM_UNSIGNED;
Abc_NtkForEachNode( pNtk, pObj, i )
{
if ( i == 0 ) continue;
uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData;
uData = Abc_ObjFaninC0(pObj)? ~uData0 : uData0;
uData &= Abc_ObjFaninC1(pObj)? ~uData1 : uData1;
pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)uData;
}
// store the result in data
Abc_NtkForEachCo( pNtk, pObj, i )
{
uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
if ( Abc_ObjFaninC0(pObj) )
pObj->pData = (void *)(ABC_PTRUINT_T)~uData0;
else
pObj->pData = (void *)(ABC_PTRUINT_T)uData0;
}
// refine the candidates
for ( PrevCi = 0; PrevCi < Abc_NtkCiNum(pNtk); PrevCi = i )
{
vNodes = Vec_PtrAlloc( 10 );
Abc_NtkIncrementTravId( pNtk );
for ( i = PrevCi; i < Abc_NtkCiNum(pNtk); i++ )
{
Sim_TraverseNodes_rec( Abc_NtkCi(pNtk, i), vTargets, vNodes );
if ( Vec_PtrSize(vNodes) > 128 )
break;
}
// collect the marked nodes in the topological order
vField = Vec_PtrAlloc( 10 );
Abc_NtkIncrementTravId( pNtk );
Abc_NtkForEachCo( pNtk, pObj, k )
Sim_CollectNodes_rec( pObj, vField );
// simulate these nodes
Sim_SimulateCollected( vTargets, vNodes, vField );
// prepare for the next loop
Vec_PtrFree( vNodes );
}
// clean
Abc_NtkForEachObj( pNtk, pObj, i )
pObj->pData = NULL;
return vTargets;
}
/**Function*************************************************************
Synopsis [Collects nodes starting from the given node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Sim_TraverseNodes_rec( Abc_Obj_t * pRoot, Vec_Str_t * vTargets, Vec_Ptr_t * vNodes )
{
Abc_Obj_t * pFanout;
char Entry;
int k;
if ( Abc_NodeIsTravIdCurrent(pRoot) )
return;
Abc_NodeSetTravIdCurrent( pRoot );
// save the reached targets
Entry = Vec_StrEntry(vTargets, pRoot->Id);
if ( Entry & 1 )
Vec_PtrPush( vNodes, Abc_ObjNot(pRoot) );
if ( Entry & 2 )
Vec_PtrPush( vNodes, pRoot );
// explore the fanouts
Abc_ObjForEachFanout( pRoot, pFanout, k )
Sim_TraverseNodes_rec( pFanout, vTargets, vNodes );
}
/**Function*************************************************************
Synopsis [Collects nodes starting from the given node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Sim_CollectNodes_rec( Abc_Obj_t * pRoot, Vec_Ptr_t * vField )
{
Abc_Obj_t * pFanin;
int i;
if ( Abc_NodeIsTravIdCurrent(pRoot) )
return;
if ( !Abc_NodeIsTravIdPrevious(pRoot) )
return;
Abc_NodeSetTravIdCurrent( pRoot );
Abc_ObjForEachFanin( pRoot, pFanin, i )
Sim_CollectNodes_rec( pFanin, vField );
if ( !Abc_ObjIsCo(pRoot) )
pRoot->pData = (void *)(ABC_PTRUINT_T)Vec_PtrSize(vField);
Vec_PtrPush( vField, pRoot );
}
/**Function*************************************************************
Synopsis [Simulate the given nodes.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Sim_SimulateCollected( Vec_Str_t * vTargets, Vec_Ptr_t * vNodes, Vec_Ptr_t * vField )
{
Abc_Obj_t * pObj, * pFanin0, * pFanin1, * pDisproved;
Vec_Ptr_t * vSims;
unsigned * pUnsigned, * pUnsignedF;
int i, k, Phase, fCompl;
// get simulation info
vSims = Sim_UtilInfoAlloc( Vec_PtrSize(vField), Vec_PtrSize(vNodes), 0 );
// simulate the nodes
Vec_PtrForEachEntry( Abc_Obj_t *, vField, pObj, i )
{
if ( Abc_ObjIsCi(pObj) )
{
pUnsigned = (unsigned *)Vec_PtrEntry( vSims, i );
for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
pUnsigned[k] = (unsigned)(ABC_PTRUINT_T)pObj->pCopy;
continue;
}
if ( Abc_ObjIsCo(pObj) )
{
pUnsigned = (unsigned *)Vec_PtrEntry( vSims, i );
pUnsignedF = (unsigned *)Vec_PtrEntry( vSims, (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData );
if ( Abc_ObjFaninC0(pObj) )
for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
pUnsigned[k] = ~pUnsignedF[k];
else
for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
pUnsigned[k] = pUnsignedF[k];
// update targets
for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
{
if ( pUnsigned[k] == (unsigned)(ABC_PTRUINT_T)pObj->pData )
continue;
pDisproved = (Abc_Obj_t *)Vec_PtrEntry( vNodes, k );
fCompl = Abc_ObjIsComplement(pDisproved);
pDisproved = Abc_ObjRegular(pDisproved);
Phase = Vec_StrEntry( vTargets, pDisproved->Id );
if ( fCompl )
Phase = (Phase & 2);
else
Phase = (Phase & 1);
Vec_StrWriteEntry( vTargets, pDisproved->Id, (char)Phase );
}
continue;
}
// simulate the node
pFanin0 = Abc_ObjFanin0(pObj);
pFanin1 = Abc_ObjFanin1(pObj);
}
}
/*
{
unsigned uData;
if ( pFanin == Abc_ObjFanin0(pNode) )
{
uData = (unsigned)Abc_ObjFanin1(pNode)->pData;
uData = Abc_ObjFaninC1(pNode)? ~uData : uData;
}
else if ( pFanin == Abc_ObjFanin1(pNode) )
{
uData = (unsigned)Abc_ObjFanin0(pNode)->pData;
uData = Abc_ObjFaninC0(pNode)? ~uData : uData;
}
uData ^= (unsigned)pNode->pData;
// Extra_PrintBinary( stdout, &uData, 32 ); printf( "\n" );
if ( Extra_WordCountOnes(uData) > 8 )
continue;
}
*/
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END