/**CFile****************************************************************
FileName [gia.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Scalable AIG package.]
Synopsis []
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "gia.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static inline int Gia_ObjDom( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Vec_IntEntry(p->vDoms, Gia_ObjId(p, pObj)); }
static inline void Gia_ObjSetDom( Gia_Man_t * p, Gia_Obj_t * pObj, int d ) { Vec_IntWriteEntry(p->vDoms, Gia_ObjId(p, pObj), d); }
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Computes one-node dominators.]
Description [For each node, computes the closest one-node dominator,
which can be the node itself if the node has no other dominators.]
SideEffects []
SeeAlso []
***********************************************************************/
static inline void Gia_ManAddDom( Gia_Man_t * p, Gia_Obj_t * pObj, int iDom0 )
{
int iDom1, iDomNext;
if ( Gia_ObjDom(p, pObj) == -1 )
{
Gia_ObjSetDom( p, pObj, iDom0 );
return;
}
iDom1 = Gia_ObjDom( p, pObj );
while ( 1 )
{
if ( iDom0 > iDom1 )
{
iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom1) );
if ( iDomNext == iDom1 )
break;
iDom1 = iDomNext;
continue;
}
if ( iDom1 > iDom0 )
{
iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom0) );
if ( iDomNext == iDom0 )
break;
iDom0 = iDomNext;
continue;
}
assert( iDom0 == iDom1 );
Gia_ObjSetDom( p, pObj, iDom0 );
return;
}
Gia_ObjSetDom( p, pObj, Gia_ObjId(p, pObj) );
}
static inline void Gia_ManComputeDoms( Gia_Man_t * p )
{
Gia_Obj_t * pObj;
int i;
if ( p->vDoms == NULL )
p->vDoms = Vec_IntAlloc( 0 );
Vec_IntFill( p->vDoms, Gia_ManObjNum(p), -1 );
Gia_ManForEachObjReverse( p, pObj, i )
{
if ( i == 0 || Gia_ObjIsCi(pObj) )
continue;
if ( Gia_ObjIsCo(pObj) )
{
Gia_ObjSetDom( p, pObj, i );
Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
continue;
}
assert( Gia_ObjIsAnd(pObj) );
Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
Gia_ManAddDom( p, Gia_ObjFanin1(pObj), i );
}
}
/**Function*************************************************************
Synopsis [Returns the number of internal nodes in the MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Gia_NodeDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
{
Gia_Obj_t * pFanin;
int Counter = 0;
if ( Gia_ObjIsCi(pNode) )
return 0;
assert( Gia_ObjIsAnd(pNode) );
pFanin = Gia_ObjFanin0(pNode);
assert( Gia_ObjRefNum(p, pFanin) > 0 );
if ( Gia_ObjRefDec(p, pFanin) == 0 )
Counter += Gia_NodeDeref_rec( p, pFanin );
pFanin = Gia_ObjFanin1(pNode);
assert( Gia_ObjRefNum(p, pFanin) > 0 );
if ( Gia_ObjRefDec(p, pFanin) == 0 )
Counter += Gia_NodeDeref_rec( p, pFanin );
return Counter + 1;
}
static inline int Gia_NodeRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
{
Gia_Obj_t * pFanin;
int Counter = 0;
if ( Gia_ObjIsCi(pNode) )
return 0;
assert( Gia_ObjIsAnd(pNode) );
pFanin = Gia_ObjFanin0(pNode);
if ( Gia_ObjRefInc(p, pFanin) == 0 )
Counter += Gia_NodeRef_rec( p, pFanin );
pFanin = Gia_ObjFanin1(pNode);
if ( Gia_ObjRefInc(p, pFanin) == 0 )
Counter += Gia_NodeRef_rec( p, pFanin );
return Counter + 1;
}
static inline void Gia_NodeCollect_rec( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Int_t * vSupp, Vec_Int_t * vSuppRefs )
{
if ( Gia_ObjIsTravIdCurrent(p, pNode) )
return;
Gia_ObjSetTravIdCurrent(p, pNode);
if ( Gia_ObjRefNum(p, pNode) || Gia_ObjIsCi(pNode) )
{
Vec_IntPush( vSupp, Gia_ObjId(p, pNode) );
Vec_IntPush( vSuppRefs, Gia_ObjRefNum(p, pNode) );
return;
}
assert( Gia_ObjIsAnd(pNode) );
Gia_NodeCollect_rec( p, Gia_ObjFanin0(pNode), vSupp, vSuppRefs );
Gia_NodeCollect_rec( p, Gia_ObjFanin1(pNode), vSupp, vSuppRefs );
}
static inline int Gia_NodeMffcSizeSupp( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Int_t * vSupp, Vec_Int_t * vSuppRefs )
{
int ConeSize1, ConeSize2, i, iObj;
assert( !Gia_IsComplement(pNode) );
assert( Gia_ObjIsAnd(pNode) );
Vec_IntClear( vSupp );
Vec_IntClear( vSuppRefs );
Gia_ManIncrementTravId( p );
ConeSize1 = Gia_NodeDeref_rec( p, pNode );
Gia_NodeCollect_rec( p, Gia_ObjFanin0(pNode), vSupp, vSuppRefs );
Gia_NodeCollect_rec( p, Gia_ObjFanin1(pNode), vSupp, vSuppRefs );
ConeSize2 = Gia_NodeRef_rec( p, pNode );
assert( ConeSize1 == ConeSize2 );
assert( ConeSize1 >= 0 );
// record supp refs
Vec_IntForEachEntry( vSupp, iObj, i )
Vec_IntAddToEntry( vSuppRefs, i, -Gia_ObjRefNumId(p, iObj) );
return ConeSize1;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Gia_ManDomDerive_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pNode )
{
if ( Gia_ObjIsTravIdCurrent(p, pNode) )
return pNode->Value;
Gia_ObjSetTravIdCurrent(p, pNode);
assert( Gia_ObjIsAnd(pNode) );
Gia_ManDomDerive_rec( pNew, p, Gia_ObjFanin0(pNode) );
Gia_ManDomDerive_rec( pNew, p, Gia_ObjFanin1(pNode) );
return pNode->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pNode), Gia_ObjFanin1Copy(pNode) );
}
Gia_Man_t * Gia_ManDomDerive( Gia_Man_t * p, Gia_Obj_t * pRoot, Vec_Int_t * vSupp, int nVars )
{
Gia_Man_t * pNew, * pTemp;
int nMints = 1 << nVars;
int i, m, iResLit;
assert( nVars >= 0 && nVars <= 5 );
pNew = Gia_ManStart( Gia_ManObjNum(p) );
pNew->pName = Abc_UtilStrsav( p->pName );
pNew->pSpec = Abc_UtilStrsav( p->pSpec );
Gia_ManConst0(p)->Value = 0;
Gia_ManHashAlloc( pNew );
for ( i = 0; i < Vec_IntSize(vSupp); i++ )
Gia_ManAppendCi(pNew);
for ( m = 0; m < nMints; m++ )
{
Gia_Obj_t * pObj;
Gia_ManIncrementTravId( p );
Gia_ManForEachObjVec( vSupp, p, pObj, i )
{
if ( i < nVars )
pObj->Value = (m >> i) & 1;
else
pObj->Value = Gia_ObjToLit(pNew, Gia_ManCi(pNew, i));
Gia_ObjSetTravIdCurrent( p, pObj );
}
iResLit = Gia_ManDomDerive_rec( pNew, p, pRoot );
Gia_ManAppendCo( pNew, iResLit );
}
Gia_ManHashStop( pNew );
pNew = Gia_ManCleanup( pTemp = pNew );
Gia_ManStop( pTemp );
return pNew;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManComputeDomsTry( Gia_Man_t * p )
{
extern void Gia_ManCollapseTestTest( Gia_Man_t * p );
Vec_Int_t * vSupp, * vSuppRefs;
Gia_Man_t * pNew;
Gia_Obj_t * pObj;
int i, nSize, Entry, k;
abctime clk = Abc_Clock();
ABC_FREE( p->pRefs );
Gia_ManLevelNum( p );
Gia_ManCreateRefs( p );
Gia_ManComputeDoms( p );
Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
vSupp = Vec_IntAlloc( 1000 );
vSuppRefs = Vec_IntAlloc( 1000 );
Gia_ManForEachObj( p, pObj, i )
{
if ( !Gia_ObjIsAnd(pObj) && !Gia_ObjIsCo(pObj) )
continue;
if ( Gia_ObjDom(p, pObj) != i )
continue;
if ( Gia_ObjIsCo(pObj) )
pObj = Gia_ObjFanin0(pObj);
if ( !Gia_ObjIsAnd(pObj) )
continue;
nSize = Gia_NodeMffcSizeSupp( p, pObj, vSupp, vSuppRefs );
if ( nSize < 10 )//|| nSize > 100 )
continue;
// sort by cost
Vec_IntSelectSortCost2( Vec_IntArray(vSupp), Vec_IntSize(vSupp), Vec_IntArray(vSuppRefs) );
printf( "Obj %6d : ", i );
printf( "Cone = %4d ", nSize );
printf( "Supp = %4d ", Vec_IntSize(vSupp) );
// Vec_IntForEachEntry( vSuppRefs, Entry, k )
// printf( "%d(%d) ", -Entry, Gia_ObjLevelId(p, Vec_IntEntry(vSupp, k)) );
printf( "\n" );
// selected k
for ( k = 0; k < Vec_IntSize(vSupp); k++ )
if ( Vec_IntEntry(vSuppRefs, k) == 1 )
break;
k = Abc_MinInt( k, 3 );
k = 0;
// dump
pNew = Gia_ManDomDerive( p, pObj, vSupp, k );
Gia_DumpAiger( pNew, "mffc", i, 6 );
Gia_ManCollapseTestTest( pNew );
Gia_ManStop( pNew );
}
Vec_IntFree( vSuppRefs );
Vec_IntFree( vSupp );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END