summaryrefslogtreecommitdiffstats
path: root/src/opt/lpk
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt/lpk')
-rw-r--r--src/opt/lpk/lpkAbcDec.c132
-rw-r--r--src/opt/lpk/lpkAbcDsd.c129
-rw-r--r--src/opt/lpk/lpkAbcMux.c123
-rw-r--r--src/opt/lpk/lpkAbcUtil.c16
-rw-r--r--src/opt/lpk/lpkCore.c11
-rw-r--r--src/opt/lpk/lpkCut.c9
-rw-r--r--src/opt/lpk/lpkInt.h16
-rw-r--r--src/opt/lpk/lpkMux.c3
8 files changed, 284 insertions, 155 deletions
diff --git a/src/opt/lpk/lpkAbcDec.c b/src/opt/lpk/lpkAbcDec.c
index 831097b0..e9f8d0df 100644
--- a/src/opt/lpk/lpkAbcDec.c
+++ b/src/opt/lpk/lpkAbcDec.c
@@ -17,7 +17,7 @@
Revision [$Id: lpkAbcDec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
***********************************************************************/
-
+
#include "lpkInt.h"
////////////////////////////////////////////////////////////////////////
@@ -41,24 +41,29 @@
***********************************************************************/
Abc_Obj_t * Lpk_ImplementFun( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * p )
{
+ extern Hop_Obj_t * Kit_TruthToHop( Hop_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory );
+ unsigned * pTruth;
Abc_Obj_t * pObjNew;
int i;
+ // create the new node
pObjNew = Abc_NtkCreateNode( pNtk );
for ( i = 0; i < (int)p->nVars; i++ )
Abc_ObjAddFanin( pObjNew, Vec_PtrEntry(vLeaves, p->pFanins[i]) );
Abc_ObjLevelNew( pObjNew );
- // create the logic function
+ // assign the node's function
+ pTruth = Lpk_FunTruth(p, 0);
+ if ( p->nVars == 0 )
{
- extern Hop_Obj_t * Kit_GraphToHop( Hop_Man_t * pMan, Kit_Graph_t * pGraph );
- // allocate memory for the ISOP
- Vec_Int_t * vCover = Vec_IntAlloc( 0 );
- // transform truth table into the decomposition tree
- Kit_Graph_t * pGraph = Kit_TruthToGraph( Lpk_FunTruth(p, 0), p->nVars, vCover );
- // derive the AIG for the decomposition tree
- pObjNew->pData = Kit_GraphToHop( pNtk->pManFunc, pGraph );
- Kit_GraphFree( pGraph );
- Vec_IntFree( vCover );
+ pObjNew->pData = Hop_NotCond( Hop_ManConst1(pNtk->pManFunc), !(pTruth[0] & 1) );
+ return pObjNew;
}
+ if ( p->nVars == 1 )
+ {
+ pObjNew->pData = Hop_NotCond( Hop_ManPi(pNtk->pManFunc, 0), (pTruth[0] & 1) );
+ return pObjNew;
+ }
+ // create the logic function
+ pObjNew->pData = Kit_TruthToHop( pNtk->pManFunc, pTruth, p->nVars, NULL );
return pObjNew;
}
@@ -85,6 +90,7 @@ Abc_Obj_t * Lpk_Implement( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld
Vec_PtrWriteEntry( vLeaves, i, pRes );
Lpk_FunFree( pFun );
}
+ Vec_PtrShrink( vLeaves, nLeavesOld );
return pRes;
}
@@ -92,7 +98,9 @@ Abc_Obj_t * Lpk_Implement( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld
Synopsis [Decomposes the function using recursive MUX decomposition.]
- Description []
+ Description [Returns the ID of the top-most decomposition node
+ implementing this function, or 0 if there is no decomposition satisfying
+ the constraints on area and delay.]
SideEffects []
@@ -101,22 +109,78 @@ Abc_Obj_t * Lpk_Implement( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld
***********************************************************************/
int Lpk_Decompose_rec( Lpk_Fun_t * p )
{
+ Lpk_Res_t * pResMux, * pResDsd;
Lpk_Fun_t * p2;
- int VarPol;
- assert( p->nAreaLim > 0 );
- if ( p->nVars <= p->nLutK )
- return 1;
- // check if decomposition exists
- VarPol = Lpk_MuxAnalize( p );
- if ( VarPol == -1 )
+ // is only called for non-trivial blocks
+ assert( p->nLutK >= 3 && p->nLutK <= 6 );
+ assert( p->nVars > p->nLutK );
+ // skip if area bound is exceeded
+ if ( Lpk_LutNumLuts(p->nVars, p->nLutK) > (int)p->nAreaLim )
return 0;
- // split and call recursively
- p2 = Lpk_MuxSplit( p, VarPol );
- if ( !Lpk_Decompose_rec( p2 ) )
+ // skip if delay bound is exceeded
+ if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim )
return 0;
- return Lpk_Decompose_rec( p );
+ // check MUX decomposition
+ pResMux = Lpk_MuxAnalize( p );
+ assert( !pResMux || (pResMux->DelayEst <= (int)p->nDelayLim && pResMux->AreaEst <= (int)p->nAreaLim) );
+ // accept MUX decomposition if it is "good"
+ if ( pResMux && pResMux->nSuppSizeS <= (int)p->nLutK && pResMux->nSuppSizeL <= (int)p->nLutK )
+ pResDsd = NULL;
+ else
+ {
+ pResDsd = Lpk_DsdAnalize( p );
+ assert( !pResDsd || (pResDsd->DelayEst <= (int)p->nDelayLim && pResDsd->AreaEst <= (int)p->nAreaLim) );
+ }
+ if ( pResMux && pResDsd )
+ {
+ // compare two decompositions
+ if ( pResMux->AreaEst < pResDsd->AreaEst ||
+ (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL < pResDsd->nSuppSizeL) ||
+ (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL == pResDsd->nSuppSizeL && pResMux->DelayEst < pResDsd->DelayEst) )
+ pResDsd = NULL;
+ else
+ pResMux = NULL;
+ }
+ assert( pResMux == NULL || pResDsd == NULL );
+ if ( pResMux )
+ {
+ p2 = Lpk_MuxSplit( p, pResMux->pCofVars[0], pResMux->Polarity );
+ if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( p2 ) )
+ return 0;
+ if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( p ) )
+ return 0;
+ return 1;
+ }
+ if ( pResDsd )
+ {
+ p2 = Lpk_DsdSplit( p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
+ assert( p2->nVars <= (int)p->nLutK );
+ if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( p ) )
+ return 0;
+ return 1;
+ }
+ return 0;
}
+/**Function*************************************************************
+
+ Synopsis [Removes decomposed nodes from the array of fanins.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Lpk_DecomposeClean( Vec_Ptr_t * vLeaves, int nLeavesOld )
+{
+ Lpk_Fun_t * pFunc;
+ int i;
+ Vec_PtrForEachEntryStart( vLeaves, pFunc, i, nLeavesOld )
+ Lpk_FunFree( pFunc );
+ Vec_PtrShrink( vLeaves, nLeavesOld );
+}
/**Function*************************************************************
@@ -131,22 +195,16 @@ int Lpk_Decompose_rec( Lpk_Fun_t * p )
***********************************************************************/
Abc_Obj_t * Lpk_Decompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim )
{
- Lpk_Fun_t * p;
+ Lpk_Fun_t * pFun;
Abc_Obj_t * pObjNew = NULL;
- int i, nLeaves;
- // create the starting function
- nLeaves = Vec_PtrSize( vLeaves );
- p = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim );
- Lpk_FunSuppMinimize( p );
- // decompose the function
- if ( Lpk_Decompose_rec(p) )
+ int nLeaves = Vec_PtrSize( vLeaves );
+ pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim );
+ Lpk_FunSuppMinimize( pFun );
+ if ( pFun->nVars <= pFun->nLutK )
+ pObjNew = Lpk_ImplementFun( pNtk, vLeaves, pFun );
+ else if ( Lpk_Decompose_rec(pFun) )
pObjNew = Lpk_Implement( pNtk, vLeaves, nLeaves );
- else
- {
- for ( i = Vec_PtrSize(vLeaves) - 1; i >= nLeaves; i-- )
- Lpk_FunFree( Vec_PtrEntry(vLeaves, i) );
- }
- Vec_PtrShrink( vLeaves, nLeaves );
+ Lpk_DecomposeClean( vLeaves, nLeaves );
return pObjNew;
}
diff --git a/src/opt/lpk/lpkAbcDsd.c b/src/opt/lpk/lpkAbcDsd.c
index 8de8391f..f2e19945 100644
--- a/src/opt/lpk/lpkAbcDsd.c
+++ b/src/opt/lpk/lpkAbcDsd.c
@@ -30,9 +30,11 @@
/**Function*************************************************************
- Synopsis [Returns the variable whose cofs have min sum of supp sizes.]
+ Synopsis [Cofactors TTs w.r.t. all vars and finds the best var.]
- Description []
+ Description [The best variable is the variable with the minimum
+ sum total of the support sizes of all truth tables. This procedure
+ computes and returns cofactors w.r.t. the best variable.]
SideEffects []
@@ -42,6 +44,7 @@
int Lpk_FunComputeMinSuppSizeVar( Lpk_Fun_t * p, unsigned ** ppTruths, int nTruths, unsigned ** ppCofs )
{
int i, Var, VarBest, nSuppSize0, nSuppSize1, nSuppTotalMin, nSuppTotalCur, nSuppMaxMin, nSuppMaxCur;
+ assert( nTruths > 0 );
VarBest = -1;
Lpk_SuppForEachVar( p->uSupp, Var )
{
@@ -85,7 +88,7 @@ int Lpk_FunComputeMinSuppSizeVar( Lpk_Fun_t * p, unsigned ** ppTruths, int nTrut
SeeAlso []
***********************************************************************/
-unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets )
+unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets, int nSizeMax )
{
unsigned i, iLitFanin, uSupport, uSuppCur;
Kit_DsdObj_t * pObj;
@@ -99,7 +102,7 @@ unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets
uSupport = 0;
Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i )
{
- uSupps[i] = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets );
+ uSupps[i] = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets, nSizeMax );
uSupport |= uSupps[i];
}
// create all subsets, except empty and full
@@ -110,7 +113,8 @@ unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets
for ( i = 0; i < pObj->nFans; i++ )
if ( s & (1 << i) )
uSuppCur |= uSupps[i];
- Vec_IntPush( vSets, uSuppCur );
+ if ( Kit_WordCountOnes(uSuppCur) <= nSizeMax )
+ Vec_IntPush( vSets, uSuppCur );
}
return uSupport;
}
@@ -119,9 +123,10 @@ unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets
uSupport = 0;
Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i )
{
- uSuppCur = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets );
+ uSuppCur = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets, nSizeMax );
uSupport |= uSuppCur;
- Vec_IntPush( vSets, uSuppCur );
+ if ( Kit_WordCountOnes(uSuppCur) <= nSizeMax )
+ Vec_IntPush( vSets, uSuppCur );
}
return uSupport;
}
@@ -150,12 +155,15 @@ Vec_Int_t * Lpk_ComputeBoundSets( Kit_DsdNtk_t * p, int nSizeMax )
if ( Kit_DsdNtkRoot(p)->Type == KIT_DSD_VAR )
{
uSupport = ( 1 << Kit_DsdLit2Var(Kit_DsdNtkRoot(p)->pFans[0]) );
- Vec_IntPush( vSets, uSupport );
+ if ( Kit_WordCountOnes(uSupport) <= nSizeMax )
+ Vec_IntPush( vSets, uSupport );
return vSets;
}
- uSupport = Lpk_ComputeBoundSets_rec( p, p->Root, vSets );
+ uSupport = Lpk_ComputeBoundSets_rec( p, p->Root, vSets, nSizeMax );
assert( (uSupport & 0xFFFF0000) == 0 );
- Vec_IntPush( vSets, uSupport );
+ // add the total support of the network
+ if ( Kit_WordCountOnes(uSupport) <= nSizeMax )
+ Vec_IntPush( vSets, uSupport );
// set the remaining variables
Vec_IntForEachEntry( vSets, Number, i )
{
@@ -176,7 +184,7 @@ Vec_Int_t * Lpk_ComputeBoundSets( Kit_DsdNtk_t * p, int nSizeMax )
SeeAlso []
***********************************************************************/
-Vec_Int_t * Lpk_MergeBoundSets( Vec_Int_t * vSets0, Vec_Int_t * vSets1 )
+Vec_Int_t * Lpk_MergeBoundSets( Vec_Int_t * vSets0, Vec_Int_t * vSets1, int nSizeMax )
{
Vec_Int_t * vSets;
int Entry0, Entry1, Entry;
@@ -188,7 +196,8 @@ Vec_Int_t * Lpk_MergeBoundSets( Vec_Int_t * vSets0, Vec_Int_t * vSets1 )
Entry = Entry0 | Entry1;
if ( (Entry & (Entry >> 16)) )
continue;
- Vec_IntPush( vSets, Entry );
+ if ( Kit_WordCountOnes(Entry) <= nSizeMax )
+ Vec_IntPush( vSets, Entry );
}
return vSets;
}
@@ -266,14 +275,15 @@ void Lpk_FunFreeTruthTables( Lpk_Fun_t * p, int nCofDepth, unsigned * ppTruths[5
SeeAlso []
***********************************************************************/
-Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth )
+void Lpk_DsdAnalizeOne( Lpk_Fun_t * p, int nCofDepth, Lpk_Res_t * pRes )
{
- static Lpk_Res_t Res, * pRes = &Res;
unsigned * ppTruths[5][16];
Vec_Int_t * pvBSets[4][8];
Kit_DsdNtk_t * pNtkDec, * pTemp;
unsigned uBoundSet;
int i, k, nVarsBS, nVarsRem, Delay, Area;
+ assert( nCofDepth >= 0 && nCofDepth < 4 );
+ assert( nCofDepth < (int)p->nLutK - 1 );
Lpk_FunAllocTruthTables( p, nCofDepth, ppTruths );
// find the best cofactors
memset( pRes, 0, sizeof(Lpk_Res_t) );
@@ -291,7 +301,7 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth )
// derive the set of feasible boundsets
for ( i = nCofDepth - 1; i >= 0; i-- )
for ( k = 0; k < (1<<i); k++ )
- pvBSets[i][k] = Lpk_MergeBoundSets( pvBSets[i+1][2*k+0], pvBSets[i+1][2*k+1] );
+ pvBSets[i][k] = Lpk_MergeBoundSets( pvBSets[i+1][2*k+0], pvBSets[i+1][2*k+1], p->nLutK - nCofDepth );
// compare the resulting boundsets
Vec_IntForEachEntry( pvBSets[0][0], uBoundSet, i )
{
@@ -299,12 +309,13 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth )
continue;
assert( (uBoundSet & (uBoundSet >> 16)) == 0 );
nVarsBS = Kit_WordCountOnes( uBoundSet & 0xFFFF );
+ assert( nVarsBS <= (int)p->nLutK - nCofDepth );
nVarsRem = p->nVars - nVarsBS + nCofDepth + 1;
- Delay = 1 + Lpk_SuppDelay( uBoundSet & 0xFFFF, p->pDelays );
Area = 1 + Lpk_LutNumLuts( nVarsRem, p->nLutK );
- if ( Delay > (int)p->nDelayLim || Area > (int)p->nAreaLim )
+ Delay = 1 + Lpk_SuppDelay( uBoundSet & 0xFFFF, p->pDelays );
+ if ( Area > (int)p->nAreaLim || Delay > (int)p->nDelayLim )
continue;
- if ( uBoundSet == 0 || pRes->DelayEst > Delay || pRes->DelayEst == Delay && pRes->nSuppSizeL > nVarsRem )
+ if ( pRes->BSVars == 0 || pRes->DelayEst > Delay || pRes->DelayEst == Delay && pRes->nSuppSizeL > nVarsRem )
{
pRes->nBSVars = nVarsBS;
pRes->BSVars = uBoundSet;
@@ -316,7 +327,60 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth )
}
// free cofactor storage
Lpk_FunFreeTruthTables( p, nCofDepth, ppTruths );
- return pRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs DSD-based decomposition of the function.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p )
+{
+ static Lpk_Res_t Res0, * pRes0 = &Res0;
+ static Lpk_Res_t Res1, * pRes1 = &Res1;
+ static Lpk_Res_t Res2, * pRes2 = &Res2;
+ static Lpk_Res_t Res3, * pRes3 = &Res3;
+ memset( pRes0, 0, sizeof(Lpk_Res_t) );
+ memset( pRes1, 0, sizeof(Lpk_Res_t) );
+ memset( pRes2, 0, sizeof(Lpk_Res_t) );
+ memset( pRes3, 0, sizeof(Lpk_Res_t) );
+ assert( p->uSupp == Kit_BitMask(p->nVars) );
+
+ // try decomposition without cofactoring
+ Lpk_DsdAnalizeOne( p, 0, pRes0 );
+ if ( pRes0->nBSVars == (int)p->nLutK && pRes0->AreaEst <= (int)p->nAreaLim && pRes0->DelayEst <= (int)p->nDelayLim )
+ return pRes0;
+
+ // cofactor 1 time
+ if ( p->nLutK >= 3 )
+ Lpk_DsdAnalizeOne( p, 1, pRes1 );
+ assert( pRes1->nBSVars <= (int)p->nLutK - 1 );
+ if ( pRes1->nBSVars == (int)p->nLutK - 1 && pRes1->AreaEst <= (int)p->nAreaLim && pRes1->DelayEst <= (int)p->nDelayLim )
+ return pRes1;
+
+ // cofactor 2 times
+ if ( p->nLutK >= 4 )
+ Lpk_DsdAnalizeOne( p, 2, pRes2 );
+ assert( pRes2->nBSVars <= (int)p->nLutK - 2 );
+ if ( pRes2->nBSVars == (int)p->nLutK - 2 && pRes2->AreaEst <= (int)p->nAreaLim && pRes2->DelayEst <= (int)p->nDelayLim )
+ return pRes2;
+
+ // cofactor 3 times
+ if ( p->nLutK >= 5 )
+ Lpk_DsdAnalizeOne( p, 3, pRes3 );
+ assert( pRes3->nBSVars <= (int)p->nLutK - 3 );
+ if ( pRes3->nBSVars == (int)p->nLutK - 3 && pRes3->AreaEst <= (int)p->nAreaLim && pRes3->DelayEst <= (int)p->nDelayLim )
+ return pRes3;
+
+ // choose the best under these conditions
+
+ return NULL;
}
/**Function*************************************************************
@@ -332,19 +396,21 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth )
***********************************************************************/
Lpk_Fun_t * Lpk_DsdSplit( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet )
{
+ Lpk_Fun_t * pNew;
Kit_DsdMan_t * pDsdMan;
Kit_DsdNtk_t * pNtkDec, * pTemp;
unsigned * pTruth = Lpk_FunTruth( p, 0 );
unsigned * pTruth0 = Lpk_FunTruth( p, 1 );
unsigned * pTruth1 = Lpk_FunTruth( p, 2 );
- Lpk_Fun_t * pNew;
unsigned * ppTruths[5][16];
char pBSVars[5];
- int i, k, nVars, nCofs;
+ int i, k, nVars, iVacVar, nCofs;
// get the bound set variables
nVars = Lpk_SuppToVars( uBoundSet, pBSVars );
+ // get the vacuous variable
+ iVacVar = pBSVars[0];
// compute the cofactors
- Lpk_FunAllocTruthTables( p, nCofVars, ppTruths );
+ Lpk_FunAllocTruthTables( p, nCofVars + 1, ppTruths );
for ( i = 0; i < nCofVars; i++ )
for ( k = 0; k < (1<<i); k++ )
{
@@ -353,38 +419,37 @@ Lpk_Fun_t * Lpk_DsdSplit( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned
}
// decompose each cofactor w.r.t. the bound set
nCofs = (1<<nCofVars);
- pDsdMan = Kit_DsdManAlloc( p->nVars, p->nVars * 4 );
+ pDsdMan = Kit_DsdManAlloc( p->nVars, p->nVars * 2 );
for ( k = 0; k < nCofs; k++ )
{
pNtkDec = Kit_DsdDecompose( ppTruths[nCofVars][k], p->nVars );
pNtkDec = Kit_DsdExpand( pTemp = pNtkDec ); Kit_DsdNtkFree( pTemp );
- Kit_DsdTruthPartialTwo( pDsdMan, pNtkDec, uBoundSet, pBSVars[0], ppTruths[nCofVars+1][k], ppTruths[nCofVars+1][nCofs+k] );
+ Kit_DsdTruthPartialTwo( pDsdMan, pNtkDec, uBoundSet, iVacVar, ppTruths[nCofVars+1][k], ppTruths[nCofVars+1][nCofs+k] );
Kit_DsdNtkFree( pNtkDec );
}
Kit_DsdManFree( pDsdMan );
- // compute the composition function
- for ( i = nCofVars - 1; i >= 1; i-- )
+ // compute the composition/decomposition functions (they will be in pTruth0/pTruth1)
+ for ( i = nCofVars; i >= 1; i-- )
for ( k = 0; k < (1<<i); k++ )
- Kit_TruthMuxVar( ppTruths[i][k], ppTruths[i+1][2*k+0], ppTruths[i+1][2*k+1], nVars, pCofVars[i] );
- // now the composition/decomposition functions are in pTruth0/pTruth1
+ Kit_TruthMuxVar( ppTruths[i][k], ppTruths[i+1][2*k+0], ppTruths[i+1][2*k+1], nVars, pCofVars[i-1] );
// derive the new component
pNew = Lpk_FunDup( p, pTruth1 );
// update the old component
Kit_TruthCopy( pTruth, pTruth0, p->nVars );
p->uSupp = Kit_TruthSupport( pTruth0, p->nVars );
- p->pFanins[pBSVars[0]] = pNew->Id;
- p->pDelays[pBSVars[0]] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays );
+ p->pFanins[iVacVar] = pNew->Id;
+ p->pDelays[iVacVar] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays );
// support minimize both
Lpk_FunSuppMinimize( p );
Lpk_FunSuppMinimize( pNew );
// update delay and area requirements
- pNew->nDelayLim = p->nDelayLim - 1;
+ pNew->nDelayLim = p->pDelays[iVacVar];
pNew->nAreaLim = 1;
p->nAreaLim = p->nAreaLim - 1;
// free cofactor storage
- Lpk_FunFreeTruthTables( p, nCofVars, ppTruths );
+ Lpk_FunFreeTruthTables( p, nCofVars + 1, ppTruths );
return pNew;
}
diff --git a/src/opt/lpk/lpkAbcMux.c b/src/opt/lpk/lpkAbcMux.c
index 6549e175..159cae96 100644
--- a/src/opt/lpk/lpkAbcMux.c
+++ b/src/opt/lpk/lpkAbcMux.c
@@ -48,7 +48,6 @@ void Lpk_FunComputeCofs( Lpk_Fun_t * p, int iVar )
Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, iVar );
}
-
/**Function*************************************************************
Synopsis [Computes cofactors w.r.t. each variable.]
@@ -85,18 +84,18 @@ void Lpk_FunComputeCofSupps( Lpk_Fun_t * p, unsigned * puSupps )
SeeAlso []
***********************************************************************/
-int Lpk_MuxAnalize( Lpk_Fun_t * p )
+Lpk_Res_t * Lpk_MuxAnalize( Lpk_Fun_t * p )
{
- unsigned puSupps[32] = {0};
- int nSuppSize0, nSuppSize1, Delay, Delay0, Delay1, DelayA, DelayB;
- int Var, Area, Polarity, VarBest, AreaBest, PolarityBest, nSuppSizeBest;
-
- if ( p->nVars > p->nAreaLim * (p->nLutK - 1) + 1 )
- return -1;
+ static Lpk_Res_t Res, * pRes = &Res;
+ unsigned puSupps[32];
+ int nSuppSize0, nSuppSize1, nSuppSizeBest;
+ int Var, Area, Polarity, Delay, Delay0, Delay1, DelayA, DelayB;
+ memset( pRes, 0, sizeof(Lpk_Res_t) );
+ assert( p->uSupp == Kit_BitMask(p->nVars) );
// get cofactor supports for each variable
Lpk_FunComputeCofSupps( p, puSupps );
- // derive the delay and area of each MUX-decomposition
- VarBest = -1;
+ // derive the delay and area after MUX-decomp with each var - and find the best var
+ pRes->Variable = -1;
Lpk_SuppForEachVar( p->uSupp, Var )
{
nSuppSize0 = Kit_WordCountOnes(puSupps[2*Var+0]);
@@ -124,20 +123,20 @@ int Lpk_MuxAnalize( Lpk_Fun_t * p )
Area = 1 + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
Polarity = 0;
}
- else if ( nSuppSize0 <= (int)p->nLutK )
+ else if ( nSuppSize1 <= (int)p->nLutK - 2 )
{
DelayA = Lpk_SuppDelay( puSupps[2*Var+1] | (1<<Var), p->pDelays );
DelayB = Lpk_SuppDelay( puSupps[2*Var+0] , p->pDelays );
Delay = ABC_MAX( DelayA, DelayB + 1 );
- Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK );
+ Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
Polarity = 1;
}
- else if ( nSuppSize1 <= (int)p->nLutK - 2 )
+ else if ( nSuppSize0 <= (int)p->nLutK )
{
DelayA = Lpk_SuppDelay( puSupps[2*Var+1] | (1<<Var), p->pDelays );
DelayB = Lpk_SuppDelay( puSupps[2*Var+0] , p->pDelays );
Delay = ABC_MAX( DelayA, DelayB + 1 );
- Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
+ Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK );
Polarity = 1;
}
else if ( nSuppSize1 <= (int)p->nLutK )
@@ -171,15 +170,16 @@ int Lpk_MuxAnalize( Lpk_Fun_t * p )
continue;
if ( Area > (int)p->nAreaLim )
continue;
- if ( VarBest == -1 || AreaBest > Area || (AreaBest == Area && nSuppSizeBest > nSuppSize0+nSuppSize1) )
+ if ( pRes->Variable == -1 || pRes->AreaEst > Area || (pRes->AreaEst == Area && nSuppSizeBest > nSuppSize0+nSuppSize1) )
{
- VarBest = Var;
- AreaBest = Area;
- PolarityBest = Polarity;
- nSuppSizeBest = nSuppSize0+nSuppSize1;
+ pRes->Variable = Var;
+ pRes->Polarity = Polarity;
+ pRes->AreaEst = Area;
+ pRes->DelayEst = Delay;
+ nSuppSizeBest = nSuppSize0+nSuppSize1;
}
}
- return (VarBest == -1)? -1 : (2*VarBest + Polarity);
+ return pRes->Variable == -1 ? NULL : pRes;
}
/**Function*************************************************************
@@ -193,60 +193,61 @@ int Lpk_MuxAnalize( Lpk_Fun_t * p )
SeeAlso []
***********************************************************************/
-Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int VarPol )
+Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int Var, int Pol )
{
Lpk_Fun_t * pNew;
unsigned * pTruth = Lpk_FunTruth( p, 0 );
unsigned * pTruth0 = Lpk_FunTruth( p, 1 );
unsigned * pTruth1 = Lpk_FunTruth( p, 2 );
- int Var = VarPol / 2;
- int Pol = VarPol % 2;
int iVarVac;
- assert( VarPol >= 0 && VarPol < 2 * (int)p->nVars );
+ assert( Var >= 0 && Var < (int)p->nVars );
assert( p->nAreaLim >= 2 );
Lpk_FunComputeCofs( p, Var );
- if ( Pol == 0 )
+ // derive the new component
+ pNew = Lpk_FunDup( p, Pol ? pTruth0 : pTruth1 );
+ // update the support of the old component
+ p->uSupp = Kit_TruthSupport( Pol ? pTruth1 : pTruth0, p->nVars );
+ p->uSupp |= (1 << Var);
+ // update the truth table of the old component
+ iVarVac = Kit_WordFindFirstBit( ~p->uSupp );
+ assert( iVarVac < (int)p->nVars );
+ Kit_TruthIthVar( pTruth, p->nVars, Var );
+ if ( Pol )
+ Kit_TruthMuxVar( pTruth, pTruth, pTruth1, p->nVars, iVarVac );
+ else
+ Kit_TruthMuxVar( pTruth, pTruth0, pTruth, p->nVars, iVarVac );
+ // set the decomposed variable
+ p->pFanins[iVarVac] = pNew->Id;
+ p->pDelays[iVarVac] = p->nDelayLim - 1;
+ // support minimize both
+ Lpk_FunSuppMinimize( p );
+ Lpk_FunSuppMinimize( pNew );
+ // update delay and area requirements
+ pNew->nDelayLim = p->nDelayLim - 1;
+ if ( p->nVars <= p->nLutK )
{
- // derive the new component
- pNew = Lpk_FunDup( p, pTruth1 );
- // update the old component
- p->uSupp = Kit_TruthSupport( pTruth0, p->nVars );
- iVarVac = Kit_WordFindFirstBit( ~(p->uSupp | (1 << Var)) );
- assert( iVarVac < (int)p->nVars );
- Kit_TruthIthVar( pTruth, p->nVars, iVarVac );
- // update the truth table
- Kit_TruthMux( pTruth, pTruth0, pTruth1, pTruth, p->nVars );
- p->pFanins[iVarVac] = pNew->Id;
- p->pDelays[iVarVac] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays );
- // support minimize both
- Lpk_FunSuppMinimize( p );
- Lpk_FunSuppMinimize( pNew );
- // update delay and area requirements
- pNew->nDelayLim = p->nDelayLim - 1;
- if ( p->nVars <= p->nLutK )
- {
- pNew->nAreaLim = p->nAreaLim - 1;
- p->nAreaLim = 1;
- }
- else if ( pNew->nVars <= pNew->nLutK )
- {
- pNew->nAreaLim = 1;
- p->nAreaLim = p->nAreaLim - 1;
- }
- else if ( p->nVars < pNew->nVars )
- {
- pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
- p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
- }
- else // if ( pNew->nVars < p->nVars )
- {
- pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
- p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
- }
+ pNew->nAreaLim = p->nAreaLim - 1;
+ p->nAreaLim = 1;
+ }
+ else if ( pNew->nVars <= pNew->nLutK )
+ {
+ pNew->nAreaLim = 1;
+ p->nAreaLim = p->nAreaLim - 1;
+ }
+ else if ( p->nVars < pNew->nVars )
+ {
+ pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
+ p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
+ }
+ else // if ( pNew->nVars < p->nVars )
+ {
+ pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
+ p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
}
return p;
}
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/opt/lpk/lpkAbcUtil.c b/src/opt/lpk/lpkAbcUtil.c
index 960ebded..681ec092 100644
--- a/src/opt/lpk/lpkAbcUtil.c
+++ b/src/opt/lpk/lpkAbcUtil.c
@@ -139,20 +139,20 @@ Lpk_Fun_t * Lpk_FunDup( Lpk_Fun_t * p, unsigned * pTruth )
***********************************************************************/
void Lpk_FunSuppMinimize( Lpk_Fun_t * p )
{
- int j, k, nVarsNew;
+ int i, k, nVarsNew;
// compress the truth table
if ( p->uSupp == Kit_BitMask(p->nVars) )
return;
// minimize support
nVarsNew = Kit_WordCountOnes(p->uSupp);
Kit_TruthShrink( Lpk_FunTruth(p, 1), Lpk_FunTruth(p, 0), nVarsNew, p->nVars, p->uSupp, 1 );
- for ( j = k = 0; j < (int)p->nVars; j++ )
- if ( p->uSupp & (1 << j) )
- {
- p->pFanins[k] = p->pFanins[j];
- p->pDelays[k] = p->pDelays[j];
- k++;
- }
+ k = 0;
+ Lpk_SuppForEachVar( p->uSupp, i )
+ {
+ p->pFanins[k] = p->pFanins[i];
+ p->pDelays[k] = p->pDelays[i];
+ k++;
+ }
assert( k == nVarsNew );
p->nVars = k;
p->uSupp = Kit_BitMask(p->nVars);
diff --git a/src/opt/lpk/lpkCore.c b/src/opt/lpk/lpkCore.c
index fda5423e..37bfd956 100644
--- a/src/opt/lpk/lpkCore.c
+++ b/src/opt/lpk/lpkCore.c
@@ -361,17 +361,10 @@ p->timeTruth += clock() - clk;
if ( p->pPars->fVeryVerbose )
{
// char * pFileName;
- int nSuppSize;
- Kit_DsdNtk_t * pDsdNtk;
- nSuppSize = Extra_TruthSupportSize(pTruth, pCut->nLeaves);
+ int nSuppSize = Extra_TruthSupportSize( pTruth, pCut->nLeaves );
printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ",
i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight );
-
- pDsdNtk = Kit_DsdDecompose( pTruth, pCut->nLeaves );
-// Kit_DsdVerify( pDsdNtk, pTruth, pCut->nLeaves );
- Kit_DsdPrint( stdout, pDsdNtk );
- Kit_DsdNtkFree( pDsdNtk );
-// Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves );
+ Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves );
// pFileName = Kit_TruthDumpToFile( pTruth, pCut->nLeaves, Count++ );
// printf( "Saved truth table in file \"%s\".\n", pFileName );
}
diff --git a/src/opt/lpk/lpkCut.c b/src/opt/lpk/lpkCut.c
index d0908a6a..f5c0c66c 100644
--- a/src/opt/lpk/lpkCut.c
+++ b/src/opt/lpk/lpkCut.c
@@ -30,7 +30,7 @@
/**Function*************************************************************
- Synopsis [Computes the truth able of one cut.]
+ Synopsis [Computes the truth table of one cut.]
Description []
@@ -445,10 +445,17 @@ void Lpk_NodeCutsOne( Lpk_Man_t * p, Lpk_Cut_t * pCut, int Node )
memcpy( pCutNew->pNodes, pCut->pNodes, pCut->nNodes * sizeof(int) );
pCutNew->nNodes = pCut->nNodes;
pCutNew->nNodesDup = pCut->nNodesDup;
+
// check if the node is already there
+ // if so, move the node to be the last
for ( i = 0; i < (int)pCutNew->nNodes; i++ )
if ( pCutNew->pNodes[i] == Node )
+ {
+ for ( k = i; k < (int)pCutNew->nNodes - 1; k++ )
+ pCutNew->pNodes[k] = pCutNew->pNodes[k+1];
+ pCutNew->pNodes[k] = Node;
break;
+ }
if ( i == (int)pCutNew->nNodes ) // new node
{
pCutNew->pNodes[ pCutNew->nNodes++ ] = Node;
diff --git a/src/opt/lpk/lpkInt.h b/src/opt/lpk/lpkInt.h
index 7022cc4a..32fb05b3 100644
--- a/src/opt/lpk/lpkInt.h
+++ b/src/opt/lpk/lpkInt.h
@@ -122,14 +122,14 @@ struct Lpk_Man_t_
typedef struct Lpk_Fun_t_ Lpk_Fun_t;
struct Lpk_Fun_t_
{
- Vec_Ptr_t * vNodes; // the array of all functions
- unsigned int Id : 5; // the ID of this node
+ Vec_Ptr_t * vNodes; // the array of leaves and decomposition nodes
+ unsigned int Id : 8; // the ID of this node
unsigned int nVars : 5; // the number of variables
unsigned int nLutK : 4; // the number of LUT inputs
- unsigned int nAreaLim : 8; // the area limit (the largest allowed)
+ unsigned int nAreaLim : 5; // the area limit (the largest allowed)
unsigned int nDelayLim : 10; // the delay limit (the largest allowed)
- char pFanins[16]; // the fanins of this function
char pDelays[16]; // the delays of the inputs
+ char pFanins[16]; // the fanins of this function
unsigned uSupp; // the support of this component
unsigned pTruth[0]; // the truth table (contains room for three truth tables)
};
@@ -146,6 +146,8 @@ struct Lpk_Res_t_
int nSuppSizeL; // support size of the larger (composition) function
int DelayEst; // estimated delay of the decomposition
int AreaEst; // estimated area of the decomposition
+ int Variable; // variable in MUX decomposition
+ int Polarity; // polarity in MUX decomposition
};
static inline int Lpk_LutNumVars( int nLutsLim, int nLutK ) { return nLutsLim * (nLutK - 1) + 1; }
@@ -177,11 +179,11 @@ static inline unsigned * Lpk_FunTruth( Lpk_Fun_t * p, int Num ) { assert( Num
/*=== lpkAbcDec.c ============================================================*/
extern Abc_Obj_t * Lpk_Decompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim );
/*=== lpkAbcDsd.c ============================================================*/
-extern Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth );
+extern Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p );
extern Lpk_Fun_t * Lpk_DsdSplit( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet );
/*=== lpkAbcMux.c ============================================================*/
-extern int Lpk_MuxAnalize( Lpk_Fun_t * p );
-extern Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int VarPol );
+extern Lpk_Res_t * Lpk_MuxAnalize( Lpk_Fun_t * p );
+extern Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int Var, int Pol );
/*=== lpkAbcUtil.c ============================================================*/
extern Lpk_Fun_t * Lpk_FunAlloc( int nVars );
extern void Lpk_FunFree( Lpk_Fun_t * p );
diff --git a/src/opt/lpk/lpkMux.c b/src/opt/lpk/lpkMux.c
index 7928f77e..ed046ad7 100644
--- a/src/opt/lpk/lpkMux.c
+++ b/src/opt/lpk/lpkMux.c
@@ -167,6 +167,8 @@ If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, I
ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] ); Kit_DsdNtkFree( pTemp );
Kit_DsdTruthPartial( p->pDsdMan, ppNtks[0], pDec0, uSubset0 );
Kit_DsdTruthPartial( p->pDsdMan, ppNtks[1], pDec1, uSubset1 );
+// Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[0], uSubset0, iVarReused, pCo0, pDec0 );
+// Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[1], uSubset1, iVarReused, pCo1, pDec1 );
Kit_DsdNtkFree( ppNtks[0] );
Kit_DsdNtkFree( ppNtks[1] );
//Kit_DsdPrintFromTruth( pDec0, nVars );
@@ -218,6 +220,7 @@ If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, I
Kit_TruthMuxVar( pCo1, pCo10, pCo11, nVars, iVarReused );
//Kit_DsdPrintFromTruth( pCo0, nVars );
//Kit_DsdPrintFromTruth( pCo1, nVars );
+
// derive the composition function
Kit_TruthMuxVar( pCo , pCo0 , pCo1 , nVars, iVar );
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-08 15:32:54 +0000