DSD manager.

4 files changed, 136 insertions, 30 deletions

diff --git a/src/map/if/if.h b/src/map/if/if.h
index 6a2fdd5d..e8c57998 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -188,6 +188,8 @@ struct If_Man_t_
     int                nChoices;      // the number of choice nodes
     Vec_Int_t *        vSwitching;    // switching activity of each node
     Vec_Int_t **       pDriverCuts;   // temporary driver cuts
+    int                pPerm[3][IF_MAX_LUTSIZE]; // permutations
+    int                nShared;       // the number of shared variables
     // SOP balancing
     Vec_Int_t *        vCover;        // used to compute ISOP
     Vec_Wrd_t *        vAnds;         // intermediate storage
@@ -437,7 +439,7 @@ extern int             If_ManPerformMappingComb( If_Man_t * p );
 extern int             If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut );
 extern void            If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut );
 extern void            If_CutOrder( If_Cut_t * pCut );
-extern int             If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut );
+extern int             If_CutMerge( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut );
 extern int             If_CutCheck( If_Cut_t * pCut );
 extern void            If_CutPrint( If_Cut_t * pCut );
 extern void            If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut );
diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c
index d23c4365..8e89977f 100644
--- a/src/map/if/ifCut.c
+++ b/src/map/if/ifCut.c
@@ -231,13 +231,12 @@ static inline int If_CutMergeOrderedOld( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_
   SeeAlso     []
 
 ***********************************************************************/
-static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC )
+static inline int If_CutMergeOrdered( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC )
 { 
-    int nLimit = pC0->nLimit;
     int nSizeC0 = pC0->nLeaves;
     int nSizeC1 = pC1->nLeaves;
-    int i, k, c;
-    assert( nSizeC0 >= nSizeC1 );
+    int nLimit  = pC0->nLimit;
+    int i, k, c, s;
 
     // the case when one of the cuts is the largest
     if ( nSizeC0 == nLimit )
@@ -246,43 +245,37 @@ static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t *
         if ( nSizeC1 == nLimit )
         {
             for ( i = 0; i < nSizeC0; i++ )
-                if ( pC0->pLeaves[i] != pC1->pLeaves[i] )
-                    return 0;
-        }
-        else
-        {
-            for ( i = 0; i < nSizeC1; i++ )
             {
-                for ( k = nSizeC0 - 1; k >= 0; k-- )
-                    if ( pC0->pLeaves[k] == pC1->pLeaves[i] )
-                        break;
-                if ( k == -1 ) // did not find
+                if ( pC0->pLeaves[i] != pC1->pLeaves[i] )
                     return 0;
+                p->pPerm[0][i] = p->pPerm[1][i] = p->pPerm[2][i] = i;
+                pC->pLeaves[i] = pC0->pLeaves[i];
             }
+            pC->nLeaves = nLimit;
+            return 1;
         }
-        for ( i = 0; i < nSizeC0; i++ )
-            pC->pLeaves[i] = pC0->pLeaves[i];
-        pC->nLeaves = nLimit;
-        return 1;
     }
 
     // compare two cuts with different numbers
-    i = k = c = 0;
+    i = k = c = s = 0;
     while ( 1 )
     {
         if ( c == nLimit ) return 0;
         if ( pC0->pLeaves[i] < pC1->pLeaves[k] )
         {
+            p->pPerm[0][i] = c;
             pC->pLeaves[c++] = pC0->pLeaves[i++];
             if ( i >= nSizeC0 ) goto FlushCut1;
         }
         else if ( pC0->pLeaves[i] > pC1->pLeaves[k] )
         {
+            p->pPerm[1][k] = c;
             pC->pLeaves[c++] = pC1->pLeaves[k++];
             if ( k >= nSizeC1 ) goto FlushCut0;
         }
         else
         {
+            p->pPerm[0][i] = p->pPerm[1][k] = p->pPerm[2][s++] = c;
             pC->pLeaves[c++] = pC0->pLeaves[i++]; k++;
             if ( i >= nSizeC0 ) goto FlushCut1;
             if ( k >= nSizeC1 ) goto FlushCut0;
@@ -292,14 +285,20 @@ static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t *
 FlushCut0:
     if ( c + nSizeC0 > nLimit + i ) return 0;
     while ( i < nSizeC0 )
+    {
+        p->pPerm[0][i] = c;
         pC->pLeaves[c++] = pC0->pLeaves[i++];
+    }
     pC->nLeaves = c;
     return 1;
 
 FlushCut1:
     if ( c + nSizeC1 > nLimit + k ) return 0;
     while ( k < nSizeC1 )
+    {
+        p->pPerm[1][k] = c;
         pC->pLeaves[c++] = pC1->pLeaves[k++];
+    }
     pC->nLeaves = c;
     return 1;
 }
@@ -369,18 +368,18 @@ static inline int If_CutMergeOrdered2( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t
   SeeAlso     []
 
 ***********************************************************************/
-int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut )
+int If_CutMerge2( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut )
 { 
     assert( pCut->nLimit > 0 );
     // merge the nodes
     if ( pCut0->nLeaves < pCut1->nLeaves )
     {
-        if ( !If_CutMergeOrdered( pCut1, pCut0, pCut ) )
+        if ( !If_CutMergeOrdered( p, pCut1, pCut0, pCut ) )
             return 0;
     }
     else
     {
-        if ( !If_CutMergeOrdered( pCut0, pCut1, pCut ) )
+        if ( !If_CutMergeOrdered( p, pCut0, pCut1, pCut ) )
             return 0;
     }
     pCut->uSign = pCut0->uSign | pCut1->uSign;
@@ -399,6 +398,91 @@ int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut )
   SeeAlso     []
 
 ***********************************************************************/
+int If_CutMerge( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC )
+{ 
+    int nSizeC0 = pC0->nLeaves;
+    int nSizeC1 = pC1->nLeaves;
+    int nLimit  = pC0->nLimit;
+    int i, k, c, s;
+
+    // both cuts are the largest
+    if ( nSizeC0 == nLimit && nSizeC1 == nLimit )
+    {
+        for ( i = 0; i < nSizeC0; i++ )
+        {
+            if ( pC0->pLeaves[i] != pC1->pLeaves[i] )
+                return 0;
+            p->pPerm[0][i] = p->pPerm[1][i] = p->pPerm[2][i] = i;
+            pC->pLeaves[i] = pC0->pLeaves[i];
+        }
+        p->nShared = nLimit;
+        pC->nLeaves = nLimit;
+        pC->uSign = pC0->uSign | pC1->uSign;
+        return 1;
+    }
+
+    // compare two cuts with different numbers
+    i = k = c = s = 0;
+    while ( 1 )
+    {
+        if ( c == nLimit ) return 0;
+        if ( pC0->pLeaves[i] < pC1->pLeaves[k] )
+        {
+            p->pPerm[0][i] = c;
+            pC->pLeaves[c++] = pC0->pLeaves[i++];
+            if ( i == nSizeC0 ) goto FlushCut1;
+        }
+        else if ( pC0->pLeaves[i] > pC1->pLeaves[k] )
+        {
+            p->pPerm[1][k] = c;
+            pC->pLeaves[c++] = pC1->pLeaves[k++];
+            if ( k == nSizeC1 ) goto FlushCut0;
+        }
+        else
+        {
+            p->pPerm[0][i] = p->pPerm[1][k] = p->pPerm[2][s++] = c;
+            pC->pLeaves[c++] = pC0->pLeaves[i++]; k++;
+            if ( i == nSizeC0 ) goto FlushCut1;
+            if ( k == nSizeC1 ) goto FlushCut0;
+        }
+    }
+
+FlushCut0:
+    if ( c + nSizeC0 > nLimit + i ) return 0;
+    while ( i < nSizeC0 )
+    {
+        p->pPerm[0][i] = c;
+        pC->pLeaves[c++] = pC0->pLeaves[i++];
+    }
+    p->nShared = s;
+    pC->nLeaves = c;
+    pC->uSign = pC0->uSign | pC1->uSign;
+    return 1;
+
+FlushCut1:
+    if ( c + nSizeC1 > nLimit + k ) return 0;
+    while ( k < nSizeC1 )
+    {
+        p->pPerm[1][k] = c;
+        pC->pLeaves[c++] = pC1->pLeaves[k++];
+    }
+    p->nShared = s;
+    pC->nLeaves = c;
+    pC->uSign = pC0->uSign | pC1->uSign;
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Prepares the object for FPGA mapping.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int If_CutCompareDelay( If_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
 {
     If_Cut_t * pC0 = *ppC0;
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
index a8876889..11b9449d 100644
--- a/src/map/if/ifMap.c
+++ b/src/map/if/ifMap.c
@@ -243,8 +243,9 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep
         if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize )
             continue;
         // merge the cuts
-        if ( !If_CutMerge( pCut0, pCut1, pCut ) )
+        if ( !If_CutMerge( p, pCut0, pCut1, pCut ) )
             continue;
+        assert( If_CutCheck( pCut ) );
         if ( pObj->fSpec && pCut->nLeaves == (unsigned)p->pPars->nLutSize )
             continue;
         assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
diff --git a/src/map/if/ifTruth.c b/src/map/if/ifTruth.c
index cef41e50..4c7a1d96 100644
--- a/src/map/if/ifTruth.c
+++ b/src/map/if/ifTruth.c
@@ -498,7 +498,7 @@ static inline int If_CutTruthMinimize6( If_Man_t * p, If_Cut_t * pCut )
 //    assert( nSuppSize == Abc_TtSupportSize(If_CutTruthW(pCut), nVars) );
     return 1;
 }
-static inline word If_TruthStretch6( word Truth, If_Cut_t * pCut, If_Cut_t * pCut0 )
+static inline word If_TruthStretch6_( word Truth, If_Cut_t * pCut, If_Cut_t * pCut0 )
 {
     int i, k;
     for ( i = (int)pCut->nLeaves - 1, k = (int)pCut0->nLeaves - 1; i >= 0 && k >= 0; i-- )
@@ -512,13 +512,23 @@ static inline word If_TruthStretch6( word Truth, If_Cut_t * pCut, If_Cut_t * pCu
     }
     return Truth;
 }
+static inline word If_TruthStretch6( word Truth, int nVars, int * pPerm, int nVarsCut )
+{
+    int i; 
+    for ( i = nVarsCut - 1; i >= 0; i-- )
+        if ( i < pPerm[i] )
+            Abc_TtSwapVars( &Truth, nVars, i, pPerm[i] );
+    return Truth;
+}
 static inline int If_CutComputeTruth6( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 )
 {
     word t0 = (fCompl0 ^ pCut0->fCompl) ? ~*If_CutTruthW(pCut0) : *If_CutTruthW(pCut0);
     word t1 = (fCompl1 ^ pCut1->fCompl) ? ~*If_CutTruthW(pCut1) : *If_CutTruthW(pCut1);
     assert( pCut->nLimit <= 6 );
-    t0 = If_TruthStretch6( t0, pCut, pCut0 );
-    t1 = If_TruthStretch6( t1, pCut, pCut1 );
+//    t0 = If_TruthStretch6( t0, pCut, pCut0 );
+//    t1 = If_TruthStretch6( t1, pCut, pCut1 );
+    t0 = If_TruthStretch6( t0, pCut->nLimit, p->pPerm[0], pCut0->nLeaves );
+    t1 = If_TruthStretch6( t1, pCut->nLimit, p->pPerm[1], pCut1->nLeaves );
     *If_CutTruthW(pCut) = t0 & t1;
 
 #ifdef IF_TRY_NEW
@@ -615,7 +625,7 @@ static inline int If_CutTruthMinimize2( If_Man_t * p, If_Cut_t * pCut )
 //    assert( nSuppSize == Abc_TtSupportSize(If_CutTruthW(pCut), nVars) );
     return 1;
 }
-static inline void If_TruthStretch2( word * pTruth, If_Cut_t * pCut, If_Cut_t * pCut0 )
+static inline void If_TruthStretch2_( word * pTruth, If_Cut_t * pCut, If_Cut_t * pCut0 )
 {
     int i, k;
     for ( i = (int)pCut->nLeaves - 1, k = (int)pCut0->nLeaves - 1; i >= 0 && k >= 0; i-- )
@@ -628,6 +638,13 @@ static inline void If_TruthStretch2( word * pTruth, If_Cut_t * pCut, If_Cut_t *
         k--;
     }
 }
+static inline void If_TruthStretch2( word * pTruth, int nVars, int * pPerm, int nVarsCut )
+{
+    int i; 
+    for ( i = nVarsCut - 1; i >= 0; i-- )
+        if ( i < pPerm[i] )
+            Abc_TtSwapVars( pTruth, nVars, i, pPerm[i] );
+}
 inline int If_CutComputeTruth2( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 )
 {
     int nWords;
@@ -636,8 +653,10 @@ inline int If_CutComputeTruth2( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0,
     nWords = Abc_TtWordNum( pCut->nLimit );
     Abc_TtCopy( (word *)p->puTemp[0], If_CutTruthW(pCut0), nWords, fCompl0 ^ pCut0->fCompl );
     Abc_TtCopy( (word *)p->puTemp[1], If_CutTruthW(pCut1), nWords, fCompl1 ^ pCut1->fCompl );
-    If_TruthStretch2( (word *)p->puTemp[0], pCut, pCut0 );
-    If_TruthStretch2( (word *)p->puTemp[1], pCut, pCut1 );
+//    If_TruthStretch2( (word *)p->puTemp[0], pCut, pCut0 );
+//    If_TruthStretch2( (word *)p->puTemp[1], pCut, pCut1 );
+    If_TruthStretch2( (word *)p->puTemp[0], pCut->nLimit, p->pPerm[0], pCut0->nLeaves );
+    If_TruthStretch2( (word *)p->puTemp[1], pCut->nLimit, p->pPerm[1], pCut1->nLeaves );
     Abc_TtAnd( If_CutTruthW(pCut), (word *)p->puTemp[0], (word *)p->puTemp[1], nWords, 0 );
 
 #ifdef IF_TRY_NEW