diff options
| -rw-r--r-- | abclib.dsp | 4 | ||||
| -rw-r--r-- | src/base/abc/abc.h | 3 | ||||
| -rw-r--r-- | src/base/abci/abc.c | 4 | ||||
| -rw-r--r-- | src/base/abci/abcShare.c | 448 | ||||
| -rw-r--r-- | src/base/abci/module.make | 1 | ||||
| -rw-r--r-- | src/misc/vec/vecInt.h | 32 |
6 files changed, 492 insertions, 0 deletions
@@ -423,6 +423,10 @@ SOURCE=.\src\base\abci\abcSense.c # End Source File # Begin Source File +SOURCE=.\src\base\abci\abcShare.c +# End Source File +# Begin Source File + SOURCE=.\src\base\abci\abcSpeedup.c # End Source File # Begin Source File diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index dc3aba5e..46974edb 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -400,6 +400,9 @@ static inline Abc_Obj_t * Abc_ObjChild1Data( Abc_Obj_t * pObj ) { return Ab //static inline Hop_Obj_t * Abc_ObjChild0Equiv( Abc_Obj_t * pObj ) { return Hop_NotCond( Abc_ObjFanin0(pObj)->pEquiv, Abc_ObjFaninC0(pObj) ); } //static inline Hop_Obj_t * Abc_ObjChild1Equiv( Abc_Obj_t * pObj ) { return Hop_NotCond( Abc_ObjFanin1(pObj)->pEquiv, Abc_ObjFaninC1(pObj) ); } +static inline Abc_Obj_t * Abc_ObjFromLit( Abc_Ntk_t * p, int iLit ) { return Abc_ObjNotCond( Abc_NtkObj(p, Abc_Lit2Var(iLit)), Abc_LitIsCompl(iLit) ); } +static inline int Abc_ObjToLit( Abc_Obj_t * p ) { return Abc_Var2Lit( Abc_ObjId(Abc_ObjRegular(p)), Abc_ObjIsComplement(p) ); } + // checking the AIG node types static inline int Abc_AigNodeIsConst( Abc_Obj_t * pNode ) { assert(Abc_NtkIsStrash(Abc_ObjRegular(pNode)->pNtk)); return Abc_ObjRegular(pNode)->Type == ABC_OBJ_CONST1; } static inline int Abc_AigNodeIsAnd( Abc_Obj_t * pNode ) { assert(!Abc_ObjIsComplement(pNode)); assert(Abc_NtkIsStrash(pNode->pNtk)); return Abc_ObjFaninNum(pNode) == 2; } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index b042bdb3..55208cad 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -9009,6 +9009,7 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv ) if ( pNtk ) { +/* Aig_Man_t * pAig = Abc_NtkToDar( pNtk, 0, 1 ); if ( fNewAlgo ) Saig_IsoDetectFast( pAig ); @@ -9018,6 +9019,9 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv ) Aig_ManStopP( &pRes ); } Aig_ManStop( pAig ); +*/ + extern void Abc_NtkShareXor( Abc_Ntk_t * pNtk ); + Abc_NtkShareXor( pNtk ); } // Abc2_NtkTestGia( "", 1 ); diff --git a/src/base/abci/abcShare.c b/src/base/abci/abcShare.c new file mode 100644 index 00000000..0dee4214 --- /dev/null +++ b/src/base/abci/abcShare.c @@ -0,0 +1,448 @@ +/**CFile**************************************************************** + + FileName [abcShare.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Shared logic extraction.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: abcShare.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "src/base/abc/abc.h" + +ABC_NAMESPACE_IMPL_START + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define SHARE_NUM 2 + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +static inline word Abc_NtkSharePack( int Lev, int Id ) { return (((word)Lev) << 32) | Id; } +static inline int Abc_NtkShareUnpackLev( word Num ) { return (Num >> 32); } +static inline int Abc_NtkShareUnpackId( word Num ) { return Num & 0xFFFF; } + +/**Function************************************************************* + + Synopsis [Collects one multi-input XOR.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Wrd_t * Abc_NtkShareSuperXor( Abc_Obj_t * pObjInit, int * pfCompl ) +{ + int fCompl = Abc_ObjIsComplement(pObjInit); + Abc_Obj_t * pObj = Abc_ObjRegular(pObjInit); + Abc_Ntk_t * pNtk = Abc_ObjNtk(pObj); + Abc_Obj_t * pObjC, * pObj0, * pObj1, * pRoot; + Vec_Wrd_t * vSuper; + word Num, NumNext; + int i, k; + assert( Abc_NodeIsExorType(pObj) ); + // start iteration + vSuper = Vec_WrdAlloc( 10 ); + Vec_WrdPush( vSuper, Abc_NtkSharePack(Abc_ObjLevel(pObj), Abc_ObjId(pObj)) ); + while ( Vec_WrdSize(vSuper) > 0 ) + { + // make sure there are no duplicates + Num = Vec_WrdEntry( vSuper, 0 ); + Vec_WrdForEachEntryStart( vSuper, NumNext, i, 1 ) + { + assert( Num != NumNext ); + Num = NumNext; + } + // extract XOR gate decomposable on the topmost level + Vec_WrdForEachEntryReverse( vSuper, Num, i ) + { + pRoot = Abc_NtkObj( pNtk, Abc_NtkShareUnpackId(Num) ); + if ( Abc_NodeIsExorType(pRoot) ) + { + Vec_WrdRemove( vSuper, Num ); + break; + } + } + if ( i == -1 ) + break; + // extract + pObjC = Abc_NodeRecognizeMux( pRoot, &pObj1, &pObj0 ); + assert( pObj1 == Abc_ObjNot(pObj0) ); + fCompl ^= Abc_ObjIsComplement(pObjC); pObjC = Abc_ObjRegular(pObjC); + fCompl ^= Abc_ObjIsComplement(pObj0); pObj0 = Abc_ObjRegular(pObj0); + Vec_WrdPushOrder( vSuper, Abc_NtkSharePack(Abc_ObjLevel(pObjC), Abc_ObjId(pObjC)) ); + Vec_WrdPushOrder( vSuper, Abc_NtkSharePack(Abc_ObjLevel(pObj0), Abc_ObjId(pObj0)) ); + // remove duplicates + k = 0; + Vec_WrdForEachEntry( vSuper, Num, i ) + { + if ( i + 1 == Vec_WrdSize(vSuper) ) + { + Vec_WrdWriteEntry( vSuper, k++, Num ); + break; + } + NumNext = Vec_WrdEntry( vSuper, i+1 ); + assert( Num <= NumNext ); + if ( Num == NumNext ) + i++; + else + Vec_WrdWriteEntry( vSuper, k++, Num ); + } + Vec_WrdShrink( vSuper, k ); + } + *pfCompl = fCompl; + Vec_WrdForEachEntry( vSuper, Num, i ) + Vec_WrdWriteEntry( vSuper, i, Abc_NtkShareUnpackId(Num) ); + return vSuper; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkShareFindBest_( Vec_Ptr_t * vBuckets ) +{ + Vec_Ptr_t * vBucket; + int i; + Vec_PtrForEachEntryReverse( Vec_Ptr_t *, vBuckets, vBucket, i ) + { + if ( Vec_PtrSize(vBucket) == 0 ) + continue; + return (Vec_Int_t *)Vec_PtrPop( vBucket ); + } + return NULL; +} +Vec_Int_t * Abc_NtkShareFindBestMatch_( Vec_Ptr_t * vBuckets, Vec_Int_t * vInput2 ) +{ + Vec_Ptr_t * vBucket, * vBucketBest = NULL; + Vec_Int_t * vInput, * vInputBest = NULL; + int i, k, Cost, CostBest = 0; + Vec_PtrForEachEntry( Vec_Ptr_t *, vBuckets, vBucket, i ) + Vec_PtrForEachEntry( Vec_Int_t *, vBucket, vInput, k ) + { + vInput->pArray += SHARE_NUM; + vInput2->pArray += SHARE_NUM; + vInput->nSize -= SHARE_NUM; + vInput2->nSize -= SHARE_NUM; + + Cost = Vec_IntTwoCountCommon(vInput, vInput2); + + vInput->pArray -= SHARE_NUM; + vInput2->pArray -= SHARE_NUM; + vInput->nSize += SHARE_NUM; + vInput2->nSize += SHARE_NUM; + + if ( Cost < 2 ) + continue; + + if ( CostBest < Cost ) + { + CostBest = Cost; + vInputBest = vInput; + vBucketBest = vBucket; + } + } + if ( vInputBest ) + Vec_PtrRemove( vBucketBest, (Vec_Int_t *)vInputBest ); + printf( "%d ", CostBest ); + return vInputBest; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkShareFindBestMatch( Vec_Ptr_t * vBuckets, Vec_Int_t ** pvInput, Vec_Int_t ** pvInput2 ) +{ + int nPoolSize = 40; + Vec_Ptr_t * vPool = Vec_PtrAlloc( nPoolSize ); + Vec_Ptr_t * vBucket; + Vec_Int_t * vInput, * vInput2, * vInputBest = NULL, * vInputBest2 = NULL; + int i, k, Cost, CostBest = 0, Delay, DelayBest = 0; + + Vec_PtrForEachEntryReverse( Vec_Ptr_t *, vBuckets, vBucket, i ) + Vec_PtrForEachEntry( Vec_Int_t *, vBucket, vInput, k ) + { + Vec_PtrPush( vPool, vInput ); + if ( Vec_PtrSize(vPool) == nPoolSize ) + goto outside; + } +outside: + + Vec_PtrForEachEntryReverse( Vec_Int_t *, vPool, vInput, i ) + Vec_PtrForEachEntryReverse( Vec_Int_t *, vPool, vInput2, k ) + { + if ( i == k ) + continue; + + vInput->pArray += SHARE_NUM; + vInput2->pArray += SHARE_NUM; + vInput->nSize -= SHARE_NUM; + vInput2->nSize -= SHARE_NUM; + + Cost = Vec_IntTwoCountCommon(vInput, vInput2); + + vInput->pArray -= SHARE_NUM; + vInput2->pArray -= SHARE_NUM; + vInput->nSize += SHARE_NUM; + vInput2->nSize += SHARE_NUM; + + if ( Cost < 2 ) + continue; + + Delay = Abc_MaxInt( Vec_IntEntry(vInput, 1), Vec_IntEntry(vInput2, 1) ); + + if ( CostBest < Cost || (CostBest == Cost && (DelayBest > Delay)) ) + { + CostBest = Cost; + DelayBest = Delay; + vInputBest = vInput; + vInputBest2 = vInput2; + } + } + Vec_PtrFree( vPool ); + + *pvInput = vInputBest; + *pvInput2 = vInputBest2; + + if ( vInputBest == NULL ) + return; + + Vec_PtrRemove( (Vec_Ptr_t *)Vec_PtrEntry(vBuckets, Vec_IntSize(vInputBest)-SHARE_NUM), (Vec_Int_t *)vInputBest ); + Vec_PtrRemove( (Vec_Ptr_t *)Vec_PtrEntry(vBuckets, Vec_IntSize(vInputBest2)-SHARE_NUM), (Vec_Int_t *)vInputBest2 ); +} + +void Abc_NtkSharePrint( Abc_Ntk_t * pNtk, Vec_Ptr_t * vBuckets, int Counter ) +{ + Vec_Ptr_t * vBucket; + Vec_Int_t * vInput; + int i, k, j, ObjId; + char * pBuffer = ABC_ALLOC( char, Counter + 1 ); + int * pCounters = ABC_CALLOC( int, Counter + 1 ); + int nTotal = 0; + Vec_PtrForEachEntry( Vec_Ptr_t *, vBuckets, vBucket, i ) + Vec_PtrForEachEntry( Vec_Int_t *, vBucket, vInput, j ) + { + for ( k = 0; k < Counter; k++ ) + pBuffer[k] = '0'; + pBuffer[k] = 0; + + Vec_IntForEachEntryStart( vInput, ObjId, k, SHARE_NUM ) + { + assert( ObjId < Counter ); + pBuffer[ObjId] = '1'; + pCounters[ObjId]++; + } + + printf( "%4d%3d: %s\n", Vec_IntEntry(vInput, 0), Vec_IntEntry(vInput, 1), pBuffer ); + } + ABC_FREE( pBuffer ); + + for ( i = 0; i < Counter; i++ ) + if ( pCounters[i] > 0 ) + printf( "%d=%d ", i, pCounters[i] ); + + nTotal = 0; + for ( i = 0; i < Abc_NtkCoNum(pNtk); i++ ) + nTotal += pCounters[i] - 1; + printf( "Total = %d.\n", nTotal ); + printf( "Xors = %d.\n", Counter - Abc_NtkCoNum(pNtk) + nTotal ); + + ABC_FREE( pCounters ); +} + +void Abc_NtkShareOptimize( Abc_Ntk_t * pNtk, Vec_Ptr_t * vBuckets, int * pCounter ) +{ + Abc_Obj_t * pObj, * pObj0, * pObj1; + Vec_Int_t * vInput, * vInput2; + Vec_Int_t * vNew, * vOld1, * vOld2; + int i, iLit; + for ( i = 0; ; i++ ) + { + Abc_NtkShareFindBestMatch( vBuckets, &vInput, &vInput2 ); + if ( vInput == NULL ) + break; + + // create new node + pObj0 = Abc_ObjFromLit( pNtk, Vec_IntEntry(vInput, 0) ); + pObj1 = Abc_ObjFromLit( pNtk, Vec_IntEntry(vInput2, 0) ); + pObj = Abc_AigXor( (Abc_Aig_t *)pNtk->pManFunc, pObj0, pObj1 ); + iLit = Abc_ObjToLit( pObj ); + + // save new node + vOld1 = Vec_IntAlloc( 16 ); Vec_IntPush( vOld1, Vec_IntEntry(vInput, 0) ); Vec_IntPush( vOld1, Vec_IntEntry(vInput, 1) ); + vOld2 = Vec_IntAlloc( 16 ); Vec_IntPush( vOld2, Vec_IntEntry(vInput2, 0) ); Vec_IntPush( vOld2, Vec_IntEntry(vInput2, 1) ); + vNew = Vec_IntAlloc( 16 ); Vec_IntPush( vNew, iLit ); Vec_IntPush( vNew, Abc_ObjLevel(Abc_ObjRegular(pObj)) ); + + // compute new arrays + vInput->pArray += SHARE_NUM; + vInput2->pArray += SHARE_NUM; + vInput->nSize -= SHARE_NUM; + vInput2->nSize -= SHARE_NUM; + + Vec_IntTwoSplit( vInput, vInput2, vNew, vOld1, vOld2 ); + + vInput->pArray -= SHARE_NUM; + vInput2->pArray -= SHARE_NUM; + vInput->nSize += SHARE_NUM; + vInput2->nSize += SHARE_NUM; + + // add to the old ones + Vec_IntPush( vOld1, *pCounter ); + Vec_IntPush( vOld2, *pCounter ); + (*pCounter)++; + + Vec_PtrPush( (Vec_Ptr_t *)Vec_PtrEntry(vBuckets, Vec_IntSize(vOld1)-SHARE_NUM), vOld1 ); + Vec_PtrPush( (Vec_Ptr_t *)Vec_PtrEntry(vBuckets, Vec_IntSize(vOld2)-SHARE_NUM), vOld2 ); + Vec_PtrPush( (Vec_Ptr_t *)Vec_PtrEntry(vBuckets, Vec_IntSize(vNew)-SHARE_NUM), vNew ); + + Vec_IntFree( vInput ); + Vec_IntFree( vInput2 ); + } + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Extracts one multi-output XOR.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkShareXor( Abc_Ntk_t * pNtk ) +{ + Vec_Ptr_t * vBuckets, * vBucket; + Vec_Ptr_t * vInputs; + Vec_Int_t * vInput; + Vec_Wrd_t * vSuper; + Abc_Obj_t * pObj; + word Num; + int i, k, ObjId, fCompl, nOnesMax, Counter; + assert( Abc_NtkIsStrash(pNtk) ); + + vInputs = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); + Abc_NtkForEachCo( pNtk, pObj, i ) + { + if ( !Abc_NodeIsExorType(Abc_ObjFanin0(pObj)) ) + continue; + vSuper = Abc_NtkShareSuperXor( Abc_ObjChild0(pObj), &fCompl ); +//printf( "%d ", Vec_WrdSize(vSuper) ); + + pObj->fMarkA = fCompl; + Vec_WrdForEachEntry( vSuper, Num, k ) + { + ObjId = Abc_NtkShareUnpackId(Num); + vInput = (Vec_Int_t *)Vec_PtrEntry( vInputs, ObjId ); + if ( vInput == NULL ) + { + vInput = Vec_IntAlloc( 10 ); + Vec_IntPush( vInput, Abc_Var2Lit(ObjId, 0) ); + Vec_IntPush( vInput, Abc_ObjLevel(Abc_NtkObj(pNtk, ObjId)) ); + assert( SHARE_NUM == Vec_IntSize(vInput) ); + Vec_PtrWriteEntry( vInputs, ObjId, vInput ); + } +// Vec_IntPush( vInput, Abc_ObjFaninId0(pObj) ); +// Vec_IntPush( vInput, Abc_ObjId(pObj) ); + Vec_IntPush( vInput, i ); + } + Vec_WrdFree( vSuper ); + } +//printf( "\n" ); + + // find the largest number of 1s + nOnesMax = 0; + Vec_PtrForEachEntry( Vec_Int_t *, vInputs, vInput, i ) + if ( vInput ) + nOnesMax = Abc_MaxInt( nOnesMax, Vec_IntSize(vInput)-SHARE_NUM ); + + vBuckets = Vec_PtrAlloc( nOnesMax + 1 ); + for ( i = 0; i <= nOnesMax; i++ ) + Vec_PtrPush( vBuckets, Vec_PtrAlloc(10) ); + + Vec_PtrForEachEntry( Vec_Int_t *, vInputs, vInput, i ) + if ( vInput ) + Vec_PtrPush( (Vec_Ptr_t *)Vec_PtrEntry(vBuckets, Vec_IntSize(vInput)-SHARE_NUM), vInput ); + + // find the best match + Counter = Abc_NtkCoNum(pNtk); + Abc_NtkShareOptimize( pNtk, vBuckets, &Counter ); + + Abc_NtkSharePrint( pNtk, vBuckets, Counter ); + + // clean up + Vec_PtrForEachEntry( Vec_Ptr_t *, vBuckets, vBucket, i ) + printf( "%d ", Vec_PtrSize(vBucket) ); + printf( "\n" ); + + Vec_PtrForEachEntry( Vec_Ptr_t *, vBuckets, vBucket, i ) + Vec_VecFree( (Vec_Vec_t *)vBucket ); + Vec_PtrFree( vBuckets ); + +/* + // print + Vec_PtrForEachEntry( Vec_Int_t *, vInputs, vInput, i ) + { + if ( vInput == NULL ) + continue; + pObj = Abc_NtkObj(pNtk, i); + assert( Abc_ObjIsCi(pObj) ); + + Vec_IntForEachEntryStart( vInput, ObjId, k, SHARE_NUM ) + Abc_NtkObj( pNtk, ObjId )->fMarkA = 1; + + Abc_NtkForEachCo( pNtk, pObj, k ) + printf( "%d", pObj->fMarkA ); + printf( "\n" ); + + Vec_IntForEachEntryStart( vInput, ObjId, k, SHARE_NUM ) + Abc_NtkObj( pNtk, ObjId )->fMarkA = 0; + } + + Vec_PtrForEachEntry( Vec_Int_t *, vInputs, vInput, i ) + Vec_IntFreeP( &vInput ); +*/ + Vec_PtrFree( vInputs ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/base/abci/module.make b/src/base/abci/module.make index 1a240e91..80fe22e6 100644 --- a/src/base/abci/module.make +++ b/src/base/abci/module.make @@ -55,6 +55,7 @@ SRC += src/base/abci/abc.c \ src/base/abci/abcSat.c \ src/base/abci/abcScorr.c \ src/base/abci/abcSense.c \ + src/base/abci/abcShare.c \ src/base/abci/abcSpeedup.c \ src/base/abci/abcStrash.c \ src/base/abci/abcSweep.c \ diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h index 882326b2..4422fc85 100644 --- a/src/misc/vec/vecInt.h +++ b/src/misc/vec/vecInt.h @@ -1251,6 +1251,38 @@ static inline Vec_Int_t * Vec_IntTwoMerge( Vec_Int_t * vArr1, Vec_Int_t * vArr2 return vArr; } +/**Function************************************************************* + + Synopsis [Returns the result of merging the two vectors.] + + Description [Assumes that the vectors are sorted in the increasing order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_IntTwoSplit( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Vec_Int_t * vArr, Vec_Int_t * vArr1n, Vec_Int_t * vArr2n ) +{ + int * pBeg1 = vArr1->pArray; + int * pBeg2 = vArr2->pArray; + int * pEnd1 = vArr1->pArray + vArr1->nSize; + int * pEnd2 = vArr2->pArray + vArr2->nSize; + while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 ) + { + if ( *pBeg1 == *pBeg2 ) + Vec_IntPush( vArr, *pBeg1++ ), pBeg2++; + else if ( *pBeg1 < *pBeg2 ) + Vec_IntPush( vArr1n, *pBeg1++ ); + else + Vec_IntPush( vArr2n, *pBeg2++ ); + } + while ( pBeg1 < pEnd1 ) + Vec_IntPush( vArr1n, *pBeg1++ ); + while ( pBeg2 < pEnd2 ) + Vec_IntPush( vArr2n, *pBeg2++ ); +} + /**Function************************************************************* |