New feature to optimize delay during mapping.

5 files changed, 115 insertions, 8 deletions

diff --git a/src/map/if/if.h b/src/map/if/if.h
index 7be9f145..8914b464 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -525,6 +525,8 @@ extern int             If_CluCheckExt3( void * p, word * pTruth, int nVars, int
 extern int             If_CutDelaySop( If_Man_t * p, If_Cut_t * pCut );
 extern int             If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig );
 extern int             If_CutSopBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm );
+extern int             If_CutLutBalanceEval( If_Man_t * p, If_Cut_t * pCut );
+extern int             If_CutLutBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm );
 /*=== ifDsd.c =============================================================*/
 extern If_DsdMan_t *   If_DsdManAlloc( int nVars, int nLutSize );
 extern void            If_DsdManPrint( If_DsdMan_t * p, char * pFileName, int Number, int Support, int fOccurs, int fTtDump, int fVerbose );
diff --git a/src/map/if/ifDelay.c b/src/map/if/ifDelay.c
index 9c5704b7..433b4e4d 100644
--- a/src/map/if/ifDelay.c
+++ b/src/map/if/ifDelay.c
@@ -238,6 +238,7 @@ int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig )
         assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 );
         if ( vAig )
             Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) );
+        pCut->Cost = 0;
         return 0;
     }
     if ( pCut->nLeaves == 1 ) // variable
@@ -247,6 +248,7 @@ int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig )
             Vec_IntPush( vAig, 0 );
         if ( vAig )
             Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) );
+        pCut->Cost = 0;
         return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
     }
     else
@@ -263,6 +265,98 @@ int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig )
     }
 }
 
+/**Function*************************************************************
+
+  Synopsis    [Evaluate delay using SOP balancing.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int If_CutLutBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm )
+{
+    if ( pCut->nLeaves == 0 ) // const
+        return 0;
+    if ( pCut->nLeaves == 1 ) // variable
+    {
+        pPerm[0] = 0;
+        return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
+    }
+    else
+    {
+        int LutSize = p->pPars->pLutStruct[0] - '0';
+        int i, Delay, DelayMax;
+        assert( (If_CutLeaveNum(pCut) > LutSize) == (pCut->uMaskFunc > 0) );
+        for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
+        {
+            if ( If_CutLeaveNum(pCut) > LutSize && ((pCut->uMaskFunc >> (i << 2)) & 1) )
+                pPerm[i] = 2;
+            else
+                pPerm[i] = 1;
+            Delay = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay;
+            DelayMax = Abc_MaxInt( DelayMax, Delay + (int)pPerm[i] );
+        }
+        return DelayMax;
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Evaluate delay using SOP balancing.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int If_CutLutBalanceEval( If_Man_t * p, If_Cut_t * pCut )
+{
+    pCut->fUser = 1;
+    pCut->Cost = pCut->nLeaves > 1 ? 1 : 0;
+    if ( pCut->nLeaves == 0 ) // const
+    {
+        assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 );
+        return 0;
+    }
+    if ( pCut->nLeaves == 1 ) // variable
+    {
+        assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 1 );
+        return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
+    }
+    else
+    {
+        int LutSize = p->pPars->pLutStruct[0] - '0';
+        int i, pTimes[IF_MAX_FUNC_LUTSIZE];
+        int DelayMax = 0, nLeafMax = 0;
+        unsigned uLeafMask = 0;
+        for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
+        {
+            pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay; 
+            assert( DelayMax <= pTimes[i] );
+            if ( DelayMax < pTimes[i] )
+                DelayMax = pTimes[i], nLeafMax = 1, uLeafMask = (1 << (i << 2));
+            else
+                nLeafMax++, uLeafMask |= (1 << (i << 2));
+        }
+        if ( If_CutLeaveNum(pCut) <= LutSize )
+            return DelayMax + 1;
+        pCut->Cost = 2;
+        if ( nLeafMax <= LutSize - 1 )
+        {
+            pCut->uMaskFunc = If_DsdManCheckXY( p->pIfDsdMan, If_CutDsdLit(p, pCut), LutSize, 1, uLeafMask, 0, 0 );
+            if ( pCut->uMaskFunc > 0 )
+                return DelayMax + 1;
+        }
+        pCut->uMaskFunc = If_DsdManCheckXY( p->pIfDsdMan, If_CutDsdLit(p, pCut), LutSize, 1, 0, 0, 0 );
+        return DelayMax + 2;
+    }
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/ifDsd.c b/src/map/if/ifDsd.c
index 317ceac5..3eeef4c8 100644
--- a/src/map/if/ifDsd.c
+++ b/src/map/if/ifDsd.c
@@ -1529,7 +1529,7 @@ unsigned If_DsdManCheckAndXor( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, I
         If_DsdManComputeFirst( p, pObj, pFirsts );
         uRes = If_DsdSign(p, pObj, i[0], iFirst + pFirsts[i[0]], 0) | 
                If_DsdSign(p, pObj, i[1], iFirst + pFirsts[i[1]], 0);
-        if ( uRes & ~(uRes >> 1) & uMaskNot )
+        if ( uRes & uMaskNot )
             continue;
         return uRes;
     }
@@ -1549,7 +1549,7 @@ unsigned If_DsdManCheckAndXor( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, I
         uRes = If_DsdSign(p, pObj, i[0], iFirst + pFirsts[i[0]], 0) | 
                If_DsdSign(p, pObj, i[1], iFirst + pFirsts[i[1]], 0) | 
                If_DsdSign(p, pObj, i[2], iFirst + pFirsts[i[2]], 0);
-        if ( uRes & ~(uRes >> 1) & uMaskNot )
+        if ( uRes & uMaskNot )
             continue;
         return uRes;
     }
@@ -1571,7 +1571,7 @@ unsigned If_DsdManCheckAndXor( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, I
                If_DsdSign(p, pObj, i[1], iFirst + pFirsts[i[1]], 0) | 
                If_DsdSign(p, pObj, i[2], iFirst + pFirsts[i[2]], 0) | 
                If_DsdSign(p, pObj, i[3], iFirst + pFirsts[i[3]], 0);
-        if ( uRes & ~(uRes >> 1) & uMaskNot )
+        if ( uRes & uMaskNot )
             continue;
         return uRes;
     }
@@ -1596,7 +1596,7 @@ unsigned If_DsdManCheckMux( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, If_D
             return ~0;
         If_DsdManComputeFirst( p, pObj, pFirsts );
         uRes = If_DsdSign(p, pObj, 0, iFirst + pFirsts[0], 1) | If_DsdSign(p, pObj, 1, iFirst + pFirsts[1], 0);
-        if ( (uRes & ~(uRes >> 1) & uMaskNot) == 0 )
+        if ( (uRes & uMaskNot) == 0 )
             return uRes;
     }
     // second input
@@ -1608,7 +1608,7 @@ unsigned If_DsdManCheckMux( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, If_D
             return ~0;
         If_DsdManComputeFirst( p, pObj, pFirsts );
         uRes = If_DsdSign(p, pObj, 0, iFirst + pFirsts[0], 1) | If_DsdSign(p, pObj, 2, iFirst + pFirsts[2], 0);
-        if ( (uRes & ~(uRes >> 1) & uMaskNot) == 0 )
+        if ( (uRes & uMaskNot) == 0 )
             return uRes;
     }
     return 0;
@@ -1665,7 +1665,7 @@ Dau_DecPrintSets( vSets, nFans );
                     uRes |= If_DsdSign(p, pObj, v, iFirst + pFirsts[v], 1);
                 else assert( 0 );
             }
-            if ( uRes & ~(uRes >> 1) & uMaskNot )
+            if ( uRes & uMaskNot )
                 continue;
             return uRes;
         }
@@ -2010,6 +2010,7 @@ int If_CutDsdBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig )
         assert( Abc_Lit2Var(If_CutDsdLit(p, pCut)) == 0 );
         if ( vAig )
             Vec_IntPush( vAig, Abc_LitIsCompl(If_CutDsdLit(p, pCut)) );
+        pCut->Cost = 0;
         return 0;
     }
     if ( pCut->nLeaves == 1 ) // variable
@@ -2019,6 +2020,7 @@ int If_CutDsdBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig )
             Vec_IntPush( vAig, 0 );
         if ( vAig )
             Vec_IntPush( vAig, Abc_LitIsCompl(If_CutDsdLit(p, pCut)) );
+        pCut->Cost = 0;
         return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
     }
     else
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
index 9452feb3..e1d69501 100644
--- a/src/map/if/ifMap.c
+++ b/src/map/if/ifMap.c
@@ -99,7 +99,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep
     If_Cut_t * pCut0R, * pCut1R;
     int fFunc0R, fFunc1R;
     int i, k, v, fChange;
-    int fSave0 = p->pPars->fDelayOpt || p->pPars->fDsdBalance || p->pPars->fUserRecLib;
+    int fSave0 = p->pPars->fDelayOpt || p->pPars->fDelayOptLut || p->pPars->fDsdBalance || p->pPars->fUserRecLib;
     assert( !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 0 );
     assert( !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 0 );
 
@@ -122,6 +122,8 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep
         // recompute the parameters of the best cut
         if ( p->pPars->fDelayOpt )
             pCut->Delay = If_CutSopBalanceEval( p, pCut, NULL );
+        else if ( p->pPars->fDelayOptLut )
+            pCut->Delay = If_CutLutBalanceEval( p, pCut );
         else if ( p->pPars->fDsdBalance )
             pCut->Delay = If_CutDsdBalanceEval( p, pCut, NULL );
         else if ( p->pPars->fUserRecLib )
@@ -278,6 +280,8 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep
         // check if the cut satisfies the required times
         if ( p->pPars->fDelayOpt )
             pCut->Delay = If_CutSopBalanceEval( p, pCut, NULL );
+        else if ( p->pPars->fDelayOptLut )
+            pCut->Delay = If_CutLutBalanceEval( p, pCut );
         else if ( p->pPars->fDsdBalance )
             pCut->Delay = If_CutDsdBalanceEval( p, pCut, NULL );
         else if ( p->pPars->fUserRecLib )
@@ -351,7 +355,7 @@ void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fP
     If_Set_t * pCutSet;
     If_Obj_t * pTemp;
     If_Cut_t * pCutTemp, * pCut;
-    int i, fSave0 = p->pPars->fDelayOpt || p->pPars->fDsdBalance || p->pPars->fUserRecLib;
+    int i, fSave0 = p->pPars->fDelayOpt || p->pPars->fDelayOptLut || p->pPars->fDsdBalance || p->pPars->fUserRecLib;
     assert( pObj->pEquiv != NULL );
 
     // prepare
diff --git a/src/map/if/ifTime.c b/src/map/if/ifTime.c
index 82468f75..e35ba0db 100644
--- a/src/map/if/ifTime.c
+++ b/src/map/if/ifTime.c
@@ -207,6 +207,11 @@ void If_CutPropagateRequired( If_Man_t * p, If_Obj_t * pObj, If_Cut_t * pCut, fl
                 int Delay = If_CutSopBalancePinDelays( p, pCut, pPerm );
                 assert( Delay == pCut->Delay );
             }
+            else if ( p->pPars->fDelayOptLut )
+            {
+                int Delay = If_CutLutBalancePinDelays( p, pCut, pPerm );
+                assert( Delay == pCut->Delay );
+            }
             else if ( p->pPars->fDsdBalance )
             {
                 int Delay = If_CutDsdBalancePinDelays( p, pCut, pPerm );