diff options
Diffstat (limited to 'src/map/if')
-rw-r--r-- | src/map/if/if.h | 5 | ||||
-rw-r--r-- | src/map/if/ifCut.c | 2 | ||||
-rw-r--r-- | src/map/if/ifDec07.c | 2 | ||||
-rw-r--r-- | src/map/if/ifDec16.c | 127 | ||||
-rw-r--r-- | src/map/if/ifDec75.c | 341 | ||||
-rw-r--r-- | src/map/if/module.make | 1 |
6 files changed, 477 insertions, 1 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h index be787a0b..5076bb28 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -117,6 +117,8 @@ struct If_Par_t_ int fEnableCheck07;// enable additional checking int fEnableCheck08;// enable additional checking int fEnableCheck10;// enable additional checking + int fEnableCheck75;// enable additional checking + int fEnableCheck75u;// enable additional checking int fEnableRealPos;// enable additional feature int fUseDsd; // compute DSD of the cut functions int fDeriveLuts; // enables deriving LUT structures @@ -492,6 +494,9 @@ extern int If_CutPerformCheck07( If_Man_t * p, unsigned * pTruth, in extern int If_CutPerformCheck08( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); extern int If_CutPerformCheck10( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); extern int If_CutPerformCheck16( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck45( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck54( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck75( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); extern float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float WireDelay ); extern int If_CluCheckExt( void * p, word * pTruth, int nVars, int nLutLeaf, int nLutRoot, char * pLut0, char * pLut1, word * pFunc0, word * pFunc1 ); diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c index 78f9ec68..c9edc66b 100644 --- a/src/map/if/ifCut.c +++ b/src/map/if/ifCut.c @@ -856,7 +856,7 @@ void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut ) return; } - if ( (p->pPars->fUseDsd || p->pPars->fUseBat || p->pPars->fEnableCheck07 || p->pPars->fEnableCheck08 || p->pPars->fEnableCheck10 || p->pPars->pLutStruct || p->pPars->fUserRecLib) && !pCut->fUseless ) + if ( (p->pPars->fUseDsd || p->pPars->fUseBat || p->pPars->fEnableCheck07 || p->pPars->fEnableCheck08 || p->pPars->fEnableCheck10 || p->pPars->fEnableCheck75 || p->pPars->fEnableCheck75u || p->pPars->pLutStruct || p->pPars->fUserRecLib) && !pCut->fUseless ) { If_Cut_t * pFirst = pCutSet->ppCuts[0]; if ( pFirst->fUseless || If_ManSortCompare(p, pFirst, pCut) == 1 ) diff --git a/src/map/if/ifDec07.c b/src/map/if/ifDec07.c index 6d454a96..4c586ed8 100644 --- a/src/map/if/ifDec07.c +++ b/src/map/if/ifDec07.c @@ -455,10 +455,12 @@ word If_Dec7Perform( word t0[2], int fDerive ) // start arrays for ( i = 0; i < 7; i++ ) { +/* if ( i < 6 ) assert( If_Dec6HasVar( t[0], i ) || If_Dec6HasVar( t[1], i ) ); else assert( t[0] != t[1] ); +*/ Pla2Var[i] = Var2Pla[i] = i; } // generate permutations diff --git a/src/map/if/ifDec16.c b/src/map/if/ifDec16.c index e349f6eb..729b0489 100644 --- a/src/map/if/ifDec16.c +++ b/src/map/if/ifDec16.c @@ -1749,6 +1749,133 @@ If_Grp_t If_CluCheck( If_Man_t * p, word * pTruth0, int nVars, int iVarStart, in return G1; } + +static inline word Abc_Tt6Cofactor0( word t, int iVar ) +{ + assert( iVar >= 0 && iVar < 6 ); + return (t &~Truth6[iVar]) | ((t &~Truth6[iVar]) << (1<<iVar)); +} +static inline word Abc_Tt6Cofactor1( word t, int iVar ) +{ + assert( iVar >= 0 && iVar < 6 ); + return (t & Truth6[iVar]) | ((t & Truth6[iVar]) >> (1<<iVar)); +} +int If_CluCheckDecIn( word t, int nVars ) +{ + int v, u, Cof2[2], Cof4[4]; +// for ( v = 0; v < nVars; v++ ) + for ( v = 0; v < 1; v++ ) // restrict to the first (decomposed) input + { + Cof2[0] = Abc_Tt6Cofactor0( t, v ); + Cof2[1] = Abc_Tt6Cofactor1( t, v ); + for ( u = v+1; u < nVars; u++ ) + { + Cof4[0] = Abc_Tt6Cofactor0( Cof2[0], u ); + Cof4[1] = Abc_Tt6Cofactor1( Cof2[0], u ); + Cof4[2] = Abc_Tt6Cofactor0( Cof2[1], u ); + Cof4[3] = Abc_Tt6Cofactor1( Cof2[1], u ); + if ( Cof4[0] == Cof4[1] && Cof4[0] == Cof4[2] ) + return 1; + if ( Cof4[0] == Cof4[2] && Cof4[0] == Cof4[3] ) + return 1; + if ( Cof4[0] == Cof4[1] && Cof4[0] == Cof4[3] ) + return 1; + if ( Cof4[1] == Cof4[2] && Cof4[1] == Cof4[3] ) + return 1; + } + } + return 0; +} +int If_CluCheckDecInU( word t, int nVars ) +{ + int v, u, Cof2[2], Cof4[4]; +// for ( v = 0; v < nVars; v++ ) + for ( v = 0; v < 1; v++ ) // restrict to the first (decomposed) input + { + Cof2[0] = Abc_Tt6Cofactor0( t, v ); + Cof2[1] = Abc_Tt6Cofactor1( t, v ); + for ( u = v+1; u < nVars; u++ ) + { + Cof4[0] = Abc_Tt6Cofactor0( Cof2[0], u ); + Cof4[1] = Abc_Tt6Cofactor1( Cof2[0], u ); + Cof4[2] = Abc_Tt6Cofactor0( Cof2[1], u ); + Cof4[3] = Abc_Tt6Cofactor1( Cof2[1], u ); + if ( Cof4[0] == Cof4[1] && Cof4[0] == Cof4[2] ) + return 1; + if ( Cof4[0] == Cof4[2] && Cof4[0] == Cof4[3] ) + return 1; + } + } + return 0; +} +int If_CluCheckDecOut( word t, int nVars ) +{ + int v; + for ( v = 0; v < nVars; v++ ) + if ( + (t & Truth6[v]) == 0 || // F * !a + (~t & Truth6[v]) == 0 || // !F * !a + (t & ~Truth6[v]) == 0 || // F * a + (~t & ~Truth6[v]) == 0 // !F * a + ) + return 1; + return 0; +} +int If_CluCheckDecOutU( word t, int nVars ) +{ + int v; + for ( v = 0; v < nVars; v++ ) + if ( + (t & ~Truth6[v]) == 0 || // F * a + (~t & ~Truth6[v]) == 0 // !F * a + ) + return 1; + return 0; +} + +int If_CutPerformCheck45( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +{ + // 5LUT -> 4LUT + If_Grp_t G, R; + word Func0, Func1; + G = If_CluCheck( p, (word *)pTruth, nLeaves, 0, 5, 4, &R, &Func0, &Func1, NULL, 0 ); + if ( G.nVars == 0 ) + return 0; + Func0 = If_CluAdjust( Func0, R.nVars ); + Func1 = If_CluAdjust( Func1, G.nVars ); +#if 0 + Kit_DsdPrintFromTruth( pTruth, nVars ); printf( "\n" ); + Kit_DsdPrintFromTruth( (unsigned*)&Func0, R.nVars ); printf( "\n" ); + Kit_DsdPrintFromTruth( (unsigned*)&Func1, G.nVars ); printf( "\n" ); + If_CluPrintGroup( &R ); + If_CluPrintGroup( &G ); +#endif + if ( G.nVars < 5 || (p->pPars->fEnableCheck75 && If_CluCheckDecOut(Func1, 5)) || (p->pPars->fEnableCheck75u && If_CluCheckDecOutU(Func1, 5)) ) + return 1; + return 0; +} +int If_CutPerformCheck54( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +{ + // 4LUT -> 5LUT + If_Grp_t G, R; + word Func0, Func1; + G = If_CluCheck( p, (word *)pTruth, nLeaves, 0, 4, 5, &R, &Func0, &Func1, NULL, 0 ); + if ( G.nVars == 0 ) + return 0; + Func0 = If_CluAdjust( Func0, R.nVars ); + Func1 = If_CluAdjust( Func1, G.nVars ); +#if 0 + Kit_DsdPrintFromTruth( pTruth, nVars ); printf( "\n" ); + Kit_DsdPrintFromTruth( (unsigned*)&Func0, R.nVars ); printf( "\n" ); + Kit_DsdPrintFromTruth( (unsigned*)&Func1, G.nVars ); printf( "\n" ); + If_CluPrintGroup( &R ); + If_CluPrintGroup( &G ); +#endif + if ( R.nVars < 5 || (p->pPars->fEnableCheck75 && If_CluCheckDecIn(Func0, 5)) || (p->pPars->fEnableCheck75u && If_CluCheckDecInU(Func0, 5)) ) + return 1; + return 0; +} + // returns the best group found If_Grp_t If_CluCheck3( If_Man_t * p, word * pTruth0, int nVars, int nLutLeaf, int nLutLeaf2, int nLutRoot, If_Grp_t * pR, If_Grp_t * pG2, word * pFunc0, word * pFunc1, word * pFunc2 ) diff --git a/src/map/if/ifDec75.c b/src/map/if/ifDec75.c new file mode 100644 index 00000000..0135f87d --- /dev/null +++ b/src/map/if/ifDec75.c @@ -0,0 +1,341 @@ +/**CFile**************************************************************** + + FileName [ifDec75.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapping based on priority cuts.] + + Synopsis [Performs additional check.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - November 21, 2006.] + + Revision [$Id: ifDec75.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "if.h" +#include "misc/extra/extra.h" +#include "bool/kit/kit.h" +#include "opt/dau/dau.h" +#include "misc/util/utilTruth.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Finds all boundsets for which decomposition exists.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Dau_DsdCheckDecExist_rec( char * pStr, char ** p, int * pMatches, int * pnSupp ) +{ + if ( **p == '!' ) + (*p)++; + while ( (**p >= 'A' && **p <= 'F') || (**p >= '0' && **p <= '9') ) + (*p)++; + if ( **p >= 'a' && **p <= 'z' ) // var + { + (*pnSupp)++; + return 0; + } + if ( **p == '(' || **p == '[' ) // and/xor + { + unsigned Mask = 0; + int m, pSupps[8] = {0}, nParts = 0, nMints; + char * q = pStr + pMatches[ *p - pStr ]; + assert( *q == **p + 1 + (**p != '(') ); + for ( (*p)++; *p < q; (*p)++ ) + { + Mask |= Dau_DsdCheckDecExist_rec( pStr, p, pMatches, &pSupps[nParts] ); + *pnSupp += pSupps[nParts++]; + } + assert( *p == q ); + assert( nParts > 1 ); + nMints = (1 << nParts); + for ( m = 1; m < nMints; m++ ) + { + int i, Sum = 0; + for ( i = 0; i < nParts; i++ ) + if ( (m >> i) & 1 ) + Sum += pSupps[i]; + assert( Sum > 0 && Sum <= 8 ); + if ( Sum >= 2 ) + Mask |= (1 << Sum); + } + return Mask; + } + if ( **p == '<' || **p == '{' ) // mux + { + int uSupp; + unsigned Mask = 0; + char * q = pStr + pMatches[ *p - pStr ]; + assert( *q == **p + 1 + (**p != '(') ); + for ( (*p)++; *p < q; (*p)++ ) + { + uSupp = 0; + Mask |= Dau_DsdCheckDecExist_rec( pStr, p, pMatches, &uSupp ); + *pnSupp += uSupp; + } + assert( *p == q ); + Mask |= (1 << *pnSupp); + return Mask; + } + assert( 0 ); + return 0; +} +int Dau_DsdCheckDecExist( char * pDsd ) +{ + int nSupp = 0; + if ( pDsd[1] == 0 ) + return 0; + return Dau_DsdCheckDecExist_rec( pDsd, &pDsd, Dau_DsdComputeMatches(pDsd), &nSupp ); +} + +/**Function************************************************************* + + Synopsis [Finds all boundsets for which AND-decomposition exists.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Dau_DsdCheckDecAndExist_rec( char * pStr, char ** p, int * pMatches, int * pnSupp ) +{ + if ( **p == '!' ) + (*p)++; + while ( (**p >= 'A' && **p <= 'F') || (**p >= '0' && **p <= '9') ) + (*p)++; + if ( **p >= 'a' && **p <= 'z' ) // var + { + (*pnSupp)++; + return 0; + } + if ( **p == '(' ) // and + { + unsigned Mask = 0; + int m, i, pSupps[8] = {0}, nParts = 0, nSimple = 0, nMints; + char * q = pStr + pMatches[ *p - pStr ]; + assert( *q == **p + 1 + (**p != '(') ); + for ( (*p)++; *p < q; (*p)++ ) + { + Mask |= Dau_DsdCheckDecAndExist_rec( pStr, p, pMatches, &pSupps[nParts] ); + nSimple += (pSupps[nParts] == 1); + *pnSupp += pSupps[nParts++]; + } + assert( *p == q ); + assert( nParts > 1 ); + if ( nSimple > 0 ) + { + nMints = (1 << nParts); + for ( m = 1; m < nMints; m++ ) + { + int Sum = 0; + for ( i = 0; i < nParts; i++ ) + if ( pSupps[i] > 1 && ((m >> i) & 1) ) + Sum += pSupps[i]; + assert( Sum <= 8 ); + if ( Sum >= 2 ) + for ( i = 0; i < nSimple; i++ ) + Mask |= (1 << (Sum + i)); + } + for ( i = 2; i < nSimple; i++ ) + Mask |= (1 << i); + } + return Mask; + } + if ( **p == '<' || **p == '{' || **p == '[' ) // mux/xor/nondec + { + int uSupp; + unsigned Mask = 0; + char * q = pStr + pMatches[ *p - pStr ]; + assert( *q == **p + 1 + (**p != '(') ); + for ( (*p)++; *p < q; (*p)++ ) + { + uSupp = 0; + Mask |= Dau_DsdCheckDecAndExist_rec( pStr, p, pMatches, &uSupp ); + *pnSupp += uSupp; + } + assert( *p == q ); + return Mask; + } + assert( 0 ); + return 0; +} +int Dau_DsdCheckDecAndExist( char * pDsd ) +{ + int nSupp = 0; + if ( pDsd[1] == 0 ) + return 1; + return Dau_DsdCheckDecAndExist_rec( pDsd, &pDsd, Dau_DsdComputeMatches(pDsd), &nSupp ); +} + +/**Function************************************************************* + + Synopsis [Performs additional check.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutPerformCheck75__( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +{ + char pDsdStr[1000]; + int fDerive = 0; + int nSizeNonDec, nDecExists, nDecAndExists; + static int Counter = 0; + Counter++; + if ( nLeaves < 6 ) + return 1; + assert( nLeaves <= 8 ); + if ( nLeaves < 8 && If_CutPerformCheck16( p, pTruth, nVars, nLeaves, "44" ) ) + return 1; + // check decomposability + nSizeNonDec = Dau_DsdDecompose( (word *)pTruth, nLeaves, 0, 0, pDsdStr ); +// printf( "Vars = %d %s", nLeaves, pDsdStr ); printf( "\n" ); +// Extra_PrintBinary( stdout, &nDecExists, 8 ); printf( "\n" ); +// Extra_PrintBinary( stdout, &nDecAndExists, 8 ); printf( "\n" ); + if ( nLeaves == 8 ) + { + if ( nSizeNonDec >= 5 ) + return 0; + nDecAndExists = Dau_DsdCheckDecAndExist( pDsdStr ); + if ( nDecAndExists & 0x10 ) // bit 4 + return 1; + else + return 0; + } + if ( nLeaves == 7 ) + { + extern void If_Dec7MinimumBase( word uTruth[2], int * pSupp, int nVarsAll, int * pnVars ); + word * pT = (word *)pTruth; + word pCof0[2], pCof1[2]; + int v, nVarsMin; + if ( nSizeNonDec < 5 ) + { + nDecExists = Dau_DsdCheckDecExist( pDsdStr ); + if ( nDecExists & 0x10 ) // bit 4 + return 1; + nDecAndExists = Dau_DsdCheckDecAndExist( pDsdStr ); + if ( nDecAndExists & 0x18 ) // bit 4, 3 + return 1; + } + // check cofactors + for ( v = 0; v < 7; v++ ) + { + pCof0[0] = pCof1[0] = pT[0]; + pCof0[1] = pCof1[1] = pT[1]; + Abc_TtCofactor0( pCof0, 2, v ); + Abc_TtCofactor1( pCof1, 2, v ); + if ( Abc_TtSupportSize(pCof0, 7) < 4 ) + { + If_Dec7MinimumBase( pCof1, NULL, 7, &nVarsMin ); + nSizeNonDec = Dau_DsdDecompose( pCof1, nVarsMin, 0, 0, pDsdStr ); + if ( nSizeNonDec >= 5 ) + continue; + nDecExists = Dau_DsdCheckDecExist( pDsdStr ); + if ( nDecExists & 0x18 ) // bit 4, 3 + return 1; + } + else if ( Abc_TtSupportSize(pCof1, 7) < 4 ) + { + If_Dec7MinimumBase( pCof0, NULL, 7, &nVarsMin ); + nSizeNonDec = Dau_DsdDecompose( pCof0, nVarsMin, 0, 0, pDsdStr ); + if ( nSizeNonDec >= 5 ) + continue; + nDecExists = Dau_DsdCheckDecExist( pDsdStr ); + if ( nDecExists & 0x18 ) // bit 4, 3 + return 1; + } + } + return 0; + } + if ( nLeaves == 6 ) + { + if ( nSizeNonDec < 5 ) + { + nDecExists = Dau_DsdCheckDecExist( pDsdStr ); + if ( nDecExists & 0x18 ) // bit 4, 3 + return 1; + nDecAndExists = Dau_DsdCheckDecAndExist( pDsdStr ); + if ( nDecAndExists & 0x1C ) // bit 4, 3, 2 + return 1; + } + return If_CutPerformCheck07( p, pTruth, nVars, nLeaves, pStr ); + } + assert( 0 ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Performs additional check.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutPerformCheck75( If_Man_t * p, unsigned * pTruth0, int nVars, int nLeaves, char * pStr ) +{ + word * pTruthW = (word *)pTruth0; + word pTruth[4] = { pTruthW[0], pTruthW[1], pTruthW[2], pTruthW[3] }; + assert( nLeaves <= 8 ); + Abc_TtMinimumBase( pTruth, NULL, nLeaves, &nLeaves ); + if ( nLeaves < 6 ) + return 1; +// if ( nLeaves < 8 && If_CutPerformCheck07( p, (unsigned *)pTruth, nVars, nLeaves, "44" ) ) + if ( nLeaves < 8 && If_CutPerformCheck16( p, (unsigned *)pTruth, nVars, nLeaves, "44" ) ) + return 1; + if ( p->pPars->fEnableCheck75 && nLeaves == 8 ) + { +// char pDsdStr[1000] = "(!(abd)!(c!([fe][gh])))"; + char pDsdStr[1000]; + int nSizeNonDec = Dau_DsdDecompose( (word *)pTruth, nLeaves, 0, 0, pDsdStr ); + if ( nSizeNonDec >= 5 ) + return 0; + if ( Dau_DsdCheckDecAndExist(pDsdStr) & 0x10 ) // bit 4 + return 1; + return 0; + } + if ( If_CutPerformCheck45( p, (unsigned *)pTruth, nVars, nLeaves, pStr ) ) + return 1; + if ( If_CutPerformCheck54( p, (unsigned *)pTruth, nVars, nLeaves, pStr ) ) + return 1; + return 0; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/map/if/module.make b/src/map/if/module.make index b7b08722..e80aa1c4 100644 --- a/src/map/if/module.make +++ b/src/map/if/module.make @@ -5,6 +5,7 @@ SRC += src/map/if/ifCom.c \ src/map/if/ifDec08.c \ src/map/if/ifDec10.c \ src/map/if/ifDec16.c \ + src/map/if/ifDec75.c \ src/map/if/ifLibBox.c \ src/map/if/ifLibLut.c \ src/map/if/ifMan.c \ |