Improving performance of 'lutpack'.

6 files changed, 134 insertions, 12 deletions

diff --git a/src/opt/lpk/lpkCore.c b/src/opt/lpk/lpkCore.c
index 27912a9a..728aa2dd 100644
--- a/src/opt/lpk/lpkCore.c
+++ b/src/opt/lpk/lpkCore.c
@@ -35,6 +35,82 @@ ABC_NAMESPACE_IMPL_START
 
 /**Function*************************************************************
 
+  Synopsis    [Returns decomposed network.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Abc_Ntk_t * Abc_NtkDecFromTruth( word * pTruth, int nVars, int nLutSize )
+{
+    extern Abc_Ntk_t * Abc_NtkLutmin( Abc_Ntk_t * pNtk, int nLutSize, int fVerbose );
+    Vec_Int_t * vCover = Vec_IntAlloc( 1 << 16 );
+    Abc_Ntk_t * pTemp = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 );
+    char * pSopCover = Abc_SopCreateFromTruthIsop( (Mem_Flex_t *)pTemp->pManFunc, nVars, pTruth, vCover );
+    Abc_Ntk_t * pNtk = Abc_NtkCreateWithNode( pSopCover );
+    Abc_Ntk_t * pNew = Abc_NtkLutmin( pNtk, nLutSize, 0 );
+    Abc_NtkDelete( pTemp );
+    Abc_NtkDelete( pNtk );
+    Vec_IntFree( vCover );
+    if ( !Abc_NtkToAig(pNew) )
+    {
+        Abc_NtkDelete( pNew );
+        fprintf( stdout, "Converting to AIG has failed.\n" );
+        return NULL;
+    }
+    assert( Abc_NtkHasAig(pNew) );
+    return pNew;
+}
+Abc_Obj_t * Abc_NtkLutMinDecompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, word * pTruth, int nLutSize, int Required )
+{
+    Abc_Obj_t * pObj = NULL, * pFanin; int i, k;
+    Abc_Ntk_t * pNew = Abc_NtkDecFromTruth( pTruth, Vec_PtrSize(vLeaves), nLutSize );
+    Vec_Ptr_t * vNodes = Abc_NtkDfs( pNew, 0 );
+    assert( Abc_NtkHasAig(pNtk) );
+    // levels
+    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
+        Abc_NtkCi( pNew, i )->Level = pObj->Level;
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+    {
+        pObj->Level = 0;
+        Abc_ObjForEachFanin( pObj, pFanin, k )
+            if ( pObj->Level < pFanin->Level )
+                pObj->Level = pFanin->Level;
+        pObj->Level++;
+    }
+    if ( (int)pObj->Level > Required )
+    {
+        Vec_PtrFree( vNodes );
+        Abc_NtkDelete( pNew );
+        return NULL;
+    }
+    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
+        Abc_NtkCi( pNew, i )->pCopy = pObj;
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+    {
+        Abc_NtkDupObj( pNtk, pObj, 0 );
+        pObj->pCopy->Level = 0;
+        Abc_ObjForEachFanin( pObj, pFanin, k )
+        {
+            Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
+            if ( pObj->pCopy->Level < pFanin->pCopy->Level )
+                pObj->pCopy->Level = pFanin->pCopy->Level;
+        }
+        pObj->pCopy->Level++;
+    }
+    //printf( "Decomposed %d-input function, resulting in %d nodes.\n", Vec_PtrSize(vLeaves), Vec_PtrSize(vNodes) );
+    pObj = pObj->pCopy;
+    Vec_PtrFree( vNodes );
+    Abc_NtkDelete( pNew );
+    return pObj;
+}
+
+
+/**Function*************************************************************
+
   Synopsis    [Prepares the mapping manager.]
 
   Description []
@@ -272,7 +348,7 @@ p->timeCuts += Abc_Clock() - clk;
 //        printf( "Mffc size = %d.  ", Abc_NodeMffcLabel(p->pObj) );
         for ( k = 0; k < (int)pCut->nLeaves; k++ )
             Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++;
-        nCutNodes = Abc_NodeMffcLabel(p->pObj);
+        nCutNodes = Abc_NodeMffcLabel(p->pObj, NULL);
 //        printf( "Mffc with cut = %d.  ", nCutNodes );
         for ( k = 0; k < (int)pCut->nLeaves; k++ )
             Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--;
@@ -353,7 +429,6 @@ void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth )
         p->puSupps[0] = p->puSupps[1] = 0;
 }
 
-
 /**Function*************************************************************
 
   Synopsis    [Performs resynthesis for one node.]
@@ -368,6 +443,7 @@ void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth )
 int Lpk_ResynthesizeNodeNew( Lpk_Man_t * p )
 {
 //    static int Count = 0;
+    int NodeCounts[16] = { 0, 0, 0, 0, 1, 3, 6, 14, 26, 57, 106, 230, 425, 1000000, 1000000, 1000000 };
     Abc_Obj_t * pObjNew, * pLeaf;
     Lpk_Cut_t * pCut;
     unsigned * pTruth;
@@ -405,7 +481,7 @@ p->timeCuts += Abc_Clock() - clk;
 //        printf( "Mffc size = %d.  ", Abc_NodeMffcLabel(p->pObj) );
         for ( k = 0; k < (int)pCut->nLeaves; k++ )
             Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++;
-        nCutNodes = Abc_NodeMffcLabel(p->pObj);
+        nCutNodes = Abc_NodeMffcLabel(p->pObj, NULL);
 //        printf( "Mffc with cut = %d.  ", nCutNodes );
         for ( k = 0; k < (int)pCut->nLeaves; k++ )
             Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--;
@@ -461,6 +537,8 @@ p->timeTruth3 += Abc_Clock() - clk;
 clk = Abc_Clock();
         pObjNew = Lpk_Decompose( p, p->pNtk, p->vLeaves, pTruth, p->puSupps, p->pPars->nLutSize,
             (int)pCut->nNodes - (int)pCut->nNodesDup - 1 + (int)(p->pPars->fZeroCost > 0), Required );
+        if ( pObjNew == NULL && p->pPars->nLutSize == 4 && (int)pCut->nNodes > NodeCounts[Vec_PtrSize(p->vLeaves)] + !p->pPars->fZeroCost )
+            pObjNew = Abc_NtkLutMinDecompose( p->pNtk, p->vLeaves, (word *)pTruth, p->pPars->nLutSize, Required );
 p->timeEval += Abc_Clock() - clk;
         nNodesAft = Abc_NtkNodeNum(p->pNtk);
 
diff --git a/src/opt/lpk/lpkCut.c b/src/opt/lpk/lpkCut.c
index 208facf2..41cfaed5 100644
--- a/src/opt/lpk/lpkCut.c
+++ b/src/opt/lpk/lpkCut.c
@@ -576,6 +576,37 @@ void Lpk_NodeCutsOne( Lpk_Man_t * p, Lpk_Cut_t * pCut, int Node )
 
 /**Function*************************************************************
 
+  Synopsis    [Count support.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Lpk_CountSupp( Abc_Ntk_t * p, Vec_Ptr_t * vNodes )
+{
+    Abc_Obj_t * pObj, * pFanin; 
+    int i, k, Count = 0;
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+    {
+        Abc_ObjForEachFanin( pObj, pFanin, k )
+        {
+            if ( Abc_NodeIsTravIdCurrent(pFanin) )
+                continue;
+            Count += !pFanin->fPersist;
+            pFanin->fPersist = 1;
+        }
+    }
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+        Abc_ObjForEachFanin( pObj, pFanin, k )
+            pFanin->fPersist = 0;
+    return Count;
+}
+
+/**Function*************************************************************
+
   Synopsis    [Computes the set of all cuts.]
 
   Description []
@@ -589,13 +620,20 @@ int Lpk_NodeCuts( Lpk_Man_t * p )
 {
     Lpk_Cut_t * pCut, * pCut2;
     int i, k, Temp, nMffc, fChanges;
+    //int nSupp;
 
     // mark the MFFC of the node with the current trav ID
-    nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj );
+    Vec_PtrClear( p->vTemp );
+    nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj, p->vTemp );
     assert( nMffc > 0 );
     if ( nMffc == 1 )
         return 0;
-
+/*
+    // count the leaves
+    nSupp = Lpk_CountSupp( p->pNtk, p->vTemp );
+    if ( nMffc > 10 && nSupp <= 10 )
+        printf( "Obj = %4d : Supp = %4d. Mffc = %4d.\n", p->pObj->Id, nSupp, nMffc );
+*/
     // initialize the first cut
     pCut = p->pCuts; p->nCuts = 1;
     pCut->nNodes = 0; 
@@ -650,6 +688,9 @@ int Lpk_NodeCuts( Lpk_Man_t * p )
         if ( pCut->fHasDsd )
             continue;
         p->pEvals[p->nEvals++] = i;
+
+//        if ( pCut->nLeaves <= 9 && pCut->nNodes > 15 )
+//        printf( "%5d : Obj = %4d  Leaves = %4d  Nodes = %4d  LUTs = %4d\n", i, p->pObj->Id, pCut->nLeaves, pCut->nNodes, pCut->nLuts );
     }
     if ( p->nEvals == 0 )
         return 0;
diff --git a/src/opt/lpk/lpkInt.h b/src/opt/lpk/lpkInt.h
index 02181001..9285a423 100644
--- a/src/opt/lpk/lpkInt.h
+++ b/src/opt/lpk/lpkInt.h
@@ -44,8 +44,8 @@ ABC_NAMESPACE_HEADER_START
 ///                         BASIC TYPES                              ///
 ////////////////////////////////////////////////////////////////////////
 
-#define LPK_SIZE_MAX             24     // the largest size of the function
-#define LPK_CUTS_MAX            512     // the largest number of cuts considered
+#define LPK_SIZE_MAX            100    // the largest size of the function
+#define LPK_CUTS_MAX          10000    // the largest number of cuts considered
 
 typedef struct Lpk_Man_t_ Lpk_Man_t;
 typedef struct Lpk_Cut_t_ Lpk_Cut_t;
@@ -93,6 +93,7 @@ struct Lpk_Man_t_
     int          pRefs[LPK_SIZE_MAX];   // fanin reference counters 
     int          pCands[LPK_SIZE_MAX];  // internal nodes pointing only to the leaves
     Vec_Ptr_t *  vLeaves;
+    Vec_Ptr_t *  vTemp;
     // truth table representation
     Vec_Ptr_t *  vTtElems;              // elementary truth tables
     Vec_Ptr_t *  vTtNodes;              // storage for temporary truth tables of the nodes 
diff --git a/src/opt/lpk/lpkMan.c b/src/opt/lpk/lpkMan.c
index f012ab75..384741c5 100644
--- a/src/opt/lpk/lpkMan.c
+++ b/src/opt/lpk/lpkMan.c
@@ -54,8 +54,9 @@ Lpk_Man_t * Lpk_ManStart( Lpk_Par_t * pPars )
     p->nCutsMax = LPK_CUTS_MAX;
     p->vTtElems = Vec_PtrAllocTruthTables( pPars->nVarsMax );
     p->vTtNodes = Vec_PtrAllocSimInfo( 1024, Abc_TruthWordNum(pPars->nVarsMax) );
-    p->vCover = Vec_IntAlloc( 1 << 12 );
-    p->vLeaves = Vec_PtrAlloc( 32 );
+    p->vCover   = Vec_IntAlloc( 1 << 12 );
+    p->vLeaves  = Vec_PtrAlloc( 32 );
+    p->vTemp    = Vec_PtrAlloc( 32 );
     for ( i = 0; i < 8; i++ )
         p->vSets[i] = Vec_IntAlloc(100);
     p->pDsdMan = Kit_DsdManAlloc( pPars->nVarsMax, 64 );
@@ -112,6 +113,7 @@ void Lpk_ManStop( Lpk_Man_t * p )
     if ( p->vVisited )
         Vec_VecFree( p->vVisited );
     Vec_PtrFree( p->vLeaves );
+    Vec_PtrFree( p->vTemp );
     Vec_IntFree( p->vCover );
     Vec_PtrFree( p->vTtElems );
     Vec_PtrFree( p->vTtNodes );
diff --git a/src/opt/mfs/mfsResub.c b/src/opt/mfs/mfsResub.c
index dc73cea7..5bb2ad49 100644
--- a/src/opt/mfs/mfsResub.c
+++ b/src/opt/mfs/mfsResub.c
@@ -183,7 +183,7 @@ int Abc_NtkMfsSolveSatResub( Mfs_Man_t * p, Abc_Obj_t * pNode, int iFanin, int f
         printf( "%5d : Lev =%3d. Leaf =%3d. Node =%3d. Divs =%3d.  Fanin = %4d (%d/%d), MFFC = %d\n", 
             pNode->Id, pNode->Level, Vec_PtrSize(p->vSupp), Vec_PtrSize(p->vNodes), Vec_PtrSize(p->vDivs)-Abc_ObjFaninNum(pNode), 
             Abc_ObjFaninId(pNode, iFanin), iFanin, Abc_ObjFaninNum(pNode), 
-            Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin)) : 0 );
+            Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin), NULL) : 0 );
     }
 
     // try fanins without the critical fanin
@@ -337,7 +337,7 @@ int Abc_NtkMfsSolveSatResub2( Mfs_Man_t * p, Abc_Obj_t * pNode, int iFanin, int
         printf( "Node %5d : Level = %2d. Divs = %3d.  Fanins = %d/%d (out of %d). MFFC = %d\n", 
             pNode->Id, pNode->Level, Vec_PtrSize(p->vDivs)-Abc_ObjFaninNum(pNode), 
             iFanin, iFanin2, Abc_ObjFaninNum(pNode), 
-            Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin)) : 0 );
+            Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin), NULL) : 0 );
     }
 
     // try fanins without the critical fanin
diff --git a/src/opt/sfm/sfmDec.c b/src/opt/sfm/sfmDec.c
index c5af0ac0..a558c120 100644
--- a/src/opt/sfm/sfmDec.c
+++ b/src/opt/sfm/sfmDec.c
@@ -1865,7 +1865,7 @@ Abc_Obj_t * Abc_NtkAreaOptOne( Sfm_Dec_t * p, int i )
     Sfm_Par_t * pPars = p->pPars;
     Abc_Obj_t * pObj = Abc_NtkObj( p->pNtk, i ); 
     int Limit, RetValue;
-    if ( pPars->nMffcMin > 1 && Abc_NodeMffcLabel(pObj) < pPars->nMffcMin )
+    if ( pPars->nMffcMin > 1 && Abc_NodeMffcLabel(pObj, NULL) < pPars->nMffcMin )
         return NULL;
     if ( pPars->iNodeOne && i != pPars->iNodeOne )
         return NULL;