/**CFile****************************************************************
FileName [giaBalance.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Scalable AIG package.]
Synopsis [AIG balancing.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: giaBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "gia.h"
#include "misc/vec/vecHash.h"
#include "misc/vec/vecQue.h"
#include "opt/dau/dau.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
// operation manager
typedef struct Dam_Man_t_ Dam_Man_t;
struct Dam_Man_t_
{
Gia_Man_t * pGia; // user's AIG
Vec_Int_t * vNod2Set; // node ID into fanin set
Vec_Int_t * vDiv2Nod; // div ID into root node set
Vec_Int_t * vSetStore; // fanin set storage
Vec_Int_t * vNodStore; // root node set storage
Vec_Flt_t * vCounts; // occur counts
Vec_Int_t * vNodLevR; // node reverse level
Vec_Int_t * vDivLevR; // divisor reverse level
Vec_Int_t * vVisit; // visited MUXes
Vec_Que_t * vQue; // pairs by their weight
Hash_IntMan_t * vHash; // pair hash table
abctime clkStart; // starting the clock
int nLevelMax; // maximum level
int nDivs; // extracted divisor count
int nAnds; // total AND node count
int nGain; // total gain in AND nodes
int nGainX; // gain from XOR nodes
};
static inline int Dam_ObjHand( Dam_Man_t * p, int i ) { return i < Vec_IntSize(p->vNod2Set) ? Vec_IntEntry(p->vNod2Set, i) : 0; }
static inline int * Dam_ObjSet( Dam_Man_t * p, int i ) { int h = Dam_ObjHand(p, i); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vSetStore, h); }
static inline int Dam_DivHand( Dam_Man_t * p, int d ) { return d < Vec_IntSize(p->vDiv2Nod) ? Vec_IntEntry(p->vDiv2Nod, d) : 0; }
static inline int * Dam_DivSet( Dam_Man_t * p, int d ) { int h = Dam_DivHand(p, d); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vNodStore, h); }
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Simplify multi-input AND/XOR.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManSimplifyXor( Vec_Int_t * vSuper )
{
int i, k = 0, Prev = -1, This, fCompl = 0;
Vec_IntForEachEntry( vSuper, This, i )
{
if ( This == 0 )
continue;
if ( This == 1 )
fCompl ^= 1;
else if ( Prev != This )
Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
else
Prev = -1, k--;
}
Vec_IntShrink( vSuper, k );
if ( Vec_IntSize( vSuper ) == 0 )
Vec_IntPush( vSuper, fCompl );
else if ( fCompl )
Vec_IntWriteEntry( vSuper, 0, Abc_LitNot(Vec_IntEntry(vSuper, 0)) );
}
void Gia_ManSimplifyAnd( Vec_Int_t * vSuper )
{
int i, k = 0, Prev = -1, This;
Vec_IntForEachEntry( vSuper, This, i )
{
if ( This == 0 )
{ Vec_IntFill(vSuper, 1, 0); return; }
if ( This == 1 )
continue;
if ( Prev == -1 || Abc_Lit2Var(Prev) != Abc_Lit2Var(This) )
Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
else if ( Prev != This )
{ Vec_IntFill(vSuper, 1, 0); return; }
}
Vec_IntShrink( vSuper, k );
if ( Vec_IntSize( vSuper ) == 0 )
Vec_IntPush( vSuper, 1 );
}
/**Function*************************************************************
Synopsis [Collect multi-input AND/XOR.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManSuperCollectXor_rec( Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
{
assert( !Gia_IsComplement(pObj) );
if ( !Gia_ObjIsXor(pObj) ||
(fStrict && Gia_ObjRefNum(p, pObj) > 1) ||
Gia_ObjRefNum(p, pObj) > 2 ||
(Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
Vec_IntSize(p->vSuper) > 10000 )
{
Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
return;
}
assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj), fStrict );
Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj), fStrict );
}
void Gia_ManSuperCollectAnd_rec( Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
{
if ( Gia_IsComplement(pObj) ||
!Gia_ObjIsAndReal(p, pObj) ||
(fStrict && Gia_ObjRefNum(p, pObj) > 1) ||
Gia_ObjRefNum(p, pObj) > 2 ||
(Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
Vec_IntSize(p->vSuper) > 10000 )
{
Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
return;
}
Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj), fStrict );
Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj), fStrict );
}
void Gia_ManSuperCollect( Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
{
// int nSize;
if ( p->vSuper == NULL )
p->vSuper = Vec_IntAlloc( 1000 );
else
Vec_IntClear( p->vSuper );
if ( Gia_ObjIsXor(pObj) )
{
assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj), fStrict );
Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj), fStrict );
// nSize = Vec_IntSize(vSuper);
Vec_IntSort( p->vSuper, 0 );
Gia_ManSimplifyXor( p->vSuper );
// if ( nSize != Vec_IntSize(vSuper) )
// printf( "X %d->%d ", nSize, Vec_IntSize(vSuper) );
}
else if ( Gia_ObjIsAndReal(p, pObj) )
{
Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj), fStrict );
Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj), fStrict );
// nSize = Vec_IntSize(vSuper);
Vec_IntSort( p->vSuper, 0 );
Gia_ManSimplifyAnd( p->vSuper );
// if ( nSize != Vec_IntSize(vSuper) )
// printf( "A %d->%d ", nSize, Vec_IntSize(vSuper) );
}
else assert( 0 );
// if ( nSize > 10 )
// printf( "%d ", nSize );
assert( Vec_IntSize(p->vSuper) > 0 );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Gia_ManFindSharedNode( Gia_Man_t * pNew, Vec_Int_t * vSuper, int iLit0 )
{
int i, iLit1 = Vec_IntEntryLast(vSuper);
// iterate through the nodes whose level is equal to that of the last one
int iLit1Level = Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1));
for ( i = Vec_IntSize(vSuper)-1; i >= 0; i-- )
{
int iLit2 = Vec_IntEntry(vSuper, i);
if ( iLit1Level != Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
break;
if ( Abc_Lit2Var(iLit0) != Abc_Lit2Var(iLit2) && !Gia_ManHashLookupInt(pNew, iLit0, iLit2) ) // new node
continue;
// swap iLit2 and iLit1
if ( iLit2 != iLit1 )
{
Vec_IntWriteEntry( vSuper, i, iLit1 );
Vec_IntWriteEntry( vSuper, Vec_IntSize(vSuper)-1, iLit2 );
}
break;
}
return Vec_IntPop(vSuper);
}
void Gia_ManPrepareLastTwo( Gia_Man_t * pNew, Vec_Int_t * vSuper )
{
int i, k, Stop, Lit1, Lit2, Level1, Level2, * pArray;
int nSize = Vec_IntSize(vSuper);
if ( nSize == 2 )
return;
assert( nSize > 2 );
Level1 = Gia_ObjLevelId( pNew, Abc_Lit2Var(Vec_IntEntry(vSuper, nSize-2)) );
// find the first one with Level1
for ( Stop = nSize-3; Stop >= 0; Stop-- )
{
Level2 = Gia_ObjLevelId( pNew, Abc_Lit2Var(Vec_IntEntry(vSuper, Stop)) );
if ( Level1 != Level2 )
break;
}
if ( Stop == nSize-3 )
return;
// avoid worst-case quadratic behavior by looking at the last 8 nodes
Stop = Abc_MaxInt( Stop, nSize - 9 );
for ( i = nSize - 1; i > Stop; i-- )
for ( k = i - 1; k > Stop; k-- )
{
Lit1 = Vec_IntEntry(vSuper, i);
Lit2 = Vec_IntEntry(vSuper, k);
if ( Abc_Lit2Var(Lit1) != Abc_Lit2Var(Lit2) && !Gia_ManHashLookupInt(pNew, Lit1, Lit2) ) // new node
continue;
// move Lit1 to be last and Lit2 to be the one before
pArray = Vec_IntArray( vSuper );
if ( i != nSize-1 )
ABC_SWAP( int, pArray[i], pArray[nSize-1] );
if ( k != nSize-2 )
ABC_SWAP( int, pArray[k], pArray[nSize-2] );
}
}
void Gia_ManCreateGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper )
{
int iLit0 = Vec_IntPop(vSuper);
int iLit1 = Vec_IntPop(vSuper);
// int iLit1 = Gia_ManFindSharedNode(pNew, vSuper, iLit0);
int iLit, i;
if ( !Gia_ObjIsXor(pObj) )
iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 );
else if ( pNew->pMuxes )
iLit = Gia_ManHashXorReal( pNew, iLit0, iLit1 );
else
iLit = Gia_ManHashXor( pNew, iLit0, iLit1 );
Vec_IntPush( vSuper, iLit );
Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(iLit)) );
// shift to the corrent location
for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
{
int iLit1 = Vec_IntEntry(vSuper, i);
int iLit2 = Vec_IntEntry(vSuper, i-1);
if ( Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1)) <= Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
break;
Vec_IntWriteEntry( vSuper, i, iLit2 );
Vec_IntWriteEntry( vSuper, i-1, iLit1 );
}
}
int Gia_ManBalanceGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper, int * pLits, int nLits )
{
assert( !Gia_ObjIsBuf(pObj) );
Vec_IntClear( vSuper );
if ( nLits == 1 )
Vec_IntPush( vSuper, pLits[0] );
else if ( nLits == 2 )
{
Vec_IntPush( vSuper, pLits[0] );
Vec_IntPush( vSuper, pLits[1] );
Gia_ManCreateGate( pNew, pObj, vSuper );
}
else if ( nLits > 2 )
{
// collect levels
int i, * pArray, * pPerm; //int iLit;
for ( i = 0; i < nLits; i++ )
Vec_IntPush( vSuper, Gia_ObjLevelId(pNew, Abc_Lit2Var(pLits[i])) );
// sort by level
Vec_IntGrow( vSuper, 4 * nLits );
pArray = Vec_IntArray( vSuper );
pPerm = pArray + nLits;
Abc_QuickSortCostData( pArray, nLits, 1, (word *)(pArray + 2 * nLits), pPerm );
// collect in the increasing order of level
for ( i = 0; i < nLits; i++ )
Vec_IntWriteEntry( vSuper, i, pLits[pPerm[i]] );
Vec_IntShrink( vSuper, nLits );
/*
Vec_IntForEachEntry( vSuper, iLit, i )
printf( "%d ", Gia_ObjLevel(pNew, Gia_ManObj( pNew, Abc_Lit2Var(iLit) )) );
printf( "\n" );
*/
// perform incremental extraction
while ( Vec_IntSize(vSuper) > 1 )
{
if ( !Gia_ObjIsXor(pObj) )
Gia_ManPrepareLastTwo( pNew, vSuper );
Gia_ManCreateGate( pNew, pObj, vSuper );
}
}
// consider trivial case
assert( Vec_IntSize(vSuper) == 1 );
return Vec_IntEntry(vSuper, 0);
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManBalance_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
{
int i, iLit, iBeg, iEnd;
if ( ~pObj->Value )
return;
assert( Gia_ObjIsAnd(pObj) );
assert( !Gia_ObjIsBuf(pObj) );
// handle MUX
if ( Gia_ObjIsMux(p, pObj) )
{
Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj), fStrict );
Gia_ManBalance_rec( pNew, p, Gia_ObjFanin1(pObj), fStrict );
Gia_ManBalance_rec( pNew, p, Gia_ObjFanin2(p, pObj), fStrict );
pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
return;
}
// find supergate
Gia_ManSuperCollect( p, pObj, fStrict );
// save entries
if ( p->vStore == NULL )
p->vStore = Vec_IntAlloc( 1000 );
iBeg = Vec_IntSize( p->vStore );
Vec_IntAppend( p->vStore, p->vSuper );
iEnd = Vec_IntSize( p->vStore );
// call recursively
Vec_IntForEachEntryStartStop( p->vStore, iLit, i, iBeg, iEnd )
{
Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(iLit) );
Gia_ManBalance_rec( pNew, p, pTemp, fStrict );
Vec_IntWriteEntry( p->vStore, i, Abc_LitNotCond(pTemp->Value, Abc_LitIsCompl(iLit)) );
}
assert( Vec_IntSize(p->vStore) == iEnd );
// consider general case
pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, Vec_IntEntryP(p->vStore, iBeg), iEnd-iBeg );
Vec_IntShrink( p->vStore, iBeg );
}
Gia_Man_t * Gia_ManBalanceInt( Gia_Man_t * p, int fStrict )
{
Gia_Man_t * pNew, * pTemp;
Gia_Obj_t * pObj;
int i;
Gia_ManFillValue( p );
Gia_ManCreateRefs( p );
// start the new manager
pNew = Gia_ManStart( Gia_ManObjNum(p) );
pNew->pName = Abc_UtilStrsav( p->pName );
pNew->pSpec = Abc_UtilStrsav( p->pSpec );
pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
// create constant and inputs
Gia_ManConst0(p)->Value = 0;
Gia_ManForEachCi( p, pObj, i )
pObj->Value = Gia_ManAppendCi( pNew );
// create internal nodes
Gia_ManHashStart( pNew );
Gia_ManForEachBuf( p, pObj, i )
{
Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj), fStrict );
pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
}
Gia_ManForEachCo( p, pObj, i )
{
Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj), fStrict );
pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
}
assert( !fStrict || Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
Gia_ManHashStop( pNew );
Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
// perform cleanup
pNew = Gia_ManCleanup( pTemp = pNew );
Gia_ManStop( pTemp );
return pNew;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Gia_Man_t * Gia_ManBalance( Gia_Man_t * p, int fSimpleAnd, int fStrict, int fVerbose )
{
Gia_Man_t * pNew, * pNew1, * pNew2;
if ( fVerbose ) Gia_ManPrintStats( p, NULL );
pNew = fSimpleAnd ? Gia_ManDup( p ) : Gia_ManDupMuxes( p, 2 );
if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
pNew1 = Gia_ManBalanceInt( pNew, fStrict );
if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
Gia_ManStop( pNew );
pNew2 = Gia_ManDupNoMuxes( pNew1 );
if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
Gia_ManStop( pNew1 );
return pNew2;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dam_Man_t * Dam_ManAlloc( Gia_Man_t * pGia )
{
Dam_Man_t * p;
p = ABC_CALLOC( Dam_Man_t, 1 );
p->clkStart = Abc_Clock();
p->vVisit = Vec_IntAlloc( 1000 );
p->pGia = pGia;
return p;
}
void Dam_ManFree( Dam_Man_t * p )
{
Vec_IntFreeP( &p->vVisit );
Vec_IntFreeP( &p->vDivLevR );
Vec_IntFreeP( &p->vNodLevR );
Vec_IntFreeP( &p->vNod2Set );
Vec_IntFreeP( &p->vDiv2Nod );
Vec_IntFreeP( &p->vSetStore );
Vec_IntFreeP( &p->vNodStore );
Vec_FltFreeP( &p->vCounts );
Vec_QueFreeP( &p->vQue );
Hash_IntManStop( p->vHash );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Collect initial multi-input gates.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Dam_ManCollectSets_rec( Dam_Man_t * p, int Id )
{
Gia_Obj_t * pObj;
int i, iBeg, iEnd, iLit;
if ( Dam_ObjHand(p, Id) || Id == 0 )
return;
pObj = Gia_ManObj(p->pGia, Id);
if ( Gia_ObjIsCi(pObj) )
return;
if ( Gia_ObjIsBuf(pObj) )
{
Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) );
return;
}
if ( Gia_ObjIsMux(p->pGia, pObj) )
{
if ( pObj->fMark0 )
return;
pObj->fMark0 = 1;
Vec_IntPush( p->vVisit, Id );
Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) );
Dam_ManCollectSets_rec( p, Gia_ObjFaninId1(pObj, Id) );
Dam_ManCollectSets_rec( p, Gia_ObjFaninId2(p->pGia, Id) );
p->nAnds += 3;
return;
}
Gia_ManSuperCollect( p->pGia, pObj, 0 );
Vec_IntWriteEntry( p->vNod2Set, Id, Vec_IntSize(p->vSetStore) );
Vec_IntPush( p->vSetStore, Vec_IntSize(p->pGia->vSuper) );
p->nAnds += (1 + 2 * Gia_ObjIsXor(pObj)) * (Vec_IntSize(p->pGia->vSuper) - 1);
// save entries
iBeg = Vec_IntSize( p->vSetStore );
Vec_IntAppend( p->vSetStore, p->pGia->vSuper );
iEnd = Vec_IntSize( p->vSetStore );
// call recursively
Vec_IntForEachEntryStartStop( p->vSetStore, iLit, i, iBeg, iEnd )
Dam_ManCollectSets_rec( p, Abc_Lit2Var(iLit) );
}
void Dam_ManCollectSets( Dam_Man_t * p )
{
Gia_Obj_t * pObj;
int i;
Gia_ManCreateRefs( p->pGia );
p->vNod2Set = Vec_IntStart( Gia_ManObjNum(p->pGia) );
p->vSetStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) );
Vec_IntPush( p->vSetStore, -1 );
Vec_IntClear( p->vVisit );
Gia_ManForEachCo( p->pGia, pObj, i )
Dam_ManCollectSets_rec( p, Gia_ObjFaninId0p(p->pGia, pObj) );
ABC_FREE( p->pGia->pRefs );
Gia_ManForEachObjVec( p->vVisit, p->pGia, pObj, i )
pObj->fMark0 = 0;
}
/**Function*************************************************************
Synopsis [Create divisors.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Dam_ManDivSlack( Dam_Man_t * p, int iLit0, int iLit1, int LevR )
{
int Lev0 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit0)));
int Lev1 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit1)));
int Slack = p->nLevelMax - LevR - Abc_MaxInt(Lev0, Lev1) - 1 - (int)(iLit0 > iLit1);
return Abc_MinInt( Slack, 100 );
}
void Dam_ManCreateMultiRefs( Dam_Man_t * p, Vec_Int_t ** pvRefsAnd, Vec_Int_t ** pvRefsXor )
{
Vec_Int_t * vRefsAnd, * vRefsXor;
Gia_Obj_t * pObj;
int i, k, * pSet;
vRefsAnd = Vec_IntStart( 2 * Gia_ManObjNum(p->pGia) );
vRefsXor = Vec_IntStart( Gia_ManObjNum(p->pGia) );
Gia_ManForEachAnd( p->pGia, pObj, i )
{
if ( !Dam_ObjHand(p, i) )
continue;
pSet = Dam_ObjSet(p, i);
if ( Gia_ObjIsXor(pObj) )
for ( k = 1; k <= pSet[0]; k++ )
{
assert( !Abc_LitIsCompl(pSet[k]) );
Vec_IntAddToEntry( vRefsXor, Abc_Lit2Var(pSet[k]), 1 );
}
else if ( Gia_ObjIsAndReal(p->pGia, pObj) )
for ( k = 1; k <= pSet[0]; k++ )
Vec_IntAddToEntry( vRefsAnd, pSet[k], 1 );
else assert( 0 );
}
*pvRefsAnd = vRefsAnd;
*pvRefsXor = vRefsXor;
}
void Dam_ManCreatePairs( Dam_Man_t * p, int fVerbose )
{
Gia_Obj_t * pObj;
Hash_IntMan_t * vHash;
Vec_Int_t * vRefsAnd, * vRefsXor, * vSuper, * vDivs, * vRemap, * vLevRMax;
int i, j, k, Num, FanK, FanJ, nRefs, iNode, iDiv, * pSet;
int nPairsAll = 0, nPairsTried = 0, nPairsUsed = 0, nPairsXor = 0;
int nDivsAll = 0, nDivsUsed = 0, nDivsXor = 0;
Dam_ManCollectSets( p );
vSuper = p->pGia->vSuper;
vDivs = Vec_IntAlloc( Gia_ManObjNum(p->pGia) );
vHash = Hash_IntManStart( Gia_ManObjNum(p->pGia)/2 );
vLevRMax = Vec_IntStart( 1000 );
Dam_ManCreateMultiRefs( p, &vRefsAnd, &vRefsXor );
Gia_ManForEachAnd( p->pGia, pObj, i )
{
if ( !Dam_ObjHand(p, i) )
continue;
pSet = Dam_ObjSet(p, i);
nPairsAll += pSet[0] * (pSet[0] - 1) / 2;
Vec_IntClear(vSuper);
if ( Gia_ObjIsXor(pObj) )
{
for ( k = 1; k <= pSet[0]; k++ )
if ( Vec_IntEntry(vRefsXor, Abc_Lit2Var(pSet[k])) > 1 )
Vec_IntPush( vSuper, pSet[k] );
}
else if ( Gia_ObjIsAndReal(p->pGia, pObj) )
{
for ( k = 1; k <= pSet[0]; k++ )
if ( Vec_IntEntry(vRefsAnd, pSet[k]) > 1 )
Vec_IntPush( vSuper, pSet[k] );
}
else assert( 0 );
if ( Vec_IntSize(vSuper) < 2 )
continue;
// enumerate pairs
nPairsTried += Vec_IntSize(vSuper) * (Vec_IntSize(vSuper) - 1) / 2;
Vec_IntPush( vDivs, -i ); // remember node
Vec_IntForEachEntry( vSuper, FanK, k )
Vec_IntForEachEntryStart( vSuper, FanJ, j, k+1 )
{
if ( (FanK > FanJ) ^ Gia_ObjIsXor(pObj) )
Num = Hash_Int2ManInsert( vHash, FanJ, FanK, 0 );
else
Num = Hash_Int2ManInsert( vHash, FanK, FanJ, 0 );
if ( Hash_Int2ObjInc( vHash, Num ) == 1 )
{
nDivsUsed++;
nDivsXor += Gia_ObjIsXor(pObj);
}
Vec_IntPush( vDivs, Num ); // remember devisor
// update reverse level
if ( Num >= Vec_IntSize(vLevRMax) )
Vec_IntFillExtra( vLevRMax, 3 * Vec_IntSize(vLevRMax) / 2, 0 );
Vec_IntUpdateEntry( vLevRMax, Num, Vec_IntEntry(p->vNodLevR, i) );
}
}
Vec_IntFree( vRefsAnd );
Vec_IntFree( vRefsXor );
// Hash_IntManProfile( vHash );
// remove entries that appear only once
p->vHash = Hash_IntManStart( 3 * nDivsUsed /2 );
p->vCounts = Vec_FltAlloc( 2 * nDivsUsed ); Vec_FltPush( p->vCounts, ABC_INFINITY );
p->vQue = Vec_QueAlloc( Vec_FltCap(p->vCounts) );
Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) );
// mapping div to node
p->vDiv2Nod = Vec_IntAlloc( 2 * nDivsUsed ); Vec_IntPush( p->vDiv2Nod, ABC_INFINITY );
p->vNodStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); Vec_IntPush( p->vNodStore, -1 );
nDivsAll = Hash_IntManEntryNum(vHash);
vRemap = Vec_IntStartFull( nDivsAll+1 );
for ( i = 1; i <= nDivsAll; i++ )
{
nRefs = Hash_IntObjData2(vHash, i);
if ( nRefs < 2 )
continue;
nPairsUsed += nRefs;
if ( Hash_IntObjData0(vHash, i) > Hash_IntObjData1(vHash, i) )
nPairsXor += nRefs;
Num = Hash_Int2ManInsert( p->vHash, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), 0 );
assert( Num == Hash_IntManEntryNum(p->vHash) );
assert( Num == Vec_FltSize(p->vCounts) );
Vec_FltPush( p->vCounts, nRefs + 0.005*Dam_ManDivSlack(p, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), Vec_IntEntry(vLevRMax, i)) );
Vec_QuePush( p->vQue, Num );
// remember divisors
assert( Num == Vec_IntSize(p->vDiv2Nod) );
Vec_IntPush( p->vDiv2Nod, Vec_IntSize(p->vNodStore) );
Vec_IntPush( p->vNodStore, 0 );
Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 );
// remember entry
Vec_IntWriteEntry( vRemap, i, Num );
}
assert( Vec_FltSize(p->vCounts) == Hash_IntManEntryNum(p->vHash)+1 );
assert( Vec_IntSize(p->vDiv2Nod) == nDivsUsed+1 );
Hash_IntManStop( vHash );
Vec_IntFree( vLevRMax );
// fill in the divisors
iNode = -1;
Vec_IntForEachEntry( vDivs, iDiv, i )
{
if ( iDiv < 0 )
{
iNode = -iDiv;
continue;
}
Num = Vec_IntEntry( vRemap, iDiv );
if ( Num == -1 )
continue;
pSet = Dam_DivSet( p, Num );
pSet[++pSet[0]] = iNode;
}
Vec_IntFree( vRemap );
Vec_IntFree( vDivs );
// create storage for reverse level of divisor during update
p->vDivLevR = Vec_IntStart( 2 * nDivsUsed );
// make sure divisors are added correctly
// for ( i = 1; i <= nDivsUsed; i++ )
// assert( Dam_DivSet(p, i)[0] == Vec_FltEntry(p->vCounts, i)+1 );
if ( !fVerbose )
return;
// print stats
printf( "Pairs:" );
printf( " Total =%9d (%6.2f %%)", nPairsAll, 100.0 * nPairsAll / Abc_MaxInt(nPairsAll, 1) );
printf( " Tried =%9d (%6.2f %%)", nPairsTried, 100.0 * nPairsTried / Abc_MaxInt(nPairsAll, 1) );
printf( " Used =%9d (%6.2f %%)", nPairsUsed, 100.0 * nPairsUsed / Abc_MaxInt(nPairsAll, 1) );
printf( " Xor =%9d (%6.2f %%)", nPairsXor, 100.0 * nPairsXor / Abc_MaxInt(nPairsAll, 1) );
printf( "\n" );
printf( "Div: " );
printf( " Total =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
printf( " Tried =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) );
printf( " Xor =%9d (%6.2f %%)", nDivsXor, 100.0 * nDivsXor / Abc_MaxInt(nDivsAll, 1) );
printf( "\n" );
}
/**Function*************************************************************
Synopsis [Derives new AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Dam_ManMultiAig_rec( Dam_Man_t * pMan, Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj )
{
int i, * pSet;
if ( ~pObj->Value )
return;
assert( Gia_ObjIsAnd(pObj) );
pSet = Dam_ObjSet(pMan, Gia_ObjId(p, pObj));
if ( pSet == NULL )
{
Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin1(pObj) );
if ( Gia_ObjIsMux(p, pObj) )
{
Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin2(p, pObj) );
pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
}
else if ( Gia_ObjIsXor(pObj) )
pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
else
pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
return;
}
assert( Gia_ObjIsXor(pObj) || Gia_ObjIsAndReal(p, pObj) );
// call recursively
for ( i = 1; i <= pSet[0]; i++ )
{
Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(pSet[i]) );
Dam_ManMultiAig_rec( pMan, pNew, p, pTemp );
pSet[i] = Abc_LitNotCond( pTemp->Value, Abc_LitIsCompl(pSet[i]) );
}
// create balanced gate
pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, pSet + 1, pSet[0] );
}
Gia_Man_t * Dam_ManMultiAig( Dam_Man_t * pMan )
{
Gia_Man_t * p = pMan->pGia;
Gia_Man_t * pNew, * pTemp;
Gia_Obj_t * pObj;
int i;
// start the new manager
pNew = Gia_ManStart( 2*Gia_ManObjNum(p) );
pNew->pName = Abc_UtilStrsav( p->pName );
pNew->pSpec = Abc_UtilStrsav( p->pSpec );
pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
// create constant and inputs
Gia_ManFillValue( p );
Gia_ManConst0(p)->Value = 0;
Gia_ManForEachCi( p, pObj, i )
{
pObj->Value = Gia_ManAppendCi( pNew );
Vec_IntWriteEntry( pNew->vLevels, Abc_Lit2Var(pObj->Value), Gia_ObjLevel(p, pObj) );
}
// create internal nodes
Gia_ManHashStart( pNew );
Gia_ManForEachBuf( p, pObj, i )
{
Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
}
Gia_ManForEachCo( p, pObj, i )
{
Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
}
// assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
Gia_ManHashStop( pNew );
Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
// perform cleanup
pNew = Gia_ManCleanup( pTemp = pNew );
Gia_ManStop( pTemp );
return pNew;
}
/**Function*************************************************************
Synopsis [Updates the data-structure after extracting one divisor.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Dam_PrintDiv( Dam_Man_t * p, int iDiv )
{
if ( iDiv == 0 )
printf( "Final statistics after extracting %6d divisors: ", p->nDivs );
else
{
char Buffer[100];
int iData0 = Hash_IntObjData0(p->vHash, iDiv);
int iData1 = Hash_IntObjData1(p->vHash, iDiv);
printf( "Div%5d : ", p->nDivs+1 );
printf( "D%-8d = ", iDiv );
sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData0)? '!':' ', Abc_Lit2Var(iData0) );
printf( "%8s ", Buffer );
printf( "%c ", (iData0 < iData1) ? '*' : '+' );
sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData1)? '!':' ', Abc_Lit2Var(iData1) );
printf( "%8s ", Buffer );
printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, iDiv) );
}
printf( "Divs =%8d ", Hash_IntManEntryNum(p->vHash) );
printf( "Ands =%8d ", p->nAnds - p->nGain );
Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
}
void Dam_PrintQue( Dam_Man_t * p )
{
int i;
printf( "Divisor queue: \n" );
for ( i = 1; i <= Hash_IntManEntryNum(p->vHash); i++ )
{
int iLit0 = Hash_IntObjData0(p->vHash, i);
int iLit1 = Hash_IntObjData1(p->vHash, i);
printf( "Div %7d : ", i );
printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, i) );
printf( "F = %c%c ", Abc_LitIsCompl(iLit0) ? '!': ' ', 'a' + Abc_Lit2Var(iLit0)-1 );
printf( "%c ", (Hash_IntObjData0(p->vHash, i) < Hash_IntObjData1(p->vHash, i)) ? '*':'+' );
printf( "%c%c ", Abc_LitIsCompl(iLit1) ? '!': ' ', 'a' + Abc_Lit2Var(iLit1)-1 );
printf( "\n" );
}
}
int Dam_ManUpdateNode( Dam_Man_t * p, int iObj, int iLit0, int iLit1, int iLitNew, Vec_Int_t * vDivs )
{
int * pSet = Dam_ObjSet( p, iObj );
int i, k, c, Num, iLit, iLit2, fPres;
// check if literal can be found
for ( i = 1; i <= pSet[0]; i++ )
if ( pSet[i] == iLit0 )
break;
if ( i > pSet[0] )
return 0;
// check if literal can be found
for ( i = 1; i <= pSet[0]; i++ )
if ( pSet[i] == iLit1 )
break;
if ( i > pSet[0] )
return 0;
// compact literals
Vec_IntPush( vDivs, -iObj );
for ( k = i = 1; i <= pSet[0]; i++ )
{
if ( iLit0 == pSet[i] || iLit1 == pSet[i] )
continue;
pSet[k++] = iLit = pSet[i];
// reduce weights of the divisors
fPres = 0;
for ( c = 0; c < 2; c++ )
{
iLit2 = c ? iLit1 : iLit0;
if ( (iLit > iLit2) ^ (iLit0 > iLit1) )
Num = *Hash_Int2ManLookup( p->vHash, iLit2, iLit );
else
Num = *Hash_Int2ManLookup( p->vHash, iLit, iLit2 );
if ( Num > 0 )
{
Vec_FltAddToEntry( p->vCounts, Num, -1 );
if ( Vec_QueIsMember(p->vQue, Num) )
{
Vec_QueUpdate( p->vQue, Num );
fPres |= (1 << c);
}
}
}
if ( fPres != 3 )
continue;
if ( (iLit > iLitNew) ^ (iLit0 > iLit1) )
Num = Hash_Int2ManInsert( p->vHash, iLitNew, iLit, 0 );
else
Num = Hash_Int2ManInsert( p->vHash, iLit, iLitNew, 0 );
Hash_Int2ObjInc( p->vHash, Num );
Vec_IntPush( vDivs, Num );
// update reverse level
if ( Num >= Vec_IntSize(p->vDivLevR) )
Vec_IntFillExtra( p->vDivLevR, 3 * Vec_IntSize(p->vDivLevR) / 2, 0 );
Vec_IntUpdateEntry( p->vDivLevR, Num, Vec_IntEntry(p->vNodLevR, iObj) );
}
pSet[k] = iLitNew;
pSet[0] = k;
return 1;
}
void Dam_ManUpdate( Dam_Man_t * p, int iDiv )
{
Vec_Int_t * vDivs = p->pGia->vSuper;
int iLit0 = Hash_IntObjData0(p->vHash, iDiv);
int iLit1 = Hash_IntObjData1(p->vHash, iDiv);
int i, iLitNew, * pSet, * pNods = Dam_DivSet( p, iDiv );
int nPresent = 0, nPairsStart, nPairsStop, pPairsNew, nRefs;
int fThisIsXor = (iLit0 > iLit1), iDivTemp, iNode;
// Dam_PrintQue( p );
if ( fThisIsXor )
iLitNew = Gia_ManAppendXorReal( p->pGia, iLit0, iLit1 );
else
iLitNew = Gia_ManAppendAnd( p->pGia, iLit0, iLit1 );
Gia_ObjSetGateLevel( p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew)) );
// printf( "%d ", Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew))) );
// replace entries
assert( pNods[0] >= 2 );
nPairsStart = Hash_IntManEntryNum(p->vHash) + 1;
Vec_IntClear( vDivs );
for ( i = 1; i <= pNods[0]; i++ )
nPresent += Dam_ManUpdateNode( p, pNods[i], iLit0, iLit1, iLitNew, vDivs );
nPairsStop = Hash_IntManEntryNum(p->vHash) + 1;
// extend arrayvs
pPairsNew = 0;
Vec_FltFillExtra( p->vCounts, nPairsStop, 0 );
Vec_IntFillExtra( p->vDiv2Nod, nPairsStop, -1 );
for ( i = nPairsStart; i < nPairsStop; i++ )
{
nRefs = Hash_IntObjData2(p->vHash, i);
if ( nRefs < 2 )
continue;
Vec_FltWriteEntry( p->vCounts, i, nRefs + 0.001*Dam_ManDivSlack(p, Hash_IntObjData0(p->vHash, i), Hash_IntObjData1(p->vHash, i), Vec_IntEntry(p->vDivLevR, i)) );
Vec_QuePush( p->vQue, i );
// remember divisors
Vec_IntWriteEntry( p->vDiv2Nod, i, Vec_IntSize(p->vNodStore) );
Vec_IntPush( p->vNodStore, 0 );
Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 );
pPairsNew++;
}
// printf( "Added %d new pairs\n", pPairsNew );
// fill in the divisors
iNode = -1;
Vec_IntForEachEntry( vDivs, iDivTemp, i )
{
if ( iDivTemp < 0 )
{
iNode = -iDivTemp;
continue;
}
if ( Vec_IntEntry(p->vDiv2Nod, iDivTemp) == -1 )
continue;
pSet = Dam_DivSet( p, iDivTemp );
pSet[++pSet[0]] = iNode;
}
// make sure divisors are added correctly
for ( i = nPairsStart; i < nPairsStop; i++ )
if ( Vec_IntEntry(p->vDiv2Nod, i) > 0 )
assert( Dam_DivSet(p, i)[0] == Hash_IntObjData2(p->vHash, i) );
// update costs
Vec_FltWriteEntry( p->vCounts, iDiv, 0 );
p->nGain += (1 + 2 * fThisIsXor) * (nPresent - 1);
p->nGainX += 3 * fThisIsXor * (nPresent - 1);
p->nDivs++;
}
/**Function*************************************************************
Synopsis [Perform extraction for multi-input AND/XOR.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Gia_Man_t * Dam_ManAreaBalanceInt( Gia_Man_t * pGia, Vec_Int_t * vCiLevels, int nNewNodesMax, int fVerbose, int fVeryVerbose )
{
Gia_Man_t * pNew;
Dam_Man_t * p;
int i, iDiv;
p = Dam_ManAlloc( pGia );
p->nLevelMax = Gia_ManSetLevels( p->pGia, vCiLevels );
p->vNodLevR = Gia_ManReverseLevel( p->pGia );
Vec_IntFillExtra( p->pGia->vLevels, 3*Gia_ManObjNum(p->pGia)/2, 0 );
Dam_ManCreatePairs( p, fVerbose );
for ( i = 0; i < nNewNodesMax && Vec_QueTopPriority(p->vQue) >= 2; i++ )
{
iDiv = Vec_QuePop(p->vQue);
if ( fVeryVerbose )
Dam_PrintDiv( p, iDiv );
Dam_ManUpdate( p, iDiv );
}
if ( fVeryVerbose )
Dam_PrintDiv( p, 0 );
pNew = Dam_ManMultiAig( p );
if ( fVerbose )
{
int nDivsAll = Hash_IntManEntryNum(p->vHash);
int nDivsUsed = p->nDivs;
printf( "Div: " );
printf( " Total =%9d (%6.2f %%) ", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) );
printf( " Gain =%6d (%6.2f %%)", p->nGain, 100.0 * p->nGain / Abc_MaxInt(p->nAnds, 1) );
printf( " GainX = %d ", p->nGainX );
Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
}
Dam_ManFree( p );
return pNew;
}
Gia_Man_t * Gia_ManAreaBalance( Gia_Man_t * p, int fSimpleAnd, int nNewNodesMax, int fVerbose, int fVeryVerbose )
{
Gia_Man_t * pNew0, * pNew, * pNew1, * pNew2;
Vec_Int_t * vCiLevels;
// determine CI levels
if ( p->pManTime && p->vLevels == NULL )
Gia_ManLevelWithBoxes( p );
vCiLevels = Gia_ManGetCiLevels( p );
// get the starting manager
pNew0 = Gia_ManHasMapping(p) ? (Gia_Man_t *)Dsm_ManDeriveGia(p, 0) : p;
if ( fVerbose ) Gia_ManPrintStats( pNew0, NULL );
// derive internal manager
pNew = fSimpleAnd ? Gia_ManDup( pNew0 ) : Gia_ManDupMuxes( pNew0, 2 );
if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
if ( pNew0 != p ) Gia_ManStop( pNew0 );
// perform the operation
pNew1 = Dam_ManAreaBalanceInt( pNew, vCiLevels, nNewNodesMax, fVerbose, fVeryVerbose );
if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
Gia_ManStop( pNew );
Vec_IntFreeP( &vCiLevels );
// derive the final result
pNew2 = Gia_ManDupNoMuxes( pNew1 );
if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
Gia_ManStop( pNew1 );
// normalize if needed
if ( !Gia_ManIsNormalized(pNew2) )
{
pNew2 = Gia_ManDupNormalize( pNew1 = pNew2, 0 );
Gia_ManStop( pNew1 );
}
Gia_ManTransferTiming( pNew2, p );
return pNew2;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END