summaryrefslogtreecommitdiffstats
path: root/src/map/if
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/if')
-rw-r--r--src/map/if/if.h5
-rw-r--r--src/map/if/ifCut.c2
-rw-r--r--src/map/if/ifDec07.c2
-rw-r--r--src/map/if/ifDec16.c127
-rw-r--r--src/map/if/ifDec75.c341
-rw-r--r--src/map/if/module.make1
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 \
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-09 06:46:27 +0000