/**CFile****************************************************************
FileName [abcHaig.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Implements history AIG for combinational rewriting.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: abcHaig.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "base/abc/abc.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Collects the nodes in the classes.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Abc_NtkHaigCollectMembers( Hop_Man_t * p )
{
Vec_Ptr_t * vObjs;
Hop_Obj_t * pObj;
int i;
vObjs = Vec_PtrAlloc( 4098 );
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( pObj->pData == NULL )
continue;
pObj->pData = Hop_ObjRepr( pObj );
Vec_PtrPush( vObjs, pObj );
}
return vObjs;
}
/**Function*************************************************************
Synopsis [Creates classes.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Abc_NtkHaigCreateClasses( Vec_Ptr_t * vMembers )
{
Vec_Ptr_t * vClasses;
Hop_Obj_t * pObj, * pRepr;
int i;
// count classes
vClasses = Vec_PtrAlloc( 4098 );
Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
{
pRepr = (Hop_Obj_t *)pObj->pData;
assert( pRepr->pData == NULL );
if ( pRepr->fMarkA == 0 ) // new
{
pRepr->fMarkA = 1;
Vec_PtrPush( vClasses, pRepr );
}
}
// set representatives as representatives
Vec_PtrForEachEntry( Hop_Obj_t *, vClasses, pObj, i )
{
pObj->fMarkA = 0;
pObj->pData = pObj;
}
// go through the members and update
Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
{
pRepr = (Hop_Obj_t *)pObj->pData;
if ( ((Hop_Obj_t *)pRepr->pData)->Id > pObj->Id )
pRepr->pData = pObj;
}
// change representatives of the class
Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
{
pRepr = (Hop_Obj_t *)pObj->pData;
pObj->pData = pRepr->pData;
assert( ((Hop_Obj_t *)pObj->pData)->Id <= pObj->Id );
}
// update classes
Vec_PtrForEachEntry( Hop_Obj_t *, vClasses, pObj, i )
{
pRepr = (Hop_Obj_t *)pObj->pData;
assert( pRepr->pData == pRepr );
// pRepr->pData = NULL;
Vec_PtrWriteEntry( vClasses, i, pRepr );
Vec_PtrPush( vMembers, pObj );
}
Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
if ( pObj->pData == pObj )
pObj->pData = NULL;
/*
Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
{
printf( "ObjId = %4d : ", pObj->Id );
if ( pObj->pData == NULL )
{
printf( "NULL" );
}
else
{
printf( "%4d", ((Hop_Obj_t *)pObj->pData)->Id );
assert( ((Hop_Obj_t *)pObj->pData)->Id <= pObj->Id );
}
printf( "\n" );
}
*/
return vClasses;
}
/**Function*************************************************************
Synopsis [Counts how many data members have non-trivial fanout.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkHaigCountFans( Hop_Man_t * p )
{
Hop_Obj_t * pObj;
int i, Counter = 0;
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( pObj->pData == NULL )
continue;
if ( Hop_ObjRefs(pObj) > 0 )
Counter++;
}
printf( "The number of class members with fanouts = %5d.\n", Counter );
return Counter;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline Hop_Obj_t * Hop_ObjReprHop( Hop_Obj_t * pObj )
{
Hop_Obj_t * pRepr;
assert( pObj->pNext != NULL );
if ( pObj->pData == NULL )
return pObj->pNext;
pRepr = (Hop_Obj_t *)pObj->pData;
assert( pRepr->pData == pRepr );
return Hop_NotCond( pRepr->pNext, pObj->fPhase ^ pRepr->fPhase );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline Hop_Obj_t * Hop_ObjChild0Hop( Hop_Obj_t * pObj ) { return Hop_NotCond( Hop_ObjReprHop(Hop_ObjFanin0(pObj)), Hop_ObjFaninC0(pObj) ); }
static inline Hop_Obj_t * Hop_ObjChild1Hop( Hop_Obj_t * pObj ) { return Hop_NotCond( Hop_ObjReprHop(Hop_ObjFanin1(pObj)), Hop_ObjFaninC1(pObj) ); }
/**Function*************************************************************
Synopsis [Stops history AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Hop_Man_t * Abc_NtkHaigReconstruct( Hop_Man_t * p )
{
Hop_Man_t * pNew;
Hop_Obj_t * pObj;
int i, Counter = 0;
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
pObj->pNext = NULL;
// start the HOP package
pNew = Hop_ManStart();
pNew->vObjs = Vec_PtrAlloc( p->nCreated );
Vec_PtrPush( pNew->vObjs, Hop_ManConst1(pNew) );
// map the constant node
Hop_ManConst1(p)->pNext = Hop_ManConst1(pNew);
// map the CIs
Hop_ManForEachPi( p, pObj, i )
pObj->pNext = Hop_ObjCreatePi(pNew);
// map the internal nodes
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( !Hop_ObjIsNode(pObj) )
continue;
pObj->pNext = Hop_And( pNew, Hop_ObjChild0Hop(pObj), Hop_ObjChild1Hop(pObj) );
// assert( !Hop_IsComplement(pObj->pNext) );
if ( Hop_ManConst1(pNew) == Hop_Regular(pObj->pNext) )
Counter++;
if ( pObj->pData ) // member of the class
Hop_Regular(pObj->pNext)->pData = Hop_Regular(((Hop_Obj_t *)pObj->pData)->pNext);
}
// printf( " Counter = %d.\n", Counter );
// transfer the POs
Hop_ManForEachPo( p, pObj, i )
Hop_ObjCreatePo( pNew, Hop_ObjChild0Hop(pObj) );
// check the new manager
if ( !Hop_ManCheck(pNew) )
{
printf( "Abc_NtkHaigReconstruct: Check for History AIG has failed.\n" );
Hop_ManStop(pNew);
return NULL;
}
return pNew;
}
/**Function*************************************************************
Synopsis [Returns 1 if pOld is in the TFI of pNew.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkHaigCheckTfi_rec( Abc_Obj_t * pNode, Abc_Obj_t * pOld )
{
if ( pNode == NULL )
return 0;
if ( pNode == pOld )
return 1;
// check the trivial cases
if ( Abc_ObjIsCi(pNode) )
return 0;
assert( Abc_ObjIsNode(pNode) );
// if this node is already visited, skip
if ( Abc_NodeIsTravIdCurrent( pNode ) )
return 0;
// mark the node as visited
Abc_NodeSetTravIdCurrent( pNode );
// check the children
if ( Abc_NtkHaigCheckTfi_rec( Abc_ObjFanin0(pNode), pOld ) )
return 1;
if ( Abc_NtkHaigCheckTfi_rec( Abc_ObjFanin1(pNode), pOld ) )
return 1;
// check equivalent nodes
return Abc_NtkHaigCheckTfi_rec( (Abc_Obj_t *)pNode->pData, pOld );
}
/**Function*************************************************************
Synopsis [Returns 1 if pOld is in the TFI of pNew.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkHaigCheckTfi( Abc_Ntk_t * pNtk, Abc_Obj_t * pOld, Abc_Obj_t * pNew )
{
assert( !Abc_ObjIsComplement(pOld) );
assert( !Abc_ObjIsComplement(pNew) );
Abc_NtkIncrementTravId(pNtk);
return Abc_NtkHaigCheckTfi_rec( pNew, pOld );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline Abc_Obj_t * Hop_ObjChild0Next( Hop_Obj_t * pObj ) { return Abc_ObjNotCond( (Abc_Obj_t *)Hop_ObjFanin0(pObj)->pNext, Hop_ObjFaninC0(pObj) ); }
static inline Abc_Obj_t * Hop_ObjChild1Next( Hop_Obj_t * pObj ) { return Abc_ObjNotCond( (Abc_Obj_t *)Hop_ObjFanin1(pObj)->pNext, Hop_ObjFaninC1(pObj) ); }
/**Function*************************************************************
Synopsis [Stops history AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Ntk_t * Abc_NtkHaigRecreateAig( Abc_Ntk_t * pNtk, Hop_Man_t * p )
{
Abc_Ntk_t * pNtkAig;
Abc_Obj_t * pObjOld, * pObjAbcThis, * pObjAbcRepr;
Hop_Obj_t * pObj;
int i;
assert( p->nCreated == Vec_PtrSize(p->vObjs) );
// start the new network
pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
// transfer new nodes to the PIs of HOP
Hop_ManConst1(p)->pNext = (Hop_Obj_t *)Abc_AigConst1( pNtkAig );
Hop_ManForEachPi( p, pObj, i )
pObj->pNext = (Hop_Obj_t *)Abc_NtkCi( pNtkAig, i );
// construct new nodes
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( !Hop_ObjIsNode(pObj) )
continue;
pObj->pNext = (Hop_Obj_t *)Abc_AigAnd( (Abc_Aig_t *)pNtkAig->pManFunc, Hop_ObjChild0Next(pObj), Hop_ObjChild1Next(pObj) );
assert( !Hop_IsComplement(pObj->pNext) );
}
// set the COs
Abc_NtkForEachCo( pNtk, pObjOld, i )
Abc_ObjAddFanin( pObjOld->pCopy, Hop_ObjChild0Next(Hop_ManPo(p,i)) );
// construct choice nodes
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
// skip the node without choices
if ( pObj->pData == NULL )
continue;
// skip the representative of the class
if ( pObj->pData == pObj )
continue;
// do not create choices for constant 1 and PIs
if ( !Hop_ObjIsNode((Hop_Obj_t *)pObj->pData) )
continue;
// get the corresponding new nodes
pObjAbcThis = (Abc_Obj_t *)pObj->pNext;
pObjAbcRepr = (Abc_Obj_t *)((Hop_Obj_t *)pObj->pData)->pNext;
// the new node cannot be already in the class
assert( pObjAbcThis->pData == NULL );
// the new node cannot have fanouts
assert( Abc_ObjFanoutNum(pObjAbcThis) == 0 );
// these should be different nodes
assert( pObjAbcRepr != pObjAbcThis );
// do not create choices if there is a path from pObjAbcThis to pObjAbcRepr
if ( !Abc_NtkHaigCheckTfi( pNtkAig, pObjAbcRepr, pObjAbcThis ) )
{
// find the last node in the class
while ( pObjAbcRepr->pData )
pObjAbcRepr = (Abc_Obj_t *)pObjAbcRepr->pData;
// add the new node at the end of the list
pObjAbcRepr->pData = pObjAbcThis;
}
}
// finish the new network
// Abc_NtkFinalize( pNtk, pNtkAig );
// Abc_AigCleanup( pNtkAig->pManFunc );
// check correctness of the network
if ( !Abc_NtkCheck( pNtkAig ) )
{
printf( "Abc_NtkHaigUse: The network check has failed.\n" );
Abc_NtkDelete( pNtkAig );
return NULL;
}
return pNtkAig;
}
/**Function*************************************************************
Synopsis [Resets representatives.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkHaigResetReprsOld( Hop_Man_t * pMan )
{
Vec_Ptr_t * vMembers, * vClasses;
// collect members of the classes and make them point to reprs
vMembers = Abc_NtkHaigCollectMembers( pMan );
printf( "Collected %6d class members.\n", Vec_PtrSize(vMembers) );
// create classes
vClasses = Abc_NtkHaigCreateClasses( vMembers );
printf( "Collected %6d classes. (Ave = %5.2f)\n", Vec_PtrSize(vClasses),
(float)(Vec_PtrSize(vMembers))/Vec_PtrSize(vClasses) );
Vec_PtrFree( vMembers );
Vec_PtrFree( vClasses );
}
/**Function*************************************************************
Synopsis [Resets representatives.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkHaigResetReprs( Hop_Man_t * p )
{
Hop_Obj_t * pObj, * pRepr;
int i, nClasses, nMembers, nFanouts, nNormals;
// clear self-classes
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
// fix the strange situation of double-loop
pRepr = (Hop_Obj_t *)pObj->pData;
if ( pRepr && pRepr->pData == pObj )
pRepr->pData = pRepr;
// remove self-loops
if ( pObj->pData == pObj )
pObj->pData = NULL;
}
// set representatives
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( pObj->pData == NULL )
continue;
// get representative of the node
pRepr = Hop_ObjRepr( pObj );
pRepr->pData = pRepr;
// set the representative
pObj->pData = pRepr;
}
// make each class point to the smallest topological order
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( pObj->pData == NULL )
continue;
pRepr = Hop_ObjRepr( pObj );
if ( pRepr->Id > pObj->Id )
{
pRepr->pData = pObj;
pObj->pData = pObj;
}
else
pObj->pData = pRepr;
}
// count classes, members, and fanouts - and verify
nMembers = nClasses = nFanouts = nNormals = 0;
Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
{
if ( pObj->pData == NULL )
continue;
// count members
nMembers++;
// count the classes and fanouts
if ( pObj->pData == pObj )
nClasses++;
else if ( Hop_ObjRefs(pObj) > 0 )
nFanouts++;
else
nNormals++;
// compare representatives
pRepr = Hop_ObjRepr( pObj );
assert( pObj->pData == pRepr );
assert( pRepr->Id <= pObj->Id );
}
// printf( "Nodes = %7d. Member = %7d. Classes = %6d. Fanouts = %6d. Normals = %6d.\n",
// Hop_ManNodeNum(p), nMembers, nClasses, nFanouts, nNormals );
return nFanouts;
}
/**Function*************************************************************
Synopsis [Transform HOP manager into the one without loops.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Ntk_t * Abc_NtkHopRemoveLoops( Abc_Ntk_t * pNtk, Hop_Man_t * pMan )
{
Abc_Ntk_t * pNtkAig;
Hop_Man_t * pManTemp;
// iteratively reconstruct the HOP manager to create choice nodes
while ( Abc_NtkHaigResetReprs( pMan ) )
{
pMan = Abc_NtkHaigReconstruct( pManTemp = pMan );
Hop_ManStop( pManTemp );
}
// traverse in the topological order and create new AIG
pNtkAig = Abc_NtkHaigRecreateAig( pNtk, pMan );
Hop_ManStop( pMan );
return pNtkAig;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END