From 9c502b70f392e2a797f5105c916d558f6108748b Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 5 Apr 2014 22:51:01 -0700 Subject: Preparing new implementation of SOP/DSD balancing in 'if' mapper. --- src/aig/gia/giaIf.c | 61 ++++- src/base/abci/abcIf.c | 57 +++++ src/bool/kit/kit.h | 1 + src/bool/kit/kitIsop.c | 25 ++ src/map/if/if.h | 15 +- src/map/if/ifDelay.c | 616 +++++++++++++++++++++++++++++++++++++++++++++++++ src/map/if/ifDsd.c | 265 ++++++++++++++++++++- src/map/if/ifMan.c | 1 + src/map/if/ifMap.c | 2 + src/map/if/ifTime.c | 44 +++- src/map/if/module.make | 1 + 11 files changed, 1070 insertions(+), 18 deletions(-) create mode 100644 src/map/if/ifDelay.c (limited to 'src') diff --git a/src/aig/gia/giaIf.c b/src/aig/gia/giaIf.c index e52bdf29..ac17c745 100644 --- a/src/aig/gia/giaIf.c +++ b/src/aig/gia/giaIf.c @@ -670,6 +670,56 @@ int Gia_ManNodeIfSopToGia( Gia_Man_t * pNew, If_Man_t * p, If_Cut_t * pCut, Vec_ return iResult; } +/**Function************************************************************* + + Synopsis [Rebuilds GIA from mini AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManBuildFromMini( Gia_Man_t * pNew, Vec_Int_t * vLeaves, Vec_Int_t * vAig, int fHash ) +{ + assert( Vec_IntSize(vAig) > 0 ); + assert( Vec_IntEntryLast(vAig) < 2 ); + if ( Vec_IntSize(vAig) == 1 ) // const + return Vec_IntEntry(vAig, 0); + if ( Vec_IntSize(vAig) == 2 ) // variable + { + assert( Vec_IntEntry(vAig, 0) == 0 ); + assert( Vec_IntSize(vLeaves) == 1 ); + return Abc_LitNotCond( Vec_IntEntry(vLeaves, 0), Vec_IntEntry(vAig, 1) ); + } + else + { + int nLeaves = Vec_IntSize(vLeaves); + int i, iVar0, iVar1, iLit0, iLit1, iLit = 0; + assert( Vec_IntSize(vAig) & 1 ); + Vec_IntForEachEntryDouble( vAig, iLit0, iLit1, i ) + { + iVar0 = Abc_Lit2Var( iLit0 ); + iVar1 = Abc_Lit2Var( iLit1 ); + iLit0 = Abc_LitNotCond( iVar0 < nLeaves ? Vec_IntEntry(vLeaves, iVar0) : Vec_IntEntry(vAig, iVar0 - nLeaves), Abc_LitIsCompl(iLit0) ); + iLit1 = Abc_LitNotCond( iVar1 < nLeaves ? Vec_IntEntry(vLeaves, iVar1) : Vec_IntEntry(vAig, iVar1 - nLeaves), Abc_LitIsCompl(iLit1) ); + if ( fHash ) + iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 ); + else if ( iLit0 == iLit1 ) + iLit = iLit0; + else + iLit = Gia_ManAppendAnd( pNew, iLit0, iLit1 ); + assert( (i & 1) == 0 ); + Vec_IntWriteEntry( vAig, Abc_Lit2Var(i), iLit ); // overwriting entries + } + assert( i == Vec_IntSize(vAig) - 1 ); + iLit = Abc_LitNotCond( iLit, Vec_IntEntry(vAig, i) ); + Vec_IntClear( vAig ); // useless + return iLit; + } +} + /**Function************************************************************* Synopsis [Converts IF into GIA manager.] @@ -688,7 +738,7 @@ Gia_Man_t * Gia_ManFromIfAig( If_Man_t * pIfMan ) If_Obj_t * pIfObj, * pIfLeaf; If_Cut_t * pCutBest; Vec_Int_t * vLeaves; - Vec_Int_t * vCover; + Vec_Int_t * vAig; int i, k; assert( pIfMan->pPars->pLutStruct == NULL ); assert( pIfMan->pPars->fDelayOpt || pIfMan->pPars->fDsdBalance || pIfMan->pPars->fUserRecLib ); @@ -696,7 +746,7 @@ Gia_Man_t * Gia_ManFromIfAig( If_Man_t * pIfMan ) pNew = Gia_ManStart( If_ManObjNum(pIfMan) ); Gia_ManHashAlloc( pNew ); // iterate through nodes used in the mapping - vCover = Vec_IntAlloc( 1 << 16 ); + vAig = Vec_IntAlloc( 1 << 16 ); vLeaves = Vec_IntAlloc( 16 ); If_ManCleanCutData( pIfMan ); If_ManForEachObj( pIfMan, pIfObj, i ) @@ -714,7 +764,10 @@ Gia_Man_t * Gia_ManFromIfAig( If_Man_t * pIfMan ) if ( pIfMan->pPars->fDelayOpt ) pIfObj->iCopy = Gia_ManNodeIfSopToGia( pNew, pIfMan, pCutBest, vLeaves, fHash ); else if ( pIfMan->pPars->fDsdBalance ) - pIfObj->iCopy = If_DsdCutBalance( pNew, pIfMan, pCutBest, vLeaves, fHash ); + { + If_DsdCutBalanceAig( pIfMan, pCutBest, vAig ); + pIfObj->iCopy = Gia_ManBuildFromMini( pNew, vLeaves, vAig, fHash ); + } else if ( pIfMan->pPars->fUserRecLib ) pIfObj->iCopy = Abc_RecToGia3( pNew, pIfMan, pCutBest, vLeaves, fHash ); else assert( 0 ); @@ -727,7 +780,7 @@ Gia_Man_t * Gia_ManFromIfAig( If_Man_t * pIfMan ) pIfObj->iCopy = 1; else assert( 0 ); } - Vec_IntFree( vCover ); + Vec_IntFree( vAig ); Vec_IntFree( vLeaves ); Gia_ManHashStop( pNew ); return pNew; diff --git a/src/base/abci/abcIf.c b/src/base/abci/abcIf.c index dcfe2020..cec487f5 100644 --- a/src/base/abci/abcIf.c +++ b/src/base/abci/abcIf.c @@ -449,6 +449,63 @@ Hop_Obj_t * Abc_NodeFromDsdBalance( Hop_Man_t * pMan, If_Man_t * p, If_Cut_t * p return pResult; } +/**Function************************************************************* + + Synopsis [Rebuilds GIA from mini AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Hop_Obj_t * Abc_NodeBuildFromMiniInt( Hop_Man_t * pMan, Vec_Int_t * vAig, int nLeaves ) +{ + assert( Vec_IntSize(vAig) > 0 ); + assert( Vec_IntEntryLast(vAig) < 2 ); + if ( Vec_IntSize(vAig) == 1 ) // const + { + assert( nLeaves == 0 ); + return Hop_NotCond( Hop_ManConst1(pMan), Vec_IntEntry(vAig, 0) ); + } + if ( Vec_IntSize(vAig) == 2 ) // variable + { + assert( Vec_IntEntry(vAig, 0) == 0 ); + assert( nLeaves == 1 ); + return Hop_NotCond( Hop_IthVar(pMan, 0), Vec_IntEntry(vAig, 1) ); + } + else + { + int i, iVar0, iVar1, iLit0, iLit1; + Hop_Obj_t * piLit0, * piLit1, * piLit = NULL; + assert( Vec_IntSize(vAig) & 1 ); + Vec_IntForEachEntryDouble( vAig, iLit0, iLit1, i ) + { + iVar0 = Abc_Lit2Var( iLit0 ); + iVar1 = Abc_Lit2Var( iLit1 ); + piLit0 = Hop_NotCond( iVar0 < nLeaves ? Hop_IthVar(pMan, iVar0) : (Hop_Obj_t *)Vec_PtrEntry((Vec_Ptr_t *)vAig, iVar0 - nLeaves), Abc_LitIsCompl(iLit0) ); + piLit1 = Hop_NotCond( iVar1 < nLeaves ? Hop_IthVar(pMan, iVar1) : (Hop_Obj_t *)Vec_PtrEntry((Vec_Ptr_t *)vAig, iVar1 - nLeaves), Abc_LitIsCompl(iLit1) ); + piLit = Hop_And( pMan, piLit0, piLit1 ); + assert( (i & 1) == 0 ); + Vec_PtrWriteEntry( (Vec_Ptr_t *)vAig, Abc_Lit2Var(i), piLit ); // overwriting entries + } + assert( i == Vec_IntSize(vAig) - 1 ); + piLit = Hop_NotCond( piLit, Vec_IntEntry(vAig, i) ); + Vec_IntClear( vAig ); // useless + return piLit; + } +} +Hop_Obj_t * Abc_NodeBuildFromMini( Hop_Man_t * pMan, If_Man_t * p, If_Cut_t * pCut ) +{ + Hop_Obj_t * pResult; + if ( p->vArray == NULL ) + p->vArray = Vec_IntAlloc(100); + If_CutDelaySopArray3( p, pCut, p->vArray ); + pResult = Abc_NodeBuildFromMiniInt( pMan, p->vArray, If_CutLeaveNum(pCut) ); + return pResult; +} + /**Function************************************************************* Synopsis [Derive one node after FPGA mapping.] diff --git a/src/bool/kit/kit.h b/src/bool/kit/kit.h index cb1c1eb0..614f2fd5 100644 --- a/src/bool/kit/kit.h +++ b/src/bool/kit/kit.h @@ -568,6 +568,7 @@ extern int Kit_GraphLeafDepth_rec( Kit_Graph_t * pGraph, Kit_Node_t //extern Hop_Obj_t * Kit_CoverToHop( Hop_Man_t * pMan, Vec_Int_t * vCover, int nVars, Vec_Int_t * vMemory ); /*=== kitIsop.c ==========================================================*/ extern int Kit_TruthIsop( unsigned * puTruth, int nVars, Vec_Int_t * vMemory, int fTryBoth ); +extern void Kit_TruthIsopPrint( unsigned * puTruth, int nVars, Vec_Int_t * vMemory, int fTryBoth ); /*=== kitPla.c ==========================================================*/ extern int Kit_PlaIsConst0( char * pSop ); extern int Kit_PlaIsConst1( char * pSop ); diff --git a/src/bool/kit/kitIsop.c b/src/bool/kit/kitIsop.c index fc017c0e..68d526ed 100644 --- a/src/bool/kit/kitIsop.c +++ b/src/bool/kit/kitIsop.c @@ -101,6 +101,31 @@ int Kit_TruthIsop( unsigned * puTruth, int nVars, Vec_Int_t * vMemory, int fTryB Vec_IntShrink( vMemory, pcRes->nCubes ); return RetValue; } +void Kit_TruthIsopPrint( unsigned * puTruth, int nVars, Vec_Int_t * vCover, int fTryBoth ) +{ + int i, k, Entry, Literal; + int RetValue = Kit_TruthIsop( puTruth, nVars, vCover, fTryBoth ); + if ( Vec_IntSize(vCover) == 0 || (Vec_IntSize(vCover) == 1 && Vec_IntEntry(vCover, 0) == 0) ) + { + printf( "Constant %d\n", Vec_IntSize(vCover) ); + return; + } + Vec_IntForEachEntry( vCover, Entry, i ) + { + for ( k = 0; k < nVars; k++ ) + { + Literal = 3 & (Entry >> (k << 1)); + if ( Literal == 1 ) // neg literal + printf( "0" ); + else if ( Literal == 2 ) // pos literal + printf( "1" ); + else if ( Literal == 0 ) + printf( "-" ); + else assert( 0 ); + } + printf( " %d\n", !RetValue ); + } +} /**Function************************************************************* diff --git a/src/map/if/if.h b/src/map/if/if.h index 1ca83e78..2184b08b 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -207,6 +207,7 @@ struct If_Man_t_ int fReqTimeWarn; // warning about exceeding required times was printed // SOP balancing Vec_Int_t * vCover; // used to compute ISOP + Vec_Int_t * vArray; // intermediate storage Vec_Wrd_t * vAnds; // intermediate storage Vec_Wrd_t * vOrGate; // intermediate storage Vec_Wrd_t * vAndGate; // intermediate storage @@ -415,13 +416,16 @@ static inline void If_CutSetData( If_Cut_t * pCut, void * pData ) { * static inline int If_CutDataInt( If_Cut_t * pCut ) { return *(int *)pCut; } static inline void If_CutSetDataInt( If_Cut_t * pCut, int Data ) { *(int *)pCut = Data; } +static inline int If_CutTruthLit( If_Cut_t * pCut ) { assert( pCut->iCutFunc >= 0 ); return pCut->iCutFunc; } +static inline int If_CutTruthIsCompl( If_Cut_t * pCut ) { assert( pCut->iCutFunc >= 0 ); return Abc_LitIsCompl(pCut->iCutFunc); } static inline word * If_CutTruthWR( If_Man_t * p, If_Cut_t * pCut ) { return p->vTtMem ? Vec_MemReadEntry(p->vTtMem[pCut->nLeaves], Abc_Lit2Var(pCut->iCutFunc)) : NULL; } -static inline unsigned * If_CutTruthR( If_Man_t * p, If_Cut_t * pCut ) { return (unsigned *)If_CutTruthWR(p, pCut); } -static inline int If_CutTruthIsCompl( If_Cut_t * pCut ) { assert( pCut->iCutFunc >= 0 ); return Abc_LitIsCompl(pCut->iCutFunc); } +static inline unsigned * If_CutTruthUR( If_Man_t * p, If_Cut_t * pCut) { return (unsigned *)If_CutTruthWR(p, pCut); } static inline word * If_CutTruthW( If_Man_t * p, If_Cut_t * pCut ) { if ( p->vTtMem == NULL ) return NULL; assert( pCut->iCutFunc >= 0 ); Abc_TtCopy( p->puTempW, If_CutTruthWR(p, pCut), p->nTruth6Words[pCut->nLeaves], If_CutTruthIsCompl(pCut) ); return p->puTempW; } static inline unsigned * If_CutTruth( If_Man_t * p, If_Cut_t * pCut ) { return (unsigned *)If_CutTruthW(p, pCut); } +static inline int If_CutDsdLit( If_Cut_t * pCut ) { assert( pCut->iCutDsd >= 0 ); return pCut->iCutDsd; } +static inline If_Obj_t * If_CutLeaf( If_Man_t * p, If_Cut_t * pCut, int i ) { assert(i >= 0 && i < (int)pCut->nLeaves); return If_ManObj(p, pCut->pLeaves[i]); } -static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { return pCut->fUser? (float)pCut->Cost : (p->pPars->pLutLib? p->pPars->pLutLib->pLutAreas[pCut->nLeaves] : (float)1.0); } +static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { return pCut->fUser? (float)pCut->Cost : (p->pPars->pLutLib? p->pPars->pLutLib->pLutAreas[pCut->nLeaves] : (float)1.0); } static inline float If_CutLutDelay( If_LibLut_t * p, int Size, int iPin ) { return p ? (p->fVarPinDelays ? p->pLutDelays[Size][iPin] : p->pLutDelays[Size][0]) : 1.0; } static inline word If_AndToWrd( If_And_t m ) { union { If_And_t x; word y; } v; v.x = m; return v.y; } @@ -531,6 +535,9 @@ extern int If_CluCheckExt( void * p, word * pTruth, int nVars, int n char * pLut0, char * pLut1, word * pFunc0, word * pFunc1 ); extern int If_CluCheckExt3( void * p, word * pTruth, int nVars, int nLutLeaf, int nLutLeaf2, int nLutRoot, char * pLut0, char * pLut1, char * pLut2, word * pFunc0, word * pFunc1, word * pFunc2 ); +/*=== ifDelay.c =============================================================*/ +extern int If_CutDelaySopArray3( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ); +extern int If_CutPinDelaysSopArray3( If_Man_t * p, If_Cut_t * pCut, char * pPerm ); /*=== ifDsd.c =============================================================*/ extern If_DsdMan_t * If_DsdManAlloc( int nVars, int nLutSize ); extern void If_DsdManPrint( If_DsdMan_t * p, char * pFileName, int Number, int Support, int fOccurs, int fTtDump, int fVerbose ); @@ -548,7 +555,7 @@ extern int If_DsdManSuppSize( If_DsdMan_t * p, int iDsd ); extern int If_DsdManCheckDec( If_DsdMan_t * p, int iDsd ); extern unsigned If_DsdManCheckXY( If_DsdMan_t * p, int iDsd, int LutSize, int fDerive, int fHighEffort, int fVerbose ); extern int If_DsdCutBalanceCost( If_Man_t * pIfMan, If_Cut_t * pCut ); -extern int If_DsdCutBalance( void * pGia, If_Man_t * pIfMan, If_Cut_t * pCut, Vec_Int_t * vLeaves, int fHash ); +extern int If_DsdCutBalanceAig( If_Man_t * pIfMan, If_Cut_t * pCut, Vec_Int_t * vAig ); /*=== ifLib.c =============================================================*/ extern If_LibLut_t * If_LibLutRead( char * FileName ); extern If_LibLut_t * If_LibLutDup( If_LibLut_t * p ); diff --git a/src/map/if/ifDelay.c b/src/map/if/ifDelay.c new file mode 100644 index 00000000..d5a31850 --- /dev/null +++ b/src/map/if/ifDelay.c @@ -0,0 +1,616 @@ +/**CFile**************************************************************** + + FileName [ifDelay.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapping based on priority cuts.] + + Synopsis [Delay balancing for cut functions.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - November 21, 2006.] + + Revision [$Id: ifDelay.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "if.h" +#include "bool/kit/kit.h" + +ABC_NAMESPACE_IMPL_START + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Naive implementation of log-counter.] + + Description [Incrementally computes [log2(SUMi(2^di)).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_LogCounter64Eval( word Count ) +{ + int n = ((Count & (Count - 1)) > 0) ? -1 : 0; + assert( Count > 0 ); + if ( (Count & ABC_CONST(0xFFFFFFFF00000000)) == 0 ) { n += 32; Count <<= 32; } + if ( (Count & ABC_CONST(0xFFFF000000000000)) == 0 ) { n += 16; Count <<= 16; } + if ( (Count & ABC_CONST(0xFF00000000000000)) == 0 ) { n += 8; Count <<= 8; } + if ( (Count & ABC_CONST(0xF000000000000000)) == 0 ) { n += 4; Count <<= 4; } + if ( (Count & ABC_CONST(0xC000000000000000)) == 0 ) { n += 2; Count <<= 2; } + if ( (Count & ABC_CONST(0x8000000000000000)) == 0 ) { n++; } + return 63 - n; +} +static word If_LogCounter64Add( word Count, int Num ) +{ + assert( Num < 48 ); + return Count + (((word)1) << Num); +} + +/**Function************************************************************* + + Synopsis [Implementation of log-counter.] + + Description [Incrementally computes [log2(SUMi(2^di)). + Supposed to work correctly up to 16 entries.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int If_LogCounter32Eval( unsigned Count, int Start ) +{ + int n = (Abc_LitIsCompl(Start) || (Count & (Count - 1)) > 0) ? -1 : 0; + assert( Count > 0 ); + if ( (Count & 0xFFFF0000) == 0 ) { n += 16; Count <<= 16; } + if ( (Count & 0xFF000000) == 0 ) { n += 8; Count <<= 8; } + if ( (Count & 0xF0000000) == 0 ) { n += 4; Count <<= 4; } + if ( (Count & 0xC0000000) == 0 ) { n += 2; Count <<= 2; } + if ( (Count & 0x80000000) == 0 ) { n++; } + return Abc_Lit2Var(Start) + 31 - n; +} +static unsigned If_LogCounter32Add( unsigned Count, int * pStart, int Num ) +{ + int Start = Abc_Lit2Var(*pStart); + if ( Num < Start ) + { + *pStart |= 1; + return Count; + } + if ( Num > Start + 16 ) + { + int Shift = Num - (Start + 16); + if ( !Abc_LitIsCompl(*pStart) && (Shift >= 32 ? Count : Count & ~(~0 << Shift)) > 0 ) + *pStart |= 1; + Count >>= Shift; + Start += Shift; + *pStart = Abc_Var2Lit( Start, Abc_LitIsCompl(*pStart) ); + assert( Num <= Start + 16 ); + } + return Count + (1 << (Num-Start)); +} + +/**Function************************************************************* + + Synopsis [Testing of the counter] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_LogCounterTest2() +{ + word Count64 = 0; + + unsigned Count = 0; + int Start = 0; + + int Result, Result64; + + Count = If_LogCounter32Add( Count, &Start, 39 ); + Count = If_LogCounter32Add( Count, &Start, 35 ); + Count = If_LogCounter32Add( Count, &Start, 35 ); + Count = If_LogCounter32Add( Count, &Start, 36 ); + Count = If_LogCounter32Add( Count, &Start, 37 ); + Count = If_LogCounter32Add( Count, &Start, 38 ); + Count = If_LogCounter32Add( Count, &Start, 40 ); + Count = If_LogCounter32Add( Count, &Start, 1 ); + Count = If_LogCounter32Add( Count, &Start, 41 ); + Count = If_LogCounter32Add( Count, &Start, 42 ); + + Count64 = If_LogCounter64Add( Count64, 1 ); + Count64 = If_LogCounter64Add( Count64, 35 ); + Count64 = If_LogCounter64Add( Count64, 35 ); + Count64 = If_LogCounter64Add( Count64, 36 ); + Count64 = If_LogCounter64Add( Count64, 37 ); + Count64 = If_LogCounter64Add( Count64, 38 ); + Count64 = If_LogCounter64Add( Count64, 39 ); + Count64 = If_LogCounter64Add( Count64, 40 ); + Count64 = If_LogCounter64Add( Count64, 41 ); + Count64 = If_LogCounter64Add( Count64, 42 ); + + Result = If_LogCounter32Eval( Count, Start ); + Result64 = If_LogCounter64Eval( Count64 ); + + printf( "%d %d\n", Result, Result64 ); +} + +/**Function************************************************************* + + Synopsis [Adds the number to the numbers stored.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_LogCounterAdd( int * pTimes, int * pnTimes, int Num, int fXor ) +{ + int nTimes = *pnTimes; + pTimes[nTimes++] = Num; + if ( nTimes > 1 ) + { + int i, k; + for ( k = nTimes-1; k > 0; k-- ) + { + if ( pTimes[k] < pTimes[k-1] ) + break; + if ( pTimes[k] > pTimes[k-1] ) + { + ABC_SWAP( int, pTimes[k], pTimes[k-1] ); + continue; + } + pTimes[k-1] += 1 + fXor; + for ( nTimes--, i = k; i < nTimes; i++ ) + pTimes[i] = pTimes[i+1]; + } + } + assert( nTimes > 0 ); + *pnTimes = nTimes; + return pTimes[0] + (nTimes > 1 ? 1 + fXor : 0); +} + +/**Function************************************************************* + + Synopsis [Testing of the counter] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_LogCounterTest() +{ + int pArray[10] = { 1, 2, 4, 5, 6, 3, 1 }; + int i, nSize = 4; + + word Count64 = 0; + int Result, Result64; + + int pTimes[100]; + int nTimes = 0; + + for ( i = 0; i < nSize; i++ ) + Count64 = If_LogCounter64Add( Count64, pArray[i] ); + Result64 = If_LogCounter64Eval( Count64 ); + + for ( i = 0; i < nSize; i++ ) + Result = If_LogCounterAdd( pTimes, &nTimes, pArray[i], 0 ); + + printf( "%d %d\n", Result64, Result ); +} + +/**Function************************************************************* + + Synopsis [Inserts the entry while sorting them by delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +word If_AigVerifyArray( Vec_Int_t * vAig, int nLeaves, int fCompl ) +{ + assert( Vec_IntSize(vAig) > 0 ); + assert( Vec_IntEntryLast(vAig) < 2 ); + if ( Vec_IntSize(vAig) == 1 ) // const + return Vec_IntEntry(vAig, 0) ? ~((word)0) : 0; + if ( Vec_IntSize(vAig) == 2 ) // variable + { + assert( Vec_IntEntry(vAig, 0) == 0 ); + return Vec_IntEntry(vAig, 1) ? ~s_Truths6[0] : s_Truths6[0]; + } + else + { + word Truth0, Truth1, TruthR; + int i, iVar0, iVar1, iLit0, iLit1; + assert( Vec_IntSize(vAig) & 1 ); + Vec_IntForEachEntryDouble( vAig, iLit0, iLit1, i ) + { + iVar0 = Abc_Lit2Var( iLit0 ); + iVar1 = Abc_Lit2Var( iLit1 ); + Truth0 = iVar0 < nLeaves ? s_Truths6[iVar0] : Vec_WrdEntry( (Vec_Wrd_t *)vAig, iVar0 - nLeaves ); + Truth1 = iVar1 < nLeaves ? s_Truths6[iVar1] : Vec_WrdEntry( (Vec_Wrd_t *)vAig, iVar1 - nLeaves ); + if ( Abc_LitIsCompl(iLit0) ) + Truth0 = ~Truth0; + if ( Abc_LitIsCompl(iLit1) ) + Truth1 = ~Truth1; + assert( (i & 1) == 0 ); + Vec_WrdWriteEntry( (Vec_Wrd_t *)vAig, Abc_Lit2Var(i), Truth0 & Truth1 ); // overwriting entries + } + assert( i == Vec_IntSize(vAig) - 1 ); + TruthR = Truth0 & Truth1; + if ( Vec_IntEntry(vAig, i) ^ fCompl ) + TruthR = ~TruthR; + Vec_IntClear( vAig ); // useless + return TruthR; + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_LogCreateAnd( Vec_Int_t * vAig, int iLit0, int iLit1, int nSuppAll ) +{ + int iObjId = Vec_IntSize(vAig)/2 + nSuppAll; + Vec_IntPush( vAig, iLit0 ); + Vec_IntPush( vAig, iLit1 ); + return Abc_Var2Lit( iObjId, 0 ); +} +static inline int If_LogCreateMux( Vec_Int_t * vAig, int iLitC, int iLit1, int iLit0, int nSuppAll ) +{ + int iFanLit0 = If_LogCreateAnd( vAig, iLitC, iLit1, nSuppAll ); + int iFanLit1 = If_LogCreateAnd( vAig, Abc_LitNot(iLitC), iLit0, nSuppAll ); + int iResLit = If_LogCreateAnd( vAig, Abc_LitNot(iFanLit0), Abc_LitNot(iFanLit1), nSuppAll ); + return Abc_LitNot(iResLit); +} +static inline int If_LogCreateXor( Vec_Int_t * vAig, int iLit0, int iLit1, int nSuppAll ) +{ + return If_LogCreateMux( vAig, iLit0, Abc_LitNot(iLit1), iLit1, nSuppAll ); +} +static inline int If_LogCreateAndXor( Vec_Int_t * vAig, int iLit0, int iLit1, int nSuppAll, int fXor ) +{ + return fXor ? If_LogCreateXor(vAig, iLit0, iLit1, nSuppAll) : If_LogCreateAnd(vAig, iLit0, iLit1, nSuppAll); +} +static inline int If_LogCreateAndXorMulti( Vec_Int_t * vAig, int * pFaninLits, int nFanins, int nSuppAll, int fXor ) +{ + int i; + assert( nFanins > 0 ); + for ( i = nFanins - 1; i > 0; i-- ) + pFaninLits[i-1] = If_LogCreateAndXor( vAig, pFaninLits[i], pFaninLits[i-1], nSuppAll, fXor ); + return pFaninLits[0]; +} +static inline int If_LogCounterAddAig( int * pTimes, int * pnTimes, int * pFaninLits, int Num, int iLit, Vec_Int_t * vAig, int nSuppAll, int fXor ) +{ + int nTimes = *pnTimes; + if ( vAig ) + pFaninLits[nTimes] = iLit; + pTimes[nTimes++] = Num; + if ( nTimes > 1 ) + { + int i, k; + for ( k = nTimes-1; k > 0; k-- ) + { + if ( pTimes[k] < pTimes[k-1] ) + break; + if ( pTimes[k] > pTimes[k-1] ) + { + ABC_SWAP( int, pTimes[k], pTimes[k-1] ); + if ( vAig ) + ABC_SWAP( int, pFaninLits[k], pFaninLits[k-1] ); + continue; + } + pTimes[k-1] += 1 + fXor; + if ( vAig ) + pFaninLits[k-1] = If_LogCreateAndXor( vAig, pFaninLits[k], pFaninLits[k-1], nSuppAll, fXor ); + for ( nTimes--, i = k; i < nTimes; i++ ) + { + pTimes[i] = pTimes[i+1]; + if ( vAig ) + pFaninLits[i] = pFaninLits[i+1]; + } + } + } + assert( nTimes > 0 ); + *pnTimes = nTimes; + return pTimes[0] + (nTimes > 1 ? 1 + fXor : 0); +} + + +/**Function************************************************************* + + Synopsis [Compute delay/area profile of the structure.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutPinDelayGet( word D, int v ) { assert(v >= 0 && v < IF_MAX_FUNC_LUTSIZE); return (int)((D >> (v << 2)) & 0xF); } +static inline void If_CutPinDelaySet( word * pD, int v, int d ) { assert(v >= 0 && v < IF_MAX_FUNC_LUTSIZE); assert(d >= 0 && d < IF_MAX_FUNC_LUTSIZE); *pD |= ((word)d << (v << 2)); } +static inline word If_CutPinDelayInit( int v ) { assert(v >= 0 && v < IF_MAX_FUNC_LUTSIZE); return (word)1 << (v << 2); } +static inline word If_CutPinDelayMax( word D1, word D2, int nVars, int AddOn ) +{ + int v, Max; + word D = 0; + for ( v = 0; v < nVars; v++ ) + if ( (Max = Abc_MaxInt(If_CutPinDelayGet(D1, v), If_CutPinDelayGet(D2, v))) ) + If_CutPinDelaySet( &D, v, Abc_MinInt(Max + AddOn, 15) ); + return D; +} +static inline word If_CutPinDelayDecrement( word D1, int nVars ) +{ + int v; + word D = 0; + for ( v = 0; v < nVars; v++ ) + if ( If_CutPinDelayGet(D1, v) ) + If_CutPinDelaySet( &D, v, If_CutPinDelayGet(D1, v) - 1 ); + return D; +} +static inline int If_CutPinDelayEqual( word D1, word D2, int nVars ) // returns 1 if D1 has the same delays than D2 +{ + int v; + for ( v = 0; v < nVars; v++ ) + if ( If_CutPinDelayGet(D1, v) != If_CutPinDelayGet(D2, v) ) + return 0; + return 1; +} +static inline int If_CutPinDelayDom( word D1, word D2, int nVars ) // returns 1 if D1 has the same or smaller delays than D2 +{ + int v; + for ( v = 0; v < nVars; v++ ) + if ( If_CutPinDelayGet(D1, v) > If_CutPinDelayGet(D2, v) ) + return 0; + return 1; +} +static inline void If_CutPinDelayTranslate( word D, int nVars, char * pPerm ) // fills up the array +{ + int v, Delay; + for ( v = 0; v < nVars; v++ ) + { + Delay = If_CutPinDelayGet(D, v); + assert( Delay > 1 ); + pPerm[v] = Delay - 1; + } +} +static inline void If_CutPinDelayPrint( word D, int nVars ) +{ + int v; + printf( "Delay profile = {" ); + for ( v = 0; v < nVars; v++ ) + printf( " %d", If_CutPinDelayGet(D, v) ); + printf( " }\n" ); +} +static inline int If_LogCounterPinDelays( int * pTimes, int * pnTimes, word * pPinDels, int Num, word PinDel, int nSuppAll, int fXor ) +{ + int nTimes = *pnTimes; + pPinDels[nTimes] = PinDel; + pTimes[nTimes++] = Num; + if ( nTimes > 1 ) + { + int i, k; + for ( k = nTimes-1; k > 0; k-- ) + { + if ( pTimes[k] < pTimes[k-1] ) + break; + if ( pTimes[k] > pTimes[k-1] ) + { + ABC_SWAP( int, pTimes[k], pTimes[k-1] ); + ABC_SWAP( word, pPinDels[k], pPinDels[k-1] ); + continue; + } + pTimes[k-1] += 1 + fXor; + pPinDels[k-1] = If_CutPinDelayMax( pPinDels[k], pPinDels[k-1], nSuppAll, 1 + fXor ); + for ( nTimes--, i = k; i < nTimes; i++ ) + { + pTimes[i] = pTimes[i+1]; + pPinDels[i] = pPinDels[i+1]; + } + } + } + assert( nTimes > 0 ); + *pnTimes = nTimes; + return pTimes[0] + (nTimes > 1 ? 1 + fXor : 0); +} +static inline word If_LogPinDelaysMulti( word * pPinDels, int nFanins, int nSuppAll, int fXor ) +{ + int i; + assert( nFanins > 0 ); + for ( i = nFanins - 1; i > 0; i-- ) + pPinDels[i-1] = If_CutPinDelayMax( pPinDels[i], pPinDels[i-1], nSuppAll, 1 + fXor ); + return pPinDels[0]; +} +int If_CutPinDelaysSopArray3IntInt( Vec_Int_t * vCover, int * pTimes, int nSuppAll, char * pPerm ) +{ + word pPinDelsAnd[IF_MAX_FUNC_LUTSIZE], pPinDelsOr[32]; + int nCounterAnd, pCounterAnd[IF_MAX_FUNC_LUTSIZE]; + int nCounterOr, pCounterOr[32]; + int i, k, Entry, Literal, Delay = 0; + word ResAnd, ResOr; + if ( Vec_IntSize(vCover) > 32 ) + return -1; + nCounterOr = 0; + Vec_IntForEachEntry( vCover, Entry, i ) + { + nCounterAnd = 0; +// for ( k = 0; k < nSuppAll; k++ ) + for ( k = nSuppAll-1; k >= 0; k-- ) + { + Literal = 3 & (Entry >> (k << 1)); + if ( Literal == 1 || Literal == 2 ) // neg or pos literal + Delay = If_LogCounterPinDelays( pCounterAnd, &nCounterAnd, pPinDelsAnd, pTimes[k], If_CutPinDelayInit(k), nSuppAll, 0 ); + else if ( Literal != 0 ) + assert( 0 ); + } + assert( nCounterAnd > 0 ); + ResAnd = If_LogPinDelaysMulti( pPinDelsAnd, nCounterAnd, nSuppAll, 0 ); + Delay = If_LogCounterPinDelays( pCounterOr, &nCounterOr, pPinDelsOr, Delay, ResAnd, nSuppAll, 0 ); + } + assert( nCounterOr > 0 ); + ResOr = If_LogPinDelaysMulti( pPinDelsOr, nCounterOr, nSuppAll, 0 ); + If_CutPinDelayTranslate( ResOr, nSuppAll, pPerm ); + return Delay; +} +int If_CutPinDelaysSopArray3Int( unsigned * pTruth, int nLeaves, int * pTimes, Vec_Int_t * vCover, char * pPerm ) +{ + int RetValue = Kit_TruthIsop( pTruth, nLeaves, vCover, 1 ); + if ( RetValue == -1 ) + return -1; +// Kit_TruthIsopPrint( pTruth, nLeaves, vCover, 1 ); + return If_CutPinDelaysSopArray3IntInt( vCover, pTimes, nLeaves, pPerm ); +} +int If_CutPinDelaysSopArray3( If_Man_t * p, If_Cut_t * pCut, char * pPerm ) +{ + if ( p->vCover == NULL ) + p->vCover = Vec_IntAlloc(0); + if ( pCut->nLeaves == 0 ) // const + return 0; + if ( pCut->nLeaves == 1 ) // variable + { + pPerm[0] = 0; + return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay; + } + else + { + int i, pTimes[IF_MAX_FUNC_LUTSIZE]; + for ( i = 0; i < If_CutLeaveNum(pCut); i++ ) + pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay; + return If_CutPinDelaysSopArray3Int( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), pTimes, p->vCover, pPerm ); + } +} + +/**Function************************************************************* + + Synopsis [Evaluate delay using SOP balancing.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutDelaySopArray3IntInt( Vec_Int_t * vCover, int * pTimes, Vec_Int_t * vAig, int * piRes, int nSuppAll, int * pArea ) +{ + int nCounterAnd, pCounterAnd[IF_MAX_FUNC_LUTSIZE], pFaninLitsAnd[IF_MAX_FUNC_LUTSIZE]; + int nCounterOr, pCounterOr[32], pFaninLitsOr[32]; + int i, k, Entry, Literal, nLits, Delay = 0, iRes = 0; + if ( Vec_IntSize(vCover) > 32 ) + return -1; + nCounterOr = 0; + Vec_IntForEachEntry( vCover, Entry, i ) + { + nCounterAnd = nLits = 0; + for ( k = 0; k < nSuppAll; k++ ) + { + Literal = 3 & (Entry >> (k << 1)); + if ( Literal == 1 ) // neg literal + nLits++, Delay = If_LogCounterAddAig( pCounterAnd, &nCounterAnd, pFaninLitsAnd, pTimes[k], Abc_Var2Lit(k, 1), vAig, nSuppAll, 0 ); + else if ( Literal == 2 ) // pos literal + nLits++, Delay = If_LogCounterAddAig( pCounterAnd, &nCounterAnd, pFaninLitsAnd, pTimes[k], Abc_Var2Lit(k, 0), vAig, nSuppAll, 0 ); + else if ( Literal != 0 ) + assert( 0 ); + } + assert( nCounterAnd > 0 ); + assert( nLits > 0 ); + if ( vAig ) + iRes = If_LogCreateAndXorMulti( vAig, pFaninLitsAnd, nCounterAnd, nSuppAll, 0 ); + else + *pArea += nLits == 1 ? 0 : nLits - 1; + Delay = If_LogCounterAddAig( pCounterOr, &nCounterOr, pFaninLitsOr, Delay, Abc_LitNot(iRes), vAig, nSuppAll, 0 ); + } + assert( nCounterOr > 0 ); + if ( vAig ) + *piRes = Abc_LitNot( If_LogCreateAndXorMulti( vAig, pFaninLitsOr, nCounterOr, nSuppAll, 0 ) ); + else + *pArea += Vec_IntSize(vCover) == 1 ? 0 : Vec_IntSize(vCover) - 1; + return Delay; +} +int If_CutDelaySopArray3Int( unsigned * pTruth, int nLeaves, int * pTimes, Vec_Int_t * vCover, Vec_Int_t * vAig, int fCompl, int * pArea ) +{ + int iRes = 0, Res; + int RetValue = Kit_TruthIsop( pTruth, nLeaves, vCover, 1 ); + if ( RetValue == -1 ) + return -1; + Res = If_CutDelaySopArray3IntInt( vCover, pTimes, vAig, &iRes, nLeaves, pArea ); + assert( vAig == NULL || Abc_Lit2Var(iRes) == nLeaves + Abc_Lit2Var(Vec_IntSize(vAig)) - 1 ); + if ( vAig ) + Vec_IntPush( vAig, RetValue ^ Abc_LitIsCompl(iRes) ^ fCompl ); + assert( vAig == NULL || (Vec_IntSize(vAig) & 1) ); + return Res; +} +int If_CutDelaySopArray3( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ) +{ + pCut->fUser = 1; + if ( p->vCover == NULL ) + p->vCover = Vec_IntAlloc(0); + if ( vAig ) + Vec_IntClear( vAig ); + if ( pCut->nLeaves == 0 ) // const + { + assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 ); + if ( vAig ) + Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) ); + return 0; + } + if ( pCut->nLeaves == 1 ) // variable + { + assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 1 ); + if ( vAig ) + Vec_IntPush( vAig, 0 ); + if ( vAig ) + Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) ); + return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay; + } + else + { + int Delay, Area = 0; + int i, pTimes[IF_MAX_FUNC_LUTSIZE]; + for ( i = 0; i < If_CutLeaveNum(pCut); i++ ) + pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay; + Delay = If_CutDelaySopArray3Int( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), pTimes, p->vCover, vAig, 0, &Area ); + pCut->Cost = Area; + return Delay; + } +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/map/if/ifDsd.c b/src/map/if/ifDsd.c index 055eab84..83dec183 100644 --- a/src/map/if/ifDsd.c +++ b/src/map/if/ifDsd.c @@ -1849,14 +1849,271 @@ void If_DsdManTest() SeeAlso [] ***********************************************************************/ +static inline int If_LogCounterAdd( int * pTimes, int * pnTimes, int Num, int fXor ) +{ + int nTimes = *pnTimes; + pTimes[nTimes++] = Num; + if ( nTimes > 1 ) + { + int i, k; + for ( k = nTimes-1; k > 0; k-- ) + { + if ( pTimes[k] < pTimes[k-1] ) + break; + if ( pTimes[k] > pTimes[k-1] ) + { + ABC_SWAP( int, pTimes[k], pTimes[k-1] ); + continue; + } + pTimes[k-1] += 1 + fXor; + for ( nTimes--, i = k; i < nTimes; i++ ) + pTimes[i] = pTimes[i+1]; + } + } + assert( nTimes > 0 ); + *pnTimes = nTimes; + return pTimes[0] + (nTimes > 1 ? 1 + fXor : 0); +} +int If_DsdCutBalanceCost_rec( If_DsdMan_t * p, int Id, int * pTimes, int * pArea, int * pnSupp ) +{ + If_DsdObj_t * pObj = If_DsdVecObj( &p->vObjs, Id ); + if ( If_DsdObjType(pObj) == IF_DSD_PRIME ) + return -1; + if ( If_DsdObjType(pObj) == IF_DSD_VAR ) + return pTimes[(*pnSupp)++]; + if ( If_DsdObjType(pObj) == IF_DSD_MUX ) + { + int i, iFanin, Delay[3]; + If_DsdObjForEachFaninLit( &p->vObjs, pObj, iFanin, i ) + { + Delay[i] = If_DsdCutBalanceCost_rec( p, Abc_Lit2Var(iFanin), pTimes, pArea, pnSupp ); + if ( Delay[i] == -1 ) + return -1; + } + *pArea += 3; + return 2 + Abc_MaxInt(Delay[0], Abc_MaxInt(Delay[1], Delay[2])); + } + else + { + int i, iFanin, Delay, Result = 0; + int nCounter = 0, pCounter[IF_MAX_FUNC_LUTSIZE]; + assert( If_DsdObjType(pObj) == IF_DSD_AND || If_DsdObjType(pObj) == IF_DSD_XOR ); + If_DsdObjForEachFaninLit( &p->vObjs, pObj, iFanin, i ) + { + Delay = If_DsdCutBalanceCost_rec( p, Abc_Lit2Var(iFanin), pTimes, pArea, pnSupp ); + if ( Delay == -1 ) + return -1; + Result = If_LogCounterAdd( pCounter, &nCounter, Delay, If_DsdObjType(pObj) == IF_DSD_XOR ); + } + *pArea += (If_DsdObjType(pObj) == IF_DSD_XOR ? 3 : 1); + return Result; + } +} +int If_DsdCutBalanceCostInt( If_DsdMan_t * p, int iDsd, int * pTimes, int * pArea ) +{ + int nSupp = 0; + int Res = If_DsdCutBalanceCost_rec( p, Abc_Lit2Var(iDsd), pTimes, pArea, &nSupp ); + assert( nSupp == If_DsdVecLitSuppSize( &p->vObjs, iDsd ) ); + return Res; +} int If_DsdCutBalanceCost( If_Man_t * pIfMan, If_Cut_t * pCut ) { - return 0; + pCut->fUser = 1; + pCut->Cost = 0; + if ( pCut->nLeaves == 0 ) + return 0; + if ( pCut->nLeaves == 1 ) + return (int)If_ObjCutBest(If_CutLeaf(pIfMan, pCut, 0))->Delay; + else + { + If_Obj_t * pLeaf; + int i, Delay, Area = 0, pTimes[IF_MAX_FUNC_LUTSIZE]; + If_CutForEachLeaf( pIfMan, pCut, pLeaf, i ) + pTimes[i] = (int)If_ObjCutBest(pLeaf)->Delay; + Delay = If_DsdCutBalanceCostInt( pIfMan->pIfDsdMan, If_CutDsdLit(pCut), pTimes, &Area ); + pCut->Cost = Area; + return Delay; + } } -int If_DsdCutBalance( void * pGia, If_Man_t * pIfMan, If_Cut_t * pCut, Vec_Int_t * vLeaves, int fHash ) + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_LogCreateAnd( Vec_Int_t * vAig, int iLit0, int iLit1, int nSuppAll ) { - Gia_Man_t * p = (Gia_Man_t *)pGia; - return 0; + int iObjId = Vec_IntSize(vAig)/2 + nSuppAll; + Vec_IntPush( vAig, iLit0 ); + Vec_IntPush( vAig, iLit1 ); + return Abc_Var2Lit( iObjId, 0 ); +} +static inline int If_LogCreateMux( Vec_Int_t * vAig, int iLitC, int iLit1, int iLit0, int nSuppAll ) +{ + int iFanLit0 = If_LogCreateAnd( vAig, iLitC, iLit1, nSuppAll ); + int iFanLit1 = If_LogCreateAnd( vAig, Abc_LitNot(iLitC), iLit0, nSuppAll ); + int iResLit = If_LogCreateAnd( vAig, Abc_LitNot(iFanLit0), Abc_LitNot(iFanLit1), nSuppAll ); + return Abc_LitNot(iResLit); +} +static inline int If_LogCreateXor( Vec_Int_t * vAig, int iLit0, int iLit1, int nSuppAll ) +{ + return If_LogCreateMux( vAig, iLit0, Abc_LitNot(iLit1), iLit1, nSuppAll ); +} +static inline int If_LogCreateAndXor( Vec_Int_t * vAig, int iLit0, int iLit1, int nSuppAll, int fXor ) +{ + return fXor ? If_LogCreateXor(vAig, iLit0, iLit1, nSuppAll) : If_LogCreateAnd(vAig, iLit0, iLit1, nSuppAll); +} +static inline int If_LogCreateAndXorMulti( Vec_Int_t * vAig, int * pFaninLits, int nFanins, int nSuppAll, int fXor ) +{ + int i; + assert( nFanins > 0 ); + for ( i = nFanins - 1; i > 0; i-- ) + pFaninLits[i-1] = If_LogCreateAndXor( vAig, pFaninLits[i], pFaninLits[i-1], nSuppAll, fXor ); + return pFaninLits[0]; +} + +static inline int If_LogCounterAddAig( int * pTimes, int * pnTimes, int * pFaninLits, int Num, int iLit, Vec_Int_t * vAig, int nSuppAll, int fXor ) +{ + int nTimes = *pnTimes; + if ( vAig ) + pFaninLits[nTimes] = iLit; + pTimes[nTimes++] = Num; + if ( nTimes > 1 ) + { + int i, k; + for ( k = nTimes-1; k > 0; k-- ) + { + if ( pTimes[k] < pTimes[k-1] ) + break; + if ( pTimes[k] > pTimes[k-1] ) + { + ABC_SWAP( int, pTimes[k], pTimes[k-1] ); + if ( vAig ) + ABC_SWAP( int, pFaninLits[k], pFaninLits[k-1] ); + continue; + } + pTimes[k-1] += 1 + fXor; + if ( vAig ) + pFaninLits[k-1] = If_LogCreateAndXor( vAig, pFaninLits[k], pFaninLits[k-1], nSuppAll, fXor ); + for ( nTimes--, i = k; i < nTimes; i++ ) + { + pTimes[i] = pTimes[i+1]; + if ( vAig ) + pFaninLits[i] = pFaninLits[i+1]; + } + } + } + assert( nTimes > 0 ); + *pnTimes = nTimes; + return pTimes[0] + (nTimes > 1 ? 1 + fXor : 0); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_DsdCutBalanceAig_rec( If_DsdMan_t * p, int Id, int * pTimes, int * pnSupp, Vec_Int_t * vAig, int * piLit, int nSuppAll, int * pArea ) +{ + If_DsdObj_t * pObj = If_DsdVecObj( &p->vObjs, Id ); + if ( If_DsdObjType(pObj) == IF_DSD_PRIME ) + return -1; + if ( If_DsdObjType(pObj) == IF_DSD_VAR ) + { + if ( vAig ) + *piLit = Abc_Var2Lit( *pnSupp, 0 ); + return pTimes[(*pnSupp)++]; + } + if ( If_DsdObjType(pObj) == IF_DSD_MUX ) + { + int i, iFanin, Delay[3], pFaninLits[3]; + If_DsdObjForEachFaninLit( &p->vObjs, pObj, iFanin, i ) + { + Delay[i] = If_DsdCutBalanceAig_rec( p, Abc_Lit2Var(iFanin), pTimes, pnSupp, vAig, pFaninLits+i, nSuppAll, pArea ); + if ( Delay[i] == -1 ) + return -1; + } + if ( vAig ) + *piLit = If_LogCreateMux( vAig, pFaninLits[0], pFaninLits[1], pFaninLits[2], nSuppAll ); + else + *pArea += 3; + return 2 + Abc_MaxInt(Delay[0], Abc_MaxInt(Delay[1], Delay[2])); + } + assert( If_DsdObjType(pObj) == IF_DSD_AND || If_DsdObjType(pObj) == IF_DSD_XOR ); + { + int i, iFanin, Delay, Result = 0; + int fXor = (If_DsdObjType(pObj) == IF_DSD_XOR); + int nCounter = 0, pCounter[IF_MAX_FUNC_LUTSIZE], pFaninLits[IF_MAX_FUNC_LUTSIZE]; + If_DsdObjForEachFaninLit( &p->vObjs, pObj, iFanin, i ) + { + Delay = If_DsdCutBalanceAig_rec( p, Abc_Lit2Var(iFanin), pTimes, pnSupp, vAig, pFaninLits+i, nSuppAll, pArea ); + if ( Delay == -1 ) + return -1; + Result = If_LogCounterAddAig( pCounter, &nCounter, pFaninLits, Delay, pFaninLits[i], vAig, nSuppAll, fXor ); + } + if ( vAig ) + *piLit = If_LogCreateAndXorMulti( vAig, pFaninLits, nCounter, nSuppAll, fXor ); + else + *pArea += (pObj->nFans - 1) * (1 + 2 * fXor); + return Result; + } +} +int If_DsdCutBalanceAigInt( If_DsdMan_t * p, int iDsd, int * pTimes, Vec_Int_t * vAig, int * pArea ) +{ + int nSupp = 0, iLit = 0; + int nSuppAll = If_DsdVecLitSuppSize( &p->vObjs, iDsd ); + int Res = If_DsdCutBalanceAig_rec( p, Abc_Lit2Var(iDsd), pTimes, &nSupp, vAig, &iLit, nSuppAll, pArea ); + assert( nSupp == nSuppAll ); + assert( vAig == NULL || Abc_Lit2Var(iLit) == nSupp + Abc_Lit2Var(Vec_IntSize(vAig)) - 1 ); + if ( vAig ) + Vec_IntPush( vAig, Abc_LitIsCompl(iLit) ); + assert( vAig == NULL || (Vec_IntSize(vAig) & 1) ); + return Res; +} +int If_DsdCutBalanceAig( If_Man_t * pIfMan, If_Cut_t * pCut, Vec_Int_t * vAig ) +{ + pCut->fUser = 1; + if ( vAig ) + Vec_IntClear( vAig ); + if ( pCut->nLeaves == 0 ) // const + { + assert( Abc_Lit2Var(If_CutDsdLit(pCut)) == 0 ); + if ( vAig ) + Vec_IntPush( vAig, Abc_LitIsCompl(If_CutDsdLit(pCut)) ); + return 0; + } + if ( pCut->nLeaves == 1 ) // variable + { + assert( Abc_Lit2Var(If_CutDsdLit(pCut)) == 1 ); + if ( vAig ) + Vec_IntPush( vAig, 0 ); + if ( vAig ) + Vec_IntPush( vAig, Abc_LitIsCompl(If_CutDsdLit(pCut)) ); + return (int)If_ObjCutBest(If_CutLeaf(pIfMan, pCut, 0))->Delay; + } + else + { + If_Obj_t * pLeaf; + int i, pTimes[IF_MAX_FUNC_LUTSIZE]; + int Delay, Area = 0; + If_CutForEachLeaf( pIfMan, pCut, pLeaf, i ) + pTimes[i] = (int)If_ObjCutBest(pLeaf)->Delay; + Delay = If_DsdCutBalanceAigInt( pIfMan->pIfDsdMan, If_CutDsdLit(pCut), pTimes, vAig, &Area ); + pCut->Cost = Area; + return Delay; + } } diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c index 7e52650d..29d648ef 100644 --- a/src/map/if/ifMan.c +++ b/src/map/if/ifMan.c @@ -206,6 +206,7 @@ void If_ManStop( If_Man_t * p ) Vec_PtrFree( p->vObjs ); Vec_PtrFree( p->vTemp ); Vec_IntFreeP( &p->vCover ); + Vec_IntFreeP( &p->vArray ); Vec_WrdFreeP( &p->vAnds ); Vec_WrdFreeP( &p->vAndGate ); Vec_WrdFreeP( &p->vOrGate ); diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 2db26927..aa43cd43 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -125,6 +125,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep // recompute the parameters of the best cut if ( p->pPars->fDelayOpt ) pCut->Delay = If_CutDelaySopCost( p, pCut ); +// pCut->Delay = If_CutDelaySopArray3( p, pCut, NULL ); else if ( p->pPars->fDsdBalance ) pCut->Delay = If_DsdCutBalanceCost( p, pCut ); else if ( p->pPars->fUserRecLib ) @@ -281,6 +282,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep // check if the cut satisfies the required times if ( p->pPars->fDelayOpt ) pCut->Delay = If_CutDelaySopCost( p, pCut ); +// pCut->Delay = If_CutDelaySopArray3( p, pCut, NULL ); else if ( p->pPars->fDsdBalance ) pCut->Delay = If_DsdCutBalanceCost( p, pCut ); else if ( p->pPars->fUserRecLib ) diff --git a/src/map/if/ifTime.c b/src/map/if/ifTime.c index 07258f95..cc08cfab 100644 --- a/src/map/if/ifTime.c +++ b/src/map/if/ifTime.c @@ -249,7 +249,7 @@ Vec_Wrd_t * If_CutDelaySopAnds( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vCove ***********************************************************************/ Vec_Wrd_t * If_CutDelaySopArray( If_Man_t * p, If_Cut_t * pCut ) -{ +{ abctime clk; Vec_Wrd_t * vAnds; int RetValue; @@ -265,7 +265,6 @@ Vec_Wrd_t * If_CutDelaySopArray( If_Man_t * p, If_Cut_t * pCut ) if ( RetValue == -1 ) return NULL; assert( RetValue == 0 || RetValue == 1 ); - clk = Abc_Clock(); vAnds = If_CutDelaySopAnds( p, pCut, p->vCover, RetValue ); s_timeOld += Abc_Clock() - clk; @@ -343,6 +342,8 @@ int If_CutDelaySopCost( If_Man_t * p, If_Cut_t * pCut ) If_And_t Leaf; Vec_Wrd_t * vAnds; int i, Delay; +// char pPerm[16]; +// int Delay2, TestArea; // mark cut as a user cut pCut->fUser = 1; vAnds = If_CutDelaySopArray( p, pCut ); @@ -357,12 +358,12 @@ int If_CutDelaySopCost( If_Man_t * p, If_Cut_t * pCut ) Leaf = If_WrdToAnd( Vec_WrdEntryLast(vAnds) ); else Leaf.Delay = 0; - if ( Vec_WrdSize(vAnds) > (int)pCut->nLeaves ) - pCut->Cost = Vec_WrdSize(vAnds) - pCut->nLeaves; + if ( pCut->nLeaves == 0 ) + pCut->Cost = 0; else if ( pCut->nLeaves == 1 ) - pCut->Cost = 1; - else if ( pCut->nLeaves == 0 ) pCut->Cost = 0; + else if ( Vec_WrdSize(vAnds) > (int)pCut->nLeaves ) + pCut->Cost = Vec_WrdSize(vAnds) - pCut->nLeaves; else assert( 0 ); // get the permutation for ( i = 0; i < (int)pCut->nLeaves; i++ ) @@ -375,6 +376,30 @@ int If_CutDelaySopCost( If_Man_t * p, If_Cut_t * pCut ) // verify the delay // Delay = If_CutDelay( p, pObj, pCut ); // assert( (int)Leaf.Delay == Delay ); +/* + TestArea = pCut->Cost; + Delay = If_CutDelaySopArray3( p, pCut, NULL ); + if ( Delay != (int)Leaf.Delay || (int)pCut->Cost != TestArea ) + { + int s = 0; + Kit_DsdPrintFromTruth( If_CutTruth(p, pCut), pCut->nLeaves ); printf( "\n" ); + Delay = If_CutDelaySopArray3( p, pCut, NULL ); + } + Delay2 = If_CutPinDelaysSopArray3( p, pCut, pPerm ); + assert( Delay == Delay2 ); + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + { + if ( pPerm[i] != pCut->pPerm[i] ) + { + int s = 0; + Kit_DsdPrintFromTruth( If_CutTruth(p, pCut), pCut->nLeaves ); printf( "\n" ); + Delay2 = If_CutPinDelaysSopArray3( p, pCut, pPerm ); + } + assert( pPerm[i] == pCut->pPerm[i] ); + } + printf( "Corrrect\n" ); +// printf( "%d ", Delay ); +*/ return Leaf.Delay; } @@ -717,6 +742,13 @@ void If_CutPropagateRequired( If_Man_t * p, If_Obj_t * pObj, If_Cut_t * pCut, fl { if ( pCut->fUser ) { +/* + if ( p->pPars->fDelayOpt ) + { + int Del = If_CutPinDelaysSopArray3( p, pCut, pCut->pPerm ); + assert( Del == pCut->Delay ); + } +*/ If_CutForEachLeaf( p, pCut, pLeaf, i ) { Pin2PinDelay = pCut->pPerm ? (pCut->pPerm[i] == IF_BIG_CHAR ? -IF_BIG_CHAR : pCut->pPerm[i]) : 1; diff --git a/src/map/if/module.make b/src/map/if/module.make index 8518406d..13c40ef9 100644 --- a/src/map/if/module.make +++ b/src/map/if/module.make @@ -7,6 +7,7 @@ SRC += src/map/if/ifCom.c \ src/map/if/ifDec10.c \ src/map/if/ifDec16.c \ src/map/if/ifDec75.c \ + src/map/if/ifDelay.c \ src/map/if/ifDsd.c \ src/map/if/ifLibBox.c \ src/map/if/ifLibLut.c \ -- cgit v1.2.3