Logic sharing for multi-input gates.

2 files changed, 204 insertions, 12 deletions

diff --git a/src/base/abci/abcExtract.c b/src/base/abci/abcExtract.c
index 1a543eaa..c0d4d70c 100644
--- a/src/base/abci/abcExtract.c
+++ b/src/base/abci/abcExtract.c
@@ -315,17 +315,19 @@ void Abc_NtkTraverseSupers( Abc_ShaMan_t * p, int fAnd )
     int i, nOnesMax;
 
     // create mapping of nodes into their column vectors
-    vInputs = Vec_PtrStart( Abc_NtkObjNumMax(p->pNtk) );
+    vInputs = Vec_PtrStart( Abc_NtkObjNumMax(p->pNtk) * (1 + fAnd) );
     Abc_NtkIncrementTravId( p->pNtk );
     if ( fAnd )
     {
         Abc_NtkForEachCo( p->pNtk, pObj, i )
-            Abc_NtkTraverseSupersAnd_rec( p, Abc_ObjFanin0(pObj), vInputs );
+            if ( Abc_ObjIsNode(Abc_ObjFanin0(pObj)) )
+                Abc_NtkTraverseSupersAnd_rec( p, Abc_ObjFanin0(pObj), vInputs );
     }
     else
     {
         Abc_NtkForEachCo( p->pNtk, pObj, i )
-            Abc_NtkTraverseSupersXor_rec( p, Abc_ObjFanin0(pObj), vInputs );
+            if ( Abc_ObjIsNode(Abc_ObjFanin0(pObj)) )
+                Abc_NtkTraverseSupersXor_rec( p, Abc_ObjFanin0(pObj), vInputs );
     }
     p->nStartCols = Vec_IntSize(p->vObj2Lit);
 
@@ -646,7 +648,10 @@ Abc_Ntk_t * Abc_NtkUpdateNetwork( Abc_ShaMan_t * p, int fAnd )
     // create map of originals
     vMap2Repl = Vec_IntStartFull( Abc_NtkObjNumMax(p->pNtk) );
     Vec_PtrForEachEntry( Abc_Obj_t *, vOrig, pObj, i )
+    {
+//        printf( "Replacing %d by %d.\n", Abc_ObjId(pObj), Abc_ObjToLit((Abc_Obj_t *)Vec_PtrEntry(vRepl, i)) );
         Vec_IntWriteEntry( vMap2Repl, Abc_ObjId(pObj), Abc_ObjToLit((Abc_Obj_t *)Vec_PtrEntry(vRepl, i)) );
+    }
     Vec_PtrFree( vOrig );
     Vec_PtrFree( vRepl );
 
@@ -660,7 +665,7 @@ Abc_Ntk_t * Abc_NtkUpdateNetwork( Abc_ShaMan_t * p, int fAnd )
             {
                 if ( iLit == iLitConst1 && fAnd )
                 {
-                    pObj->fCompl0 = 1;
+                    pObj->fCompl0 ^= 1;
                     Vec_IntWriteEntry( &pObj->vFanins, 0, Abc_Lit2Var(iLitConst1) );
                 }
                 else
@@ -677,7 +682,7 @@ Abc_Ntk_t * Abc_NtkUpdateNetwork( Abc_ShaMan_t * p, int fAnd )
             {
                 if ( iLit == iLitConst1 && fAnd )
                 {
-                    pObj->fCompl1 = 1;
+                    pObj->fCompl1 ^= 1;
                     Vec_IntWriteEntry( &pObj->vFanins, 1, Abc_Lit2Var(iLitConst1) );
                 }
                 else
diff --git a/src/opt/dar/darBalance.c b/src/opt/dar/darBalance.c
index a1afd2ad..484b86e7 100644
--- a/src/opt/dar/darBalance.c
+++ b/src/opt/dar/darBalance.c
@@ -34,6 +34,150 @@ ABC_NAMESPACE_IMPL_START
 ///                     FUNCTION DEFINITIONS                         ///
 ////////////////////////////////////////////////////////////////////////
 
+
+
+static inline word  Dar_BalPack( int Lev, int Id )  { return (((word)Lev) << 32) | Id; }
+static inline int   Dar_BalUnpackLev( word Num )    { return (Num >> 32);              }
+static inline int   Dar_BalUnpackId( word Num )     { return Num & 0xFFFF;             }
+
+/**Function*************************************************************
+
+  Synopsis    [Collects one multi-input gate.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Wrd_t * Dar_BalSuperXor( Aig_Man_t * p, Aig_Obj_t * pObj, int * pfCompl )
+{
+    Aig_Obj_t * pObj0, * pObj1, * pRoot = NULL;
+    Vec_Wrd_t * vSuper;
+    word Num, NumNext;
+    int i, k, fCompl = 0;
+    assert( !Aig_IsComplement(pObj) );
+    assert( Aig_ObjIsExor(pObj) );
+    // start iteration
+    vSuper = Vec_WrdAlloc( 10 );
+    Vec_WrdPush( vSuper, Dar_BalPack(Aig_ObjLevel(pObj), Aig_ObjId(pObj)) );
+    while ( Vec_WrdSize(vSuper) > 0 && Vec_WrdSize(vSuper) < 10000 )
+    {
+        // make sure there are no duplicates
+        Num = Vec_WrdEntry( vSuper, 0 );
+        Vec_WrdForEachEntryStart( vSuper, NumNext, i, 1 )
+        {
+            assert( Num < NumNext );
+            Num = NumNext;
+        }
+        // extract XOR gate decomposable on the topmost level
+        Vec_WrdForEachEntryReverse( vSuper, Num, i )
+        {
+            pRoot = Aig_ManObj( p, Dar_BalUnpackId(Num) );
+            if ( Aig_ObjIsExor(pRoot) && Aig_ObjRefs(pRoot) == 1 )
+            {
+                Vec_WrdRemove( vSuper, Num );
+                break;
+            }
+        }
+        if ( i == -1 )
+            break;
+        // extract
+        assert( !Aig_ObjFaninC0(pObj) && !Aig_ObjFaninC1(pObj) );
+        pObj0 = Aig_ObjChild0(pObj);
+        pObj1 = Aig_ObjChild1(pObj);
+        fCompl ^= Aig_IsComplement(pObj0);  pObj0 = Aig_Regular(pObj0);
+        fCompl ^= Aig_IsComplement(pObj1);  pObj1 = Aig_Regular(pObj1);
+        Vec_WrdPushOrder( vSuper, Dar_BalPack(Aig_ObjLevel(pObj0), Aig_ObjId(pObj0)) );
+        Vec_WrdPushOrder( vSuper, Dar_BalPack(Aig_ObjLevel(pObj1), Aig_ObjId(pObj1)) );
+        // remove duplicates
+        k = 0;
+        Vec_WrdForEachEntry( vSuper, Num, i )
+        {
+            if ( i + 1 == Vec_WrdSize(vSuper) )
+            {
+                Vec_WrdWriteEntry( vSuper, k++, Num );
+                break;
+            }
+            NumNext = Vec_WrdEntry( vSuper, i+1 );
+            assert( Num <= NumNext );
+            if ( Num == NumNext )
+                i++;
+            else
+                Vec_WrdWriteEntry( vSuper, k++, Num );
+        }
+        Vec_WrdShrink( vSuper, k );
+    }
+    *pfCompl = fCompl;
+    Vec_WrdForEachEntry( vSuper, Num, i )
+        Vec_WrdWriteEntry( vSuper, i, Dar_BalUnpackId(Num) );
+    return vSuper;
+}
+Vec_Wrd_t * Dar_BalSuperAnd( Aig_Man_t * p, Aig_Obj_t * pObj )
+{
+    Aig_Obj_t * pObj0, * pObj1, * pRoot = NULL;
+    Vec_Wrd_t * vSuper;
+    word Num, NumNext;
+    int i, k;
+    assert( !Aig_IsComplement(pObj) );
+    // start iteration
+    vSuper = Vec_WrdAlloc( 10 );
+    Vec_WrdPush( vSuper, Dar_BalPack(Aig_ObjLevel(pObj), Aig_ObjToLit(pObj)) );
+    while ( Vec_WrdSize(vSuper) > 0 && Vec_WrdSize(vSuper) < 10000 )
+    {
+        // make sure there are no duplicates
+        Num = Vec_WrdEntry( vSuper, 0 );
+        Vec_WrdForEachEntryStart( vSuper, NumNext, i, 1 )
+        {
+            assert( Num < NumNext );
+            Num = NumNext;
+        }
+        // extract AND gate decomposable on the topmost level
+        Vec_WrdForEachEntryReverse( vSuper, Num, i )
+        {
+            pRoot = Aig_ObjFromLit( p, Dar_BalUnpackId(Num) );
+            if ( !Aig_IsComplement(pRoot) && Aig_ObjIsNode(pRoot) && Aig_ObjRefs(pRoot) == 1 )
+            {
+                Vec_WrdRemove( vSuper, Num );
+                break;
+            }
+        }
+        if ( i == -1 )
+            break;
+        // extract
+        pObj0 = Aig_ObjChild0(pRoot);
+        pObj1 = Aig_ObjChild1(pRoot);
+        Vec_WrdPushOrder( vSuper, Dar_BalPack(Aig_ObjLevel(Aig_Regular(pObj0)), Aig_ObjToLit(pObj0)) );
+        Vec_WrdPushOrder( vSuper, Dar_BalPack(Aig_ObjLevel(Aig_Regular(pObj1)), Aig_ObjToLit(pObj1)) );
+        // remove duplicates
+        k = 0;
+        Vec_WrdForEachEntry( vSuper, Num, i )
+        {
+            if ( i + 1 == Vec_WrdSize(vSuper) )
+            {
+                Vec_WrdWriteEntry( vSuper, k++, Num );
+                break;
+            }
+            NumNext = Vec_WrdEntry( vSuper, i+1 );
+            assert( Num <= NumNext );
+            if ( Num + 1 == NumNext && (NumNext & 1) ) // pos_lit & neg_lit = 0
+            {
+                Vec_WrdClear( vSuper );
+                return vSuper;
+            }
+            if ( Num < NumNext )
+                Vec_WrdWriteEntry( vSuper, k++, Num );
+        }
+        Vec_WrdShrink( vSuper, k );
+    }
+    Vec_WrdForEachEntry( vSuper, Num, i )
+        Vec_WrdWriteEntry( vSuper, i, Dar_BalUnpackId(Num) );
+    return vSuper;
+}
+
+
+
 /**Function*************************************************************
 
   Synopsis    [Collects the nodes of the supergate.]
@@ -103,7 +247,7 @@ int Dar_BalanceCone_rec( Aig_Obj_t * pRoot, Aig_Obj_t * pObj, Vec_Ptr_t * vSuper
   SeeAlso     []
 
 ***********************************************************************/
-Vec_Ptr_t * Dar_BalanceCone( Aig_Obj_t * pObj, Vec_Vec_t * vStore, int Level )
+Vec_Ptr_t * Dar_BalanceCone( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Vec_t * vStore, int Level )
 {
     Vec_Ptr_t * vNodes;
     int RetValue, i;
@@ -129,6 +273,50 @@ Vec_Ptr_t * Dar_BalanceCone( Aig_Obj_t * pObj, Vec_Vec_t * vStore, int Level )
 
 /**Function*************************************************************
 
+  Synopsis    [Collects the nodes of the supergate.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Dar_BalanceCone_( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Vec_t * vStore, int Level )
+{
+    Vec_Wrd_t * vSuper;
+    Vec_Ptr_t * vNodes;
+    word Num;
+    int i;
+    assert( !Aig_IsComplement(pObj) );
+    // extend the storage
+    if ( Vec_VecSize( vStore ) <= Level )
+        Vec_VecPush( vStore, Level, 0 );
+    // get the temporary array of nodes
+    vNodes = Vec_VecEntry( vStore, Level );
+    Vec_PtrClear( vNodes );
+    // collect the nodes in the implication supergate
+    // load the result into the output array
+    if ( Aig_ObjIsExor(pObj) )
+    {
+        int fCompl = 0;
+        vSuper = Dar_BalSuperXor( p, pObj, &fCompl ); 
+        Vec_WrdForEachEntry( vSuper, Num, i )
+            Vec_PtrPush( vNodes, Aig_ManObj(p, Dar_BalUnpackId(Num)) );
+        assert( fCompl == 0 );
+    }
+    else
+    {
+        vSuper = Dar_BalSuperAnd( p, pObj );
+        Vec_WrdForEachEntry( vSuper, Num, i )
+            Vec_PtrPush( vNodes, Aig_ObjFromLit(p, Dar_BalUnpackId(Num)) );
+    }
+    Vec_WrdFree( vSuper );
+    return vNodes;
+}
+
+/**Function*************************************************************
+
   Synopsis    [Finds the left bound on the next candidate to be paired.]
 
   Description [The nodes in the array are in the decreasing order of levels. 
@@ -404,7 +592,7 @@ Aig_Obj_t * Dar_BalanceBuildSuperTop( Aig_Man_t * p, Vec_Ptr_t * vSuper, Aig_Typ
   SeeAlso     []
 
 ***********************************************************************/
-Aig_Obj_t * Dar_Balance_rec( Aig_Man_t * pNew, Aig_Obj_t * pObjOld, Vec_Vec_t * vStore, int Level, int fUpdateLevel )
+Aig_Obj_t * Dar_Balance_rec( Aig_Man_t * pNew, Aig_Man_t * p, Aig_Obj_t * pObjOld, Vec_Vec_t * vStore, int Level, int fUpdateLevel )
 {
     Aig_Obj_t * pObjNew;
     Vec_Ptr_t * vSuper;
@@ -416,7 +604,7 @@ Aig_Obj_t * Dar_Balance_rec( Aig_Man_t * pNew, Aig_Obj_t * pObjOld, Vec_Vec_t *
         return (Aig_Obj_t *)pObjOld->pData;
     assert( Aig_ObjIsNode(pObjOld) );
     // get the implication supergate
-    vSuper = Dar_BalanceCone( pObjOld, vStore, Level );
+    vSuper = Dar_BalanceCone( p, pObjOld, vStore, Level );
     // check if supergate contains two nodes in the opposite polarity
     if ( vSuper->nSize == 0 )
         return (Aig_Obj_t *)(pObjOld->pData = Aig_ManConst0(pNew));
@@ -427,7 +615,7 @@ Aig_Obj_t * Dar_Balance_rec( Aig_Man_t * pNew, Aig_Obj_t * pObjOld, Vec_Vec_t *
     // for each old node, derive the new well-balanced node
     for ( i = 0; i < Vec_PtrSize(vSuper); i++ )
     {
-        pObjNew = Dar_Balance_rec( pNew, Aig_Regular((Aig_Obj_t *)vSuper->pArray[i]), vStore, Level + 1, fUpdateLevel );
+        pObjNew = Dar_Balance_rec( pNew, p, Aig_Regular((Aig_Obj_t *)vSuper->pArray[i]), vStore, Level + 1, fUpdateLevel );
         vSuper->pArray[i] = Aig_NotCond( pObjNew, Aig_IsComplement((Aig_Obj_t *)vSuper->pArray[i]) );
     }
     // build the supergate
@@ -514,7 +702,7 @@ Aig_Man_t * Dar_ManBalance( Aig_Man_t * p, int fUpdateLevel )
             {
                 // perform balancing
                 pDriver = Aig_ObjReal_rec( Aig_ObjChild0(pObj) );
-                pObjNew = Dar_Balance_rec( pNew, Aig_Regular(pDriver), vStore, 0, fUpdateLevel );
+                pObjNew = Dar_Balance_rec( pNew, p, Aig_Regular(pDriver), vStore, 0, fUpdateLevel );
                 pObjNew = Aig_NotCond( pObjNew, Aig_IsComplement(pDriver) );
                 // save arrival time of the output
                 arrTime = (float)Aig_Regular(pObjNew)->Level;
@@ -541,7 +729,7 @@ Aig_Man_t * Dar_ManBalance( Aig_Man_t * p, int fUpdateLevel )
         Aig_ManForEachCo( p, pObj, i )
         {
             pDriver = Aig_ObjReal_rec( Aig_ObjChild0(pObj) );
-            pObjNew = Dar_Balance_rec( pNew, Aig_Regular(pDriver), vStore, 0, fUpdateLevel );
+            pObjNew = Dar_Balance_rec( pNew, p, Aig_Regular(pDriver), vStore, 0, fUpdateLevel );
             pObjNew = Aig_NotCond( pObjNew, Aig_IsComplement(pDriver) );
             pObjNew = Aig_ObjCreateCo( pNew, pObjNew );
             pObjNew->pHaig = pObj->pHaig;
@@ -640,6 +828,5 @@ void Dar_BalancePrintStats( Aig_Man_t * p )
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
 
-
 ABC_NAMESPACE_IMPL_END