summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/map/if/if.h17
-rw-r--r--src/map/if/ifDec07.c2
-rw-r--r--src/map/if/ifDec08.c2
-rw-r--r--src/map/if/ifDec10.c2
-rw-r--r--src/map/if/ifDec16.c81
-rw-r--r--src/map/if/ifMan.c6
-rw-r--r--src/map/if/ifMap.c2
7 files changed, 90 insertions, 22 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h
index 295491c5..a42c1d79 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -121,7 +121,7 @@ struct If_Par_t_
float * pTimesReq; // required times
int (* pFuncCost) (If_Cut_t *); // procedure to compute the user's cost of a cut
int (* pFuncUser) (If_Man_t *, If_Obj_t *, If_Cut_t *); // procedure called for each cut when cut computation is finished
- int (* pFuncCell) (unsigned *, int, int, char *); // procedure called for cut functions
+ int (* pFuncCell) (If_Man_t *, unsigned *, int, int, char *); // procedure called for cut functions
void * pReoMan; // reordering manager
};
@@ -191,6 +191,13 @@ struct If_Man_t_
// timing manager
Tim_Man_t * pManTim;
Vec_Int_t * vCoAttrs; // CO attributes 0=optimize; 1=keep; 2=relax
+ // hash table for functions
+ int nTableSize; // hash table size
+ int nTableEntries; // hash table entries
+ void ** pHashTable; // hash table bins
+ Mem_Fixed_t * pMemEntries; // memory manager for hash table entries
+
+
// statistics
// int timeTruth;
};
@@ -416,10 +423,10 @@ extern float If_CutPowerRef( If_Man_t * p, If_Cut_t * pCut, If_Obj_t *
extern float If_CutPowerDerefed( If_Man_t * p, If_Cut_t * pCut, If_Obj_t * pRoot );
extern float If_CutPowerRefed( If_Man_t * p, If_Cut_t * pCut, If_Obj_t * pRoot );
/*=== ifDec.c =============================================================*/
-extern int If_CutPerformCheck07( unsigned * pTruth, int nVars, int nLeaves, char * pStr );
-extern int If_CutPerformCheck08( unsigned * pTruth, int nVars, int nLeaves, char * pStr );
-extern int If_CutPerformCheck10( unsigned * pTruth, int nVars, int nLeaves, char * pStr );
-extern int If_CutPerformCheck16( unsigned * pTruth, int nVars, int nLeaves, char * pStr );
+extern int If_CutPerformCheck07( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr );
+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 float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float WireDelay );
/*=== ifLib.c =============================================================*/
extern If_Lib_t * If_LutLibRead( char * FileName );
diff --git a/src/map/if/ifDec07.c b/src/map/if/ifDec07.c
index b10ddeb8..41949a2f 100644
--- a/src/map/if/ifDec07.c
+++ b/src/map/if/ifDec07.c
@@ -673,7 +673,7 @@ int If_Dec7PickBestMux( word t[2], word c0r[2], word c1r[2] )
SeeAlso []
***********************************************************************/
-int If_CutPerformCheck07( unsigned * pTruth, int nVars, int nLeaves, char * pStr )
+int If_CutPerformCheck07( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr )
{
int fDerive = 0;
if ( nLeaves < 6 )
diff --git a/src/map/if/ifDec08.c b/src/map/if/ifDec08.c
index 53aa9ff1..06081414 100644
--- a/src/map/if/ifDec08.c
+++ b/src/map/if/ifDec08.c
@@ -478,7 +478,7 @@ printf( "\n" );
SeeAlso []
***********************************************************************/
-int If_CutPerformCheck08( unsigned * pTruth, int nVars, int nLeaves, char * pStr )
+int If_CutPerformCheck08( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr )
{
int nSupp, fDerive = 0;
word z[2] = {0}, pF[16];
diff --git a/src/map/if/ifDec10.c b/src/map/if/ifDec10.c
index 37846140..9280e193 100644
--- a/src/map/if/ifDec10.c
+++ b/src/map/if/ifDec10.c
@@ -477,7 +477,7 @@ printf( "\n" );
SeeAlso []
***********************************************************************/
-int If_CutPerformCheck10( unsigned * pTruth, int nVars, int nLeaves, char * pStr )
+int If_CutPerformCheck10( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr )
{
int nSupp, fDerive = 0;
word z[2] = {0}, pF[16];
diff --git a/src/map/if/ifDec16.c b/src/map/if/ifDec16.c
index 3902f053..a6d0edee 100644
--- a/src/map/if/ifDec16.c
+++ b/src/map/if/ifDec16.c
@@ -29,14 +29,24 @@ ABC_NAMESPACE_IMPL_START
#define CLU_VAR_MAX 16
#define CLU_WRD_MAX (1 << ((CLU_VAR_MAX)-6))
+#define CLU_UNUSED 99
// decomposition
typedef struct If_Grp_t_ If_Grp_t;
struct If_Grp_t_
{
- char nVars;
- char nMyu;
- char pVars[CLU_VAR_MAX];
+ char nVars;
+ char nMyu;
+ char pVars[CLU_VAR_MAX];
+};
+
+// hash table entry
+typedef struct If_Hte_t_ If_Hte_t;
+struct If_Hte_t_
+{
+ If_Hte_t * pNext;
+ If_Grp_t Group;
+ word pTruth[1];
};
// the bit count for the first 256 integer numbers
@@ -77,11 +87,51 @@ extern void Extra_PrintBinary( FILE * pFile, unsigned Sign[], int nBits );
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
-// variable permutation for large functions
+// hash table
static inline int If_CluWordNum( int nVars )
{
return nVars <= 6 ? 1 : 1 << (nVars-6);
}
+int If_CluHashKey( word * pTruth, int nWords, int Size )
+{
+ static unsigned BigPrimes[8] = {12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
+ unsigned char * s = (unsigned char *)pTruth;
+ unsigned Value = 0;
+ int i;
+ for ( i = 0; i < 8 * nWords; i++ )
+ Value ^= BigPrimes[i % 7] * s[i];
+ return Value % Size;
+}
+If_Grp_t * If_CluHashLookup( If_Man_t * p, word * pTruth )
+{
+ If_Hte_t * pEntry;
+ int nWords, HashKey;
+ if ( p == NULL )
+ return NULL;
+ nWords = If_CluWordNum(p->pPars->nLutSize);
+ if ( p->pMemEntries == NULL )
+ {
+ p->pMemEntries = Mem_FixedStart( sizeof(If_Hte_t) + sizeof(word) * (If_CluWordNum(p->pPars->nLutSize) - 1) );
+ p->nTableSize = Vec_PtrSize(p->vObjs) * p->pPars->nCutsMax;
+ p->pHashTable = ABC_CALLOC( void *, p->nTableSize );
+ }
+ // check if this entry exists
+ HashKey = If_CluHashKey( pTruth, nWords, p->nTableSize );
+ for ( pEntry = ((If_Hte_t **)p->pHashTable)[HashKey]; pEntry; pEntry = pEntry->pNext )
+ if ( memcmp(pEntry->pTruth, pTruth, sizeof(word) * nWords) == 0 )
+ return &pEntry->Group;
+ // create entry
+ p->nTableEntries++;
+ pEntry = (If_Hte_t *)Mem_FixedEntryFetch( p->pMemEntries );
+ memcpy( pEntry->pTruth, pTruth, sizeof(word) * nWords );
+ memset( &pEntry->Group, 0, sizeof(If_Grp_t) );
+ pEntry->Group.nVars = CLU_UNUSED;
+ pEntry->pNext = ((If_Hte_t **)p->pHashTable)[HashKey];
+ ((If_Hte_t **)p->pHashTable)[HashKey] = pEntry;
+ return &pEntry->Group;
+}
+
+// variable permutation for large functions
static inline void If_CluClear( word * pIn, int nVars )
{
int w, nWords = If_CluWordNum( nVars );
@@ -848,9 +898,9 @@ static inline int If_CluSupport( word * t, int nVars )
}
// returns the best group found
-If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot )
+If_Grp_t If_CluCheck( If_Man_t * p, word * pTruth, int nVars, int nLutLeaf, int nLutRoot )
{
- If_Grp_t G1 = {0}, R = {0};
+ If_Grp_t G1 = {0}, R = {0}, * pHashed = NULL;
word Truth, pF[CLU_WRD_MAX];//, pG[CLU_WRD_MAX];
int V2P[CLU_VAR_MAX+2], P2V[CLU_VAR_MAX+2];
int i, nSupp;
@@ -879,6 +929,11 @@ If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot )
if ( !nSupp || !If_CluSuppIsMinBase(nSupp) )
return G1;
+ // check hash table
+ pHashed = If_CluHashLookup( p, pTruth );
+ if ( pHashed && pHashed->nVars != CLU_UNUSED )
+ return *pHashed;
+
// detect easy cofs
G1 = If_CluDecUsingCofs( pTruth, nVars, nLutLeaf );
if ( G1.nVars == 0 )
@@ -914,7 +969,7 @@ If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot )
printf( "no\n" );
}
*/
- return G1;
+ return pHashed ? (*pHashed = G1) : G1;
}
}
}
@@ -936,7 +991,7 @@ If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot )
If_CluVerify( pTruth, nVars, &G1, &R, Truth, pF );
}
}
- return G1;
+ return pHashed ? (*pHashed = G1) : G1;
}
@@ -1003,7 +1058,7 @@ float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float Wi
}
// derive the first group
- G1 = If_CluCheck( (word *)If_CutTruth(pCut), nLeaves, nLutLeaf, nLutRoot );
+ G1 = If_CluCheck( p, (word *)If_CutTruth(pCut), nLeaves, nLutLeaf, nLutRoot );
if ( G1.nVars == 0 )
return ABC_INFINITY;
@@ -1053,7 +1108,7 @@ float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float Wi
SeeAlso []
***********************************************************************/
-int If_CutPerformCheck16( unsigned * pTruth, int nVars, int nLeaves, char * pStr )
+int If_CutPerformCheck16( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr )
{
If_Grp_t G1 = {0}, G2 = {0}, G3 = {0};
int nLutLeaf, nLutRoot;
@@ -1086,7 +1141,7 @@ int If_CutPerformCheck16( unsigned * pTruth, int nVars, int nLeaves, char * pStr
return 1;
// derive the first group
- G1 = If_CluCheck( (word *)pTruth, nLeaves, nLutLeaf, nLutRoot );
+ G1 = If_CluCheck( p, (word *)pTruth, nLeaves, nLutLeaf, nLutRoot );
if ( G1.nVars == 0 )
{
// printf( "-%d ", nLeaves );
@@ -1116,12 +1171,12 @@ void If_CluTest()
return;
- If_CutPerformCheck07( (unsigned *)&t, 6, 6, NULL );
+ If_CutPerformCheck07( NULL, (unsigned *)&t, 6, 6, NULL );
// return;
Kit_DsdPrintFromTruth( (unsigned*)&t, nVars ); printf( "\n" );
- G = If_CluCheck( &t, nVars, nLutLeaf, nLutRoot );
+ G = If_CluCheck( NULL, &t, nVars, nLutLeaf, nLutRoot );
If_CluPrintGroup( &G );
}
diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c
index ba8f4e0c..8ea579c4 100644
--- a/src/map/if/ifMan.c
+++ b/src/map/if/ifMan.c
@@ -160,6 +160,12 @@ void If_ManStop( If_Man_t * p )
Tim_ManStop( p->pManTim );
if ( p->vSwitching )
Vec_IntFree( p->vSwitching );
+ // hash table
+// if ( p->nTableEntries )
+// printf( "Entries = %d. Size = %d.\n", p->nTableEntries, p->nTableSize );
+ ABC_FREE( p->pHashTable );
+ if ( p->pMemEntries )
+ Mem_FixedStop( p->pMemEntries, 0 );
ABC_FREE( p );
}
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
index eb7f69b9..55d93884 100644
--- a/src/map/if/ifMap.c
+++ b/src/map/if/ifMap.c
@@ -207,7 +207,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep
if ( p->pPars->pFuncCell && RetValue < 2 )
{
assert( pCut->nLimit >= 4 && pCut->nLimit <= 16 );
- pCut->fUseless = !p->pPars->pFuncCell( If_CutTruth(pCut), pCut->nLimit, pCut->nLeaves, p->pPars->pLutStruct );
+ pCut->fUseless = !p->pPars->pFuncCell( p, If_CutTruth(pCut), pCut->nLimit, pCut->nLeaves, p->pPars->pLutStruct );
p->nCutsUselessAll += pCut->fUseless;
p->nCutsUseless[pCut->nLeaves] += pCut->fUseless;
p->nCutsCountAll++;
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 22:32:19 +0000