Experiments with word-level data structures.

2 files changed, 210 insertions, 1 deletions

diff --git a/src/aig/gia/giaDup.c b/src/aig/gia/giaDup.c
index 4f094b48..1164e16b 100644
--- a/src/aig/gia/giaDup.c
+++ b/src/aig/gia/giaDup.c
@@ -5221,6 +5221,144 @@ Gia_Man_t * Gia_ManDupAddPis( Gia_Man_t * p, int nMulti )
     return pNew;
 }
 
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Wec_t ** Gia_ManDupUifBuildMap( Gia_Man_t * p )
+{
+    Vec_Wec_t ** pvMap = ABC_ALLOC( Vec_Wec_t *, 2 ); 
+    Vec_Int_t * vBufs = Vec_IntAlloc( p->nBufs ); 
+    Gia_Obj_t * pObj; int i, Item, j, k = 0;
+    pvMap[0] = Vec_WecAlloc(10);
+    pvMap[1] = Vec_WecAlloc(10);
+    Gia_ManForEachObj1( p, pObj, i )
+        if ( Gia_ObjIsBuf(pObj) )
+            Vec_IntPush( vBufs, i );
+    assert( p->nBufs == Vec_IntSize(vBufs) );
+    Vec_IntForEachEntry( p->vBarBufs, Item, i )
+    {
+        Vec_Int_t * vVec = Vec_WecPushLevel(pvMap[Item&1]);
+        for ( j = 0; j < (Item >> 16); j++ )
+            Vec_IntPush( vVec, Vec_IntEntry(vBufs, k++) );
+    }
+    Vec_IntFree( vBufs );
+    assert( p->nBufs == k );
+    assert( Vec_WecSize(pvMap[0]) == Vec_WecSize(pvMap[1]) );
+    return pvMap;
+}
+int Gia_ManDupUifConstrOne( Gia_Man_t * pNew, Gia_Man_t * p, Vec_Int_t * vVec0, Vec_Int_t * vVec1 )
+{
+    Vec_Int_t * vTemp = Vec_IntAlloc( Vec_IntSize(vVec0) );
+    int i, o0, o1, iRes;
+    Vec_IntForEachEntryTwo( vVec0, vVec1, o0, o1, i )
+        Vec_IntPush( vTemp, Gia_ManHashXor(pNew, Gia_ManObj(p, o0)->Value, Abc_LitNot(Gia_ManObj(p, o1)->Value)) );
+    iRes = Gia_ManHashAndMulti( pNew, vTemp );
+    Vec_IntFree( vTemp );
+    return iRes;
+}
+int Gia_ManDupUifConstr( Gia_Man_t * pNew, Gia_Man_t * p, Vec_Wec_t ** pvMap )
+{
+    int i, k, iUif = 1;
+    assert( Vec_WecSize(pvMap[0]) == Vec_WecSize(pvMap[1]) );
+    for ( i = 0;     i < Vec_WecSize(pvMap[0]); i++ )
+    for ( k = i + 1; k < Vec_WecSize(pvMap[0]); k++ )
+    {
+        int iCond1 = Gia_ManDupUifConstrOne( pNew, p, Vec_WecEntry(pvMap[0], i), Vec_WecEntry(pvMap[0], k) );
+        int iCond2 = Gia_ManDupUifConstrOne( pNew, p, Vec_WecEntry(pvMap[1], i), Vec_WecEntry(pvMap[1], k) );
+        int iRes = Gia_ManHashOr( pNew, Abc_LitNot(iCond1), iCond2 );
+        iUif = Gia_ManHashAnd( pNew, iUif, iRes );
+    }
+    return iUif;
+}
+Gia_Man_t * Gia_ManDupUif( Gia_Man_t * p )
+{
+    Vec_Wec_t ** pvMap = Gia_ManDupUifBuildMap( p );
+    Gia_Man_t * pNew, * pTemp; Gia_Obj_t * pObj;
+    int i, iUif = 0;
+    pNew = Gia_ManStart( Gia_ManObjNum(p) );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    Gia_ManConst0(p)->Value = 0;
+    Gia_ManHashAlloc( pNew );
+    Gia_ManForEachObj1( p, pObj, i )
+    {
+        if ( Gia_ObjIsBuf(pObj) )
+            pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
+        else if ( Gia_ObjIsAnd(pObj) )
+            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+        else if ( Gia_ObjIsCi(pObj) )
+            pObj->Value = Gia_ManAppendCi( pNew );
+        else if ( Gia_ObjIsCo(pObj) )
+            pObj->Value = Gia_ObjFanin0Copy(pObj);
+    }
+    iUif = Gia_ManDupUifConstr( pNew, p, pvMap );
+    Gia_ManForEachCo( p, pObj, i )
+        Gia_ManAppendCo( pNew, Gia_ManAppendAnd(pNew, pObj->Value, iUif) );
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    Vec_WecFree( pvMap[0] );
+    Vec_WecFree( pvMap[1] );
+    ABC_FREE( pvMap );
+    if ( p->vBarBufs )
+        pNew->vBarBufs = Vec_IntDup( p->vBarBufs );
+    return pNew;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_ManDupBlackBoxBuildMap( Gia_Man_t * p )
+{
+    Vec_Int_t * vMap = Vec_IntAlloc( p->nBufs ); int i, Item;
+    Vec_IntForEachEntry( p->vBarBufs, Item, i )
+        Vec_IntFillExtra( vMap, Vec_IntSize(vMap) + (Item >> 16), Item & 1 );
+    assert( p->nBufs == Vec_IntSize(vMap) );
+    return vMap;
+}
+Gia_Man_t * Gia_ManDupBlackBox( Gia_Man_t * p )
+{
+    Vec_Int_t * vMap = Gia_ManDupBlackBoxBuildMap( p );
+    Gia_Man_t * pNew, * pTemp;
+    Gia_Obj_t * pObj;
+    int i, k = 0;
+    pNew = Gia_ManStart( Gia_ManObjNum(p) );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    Gia_ManConst0(p)->Value = 0;
+    Gia_ManHashAlloc( pNew );
+    Gia_ManForEachObj1( p, pObj, i )
+    {
+        if ( Gia_ObjIsBuf(pObj) )
+            pObj->Value = Vec_IntEntry(vMap, k++) ? Gia_ManAppendCi(pNew) : Gia_ObjFanin0Copy(pObj); // out/in
+        else if ( Gia_ObjIsAnd(pObj) )
+            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+        else if ( Gia_ObjIsCi(pObj) )
+            pObj->Value = Gia_ManAppendCi( pNew );
+        else if ( Gia_ObjIsCo(pObj) )
+            pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
+    }
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    Vec_IntFree( vMap );
+    return pNew;
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/aig/gia/giaSimBase.c b/src/aig/gia/giaSimBase.c
index c31064fe..c8808532 100644
--- a/src/aig/gia/giaSimBase.c
+++ b/src/aig/gia/giaSimBase.c
@@ -750,7 +750,7 @@ void Gia_ManSimProfile( Gia_Man_t * pGia )
     Vec_Wrd_t * vSims = Gia_ManSimPatSim( pGia );
     int nWords = Vec_WrdSize(vSims) / Gia_ManObjNum(pGia);
     int nC0s = 0, nC1s = 0, nUnique = Gia_ManSimPatHashPatterns( pGia, nWords, vSims, &nC0s, &nC1s );
-    printf( "Simulating %d patterns leads to %d unique objects (%.2f %% out of %d), Const0 = %d. Const1 = %d.\n", 
+    printf( "Simulating %d patterns leads to %d unique objects (%.2f %% out of %d). Const0 = %d. Const1 = %d.\n", 
         64*nWords, nUnique, 100.0*nUnique/Gia_ManCandNum(pGia), Gia_ManCandNum(pGia), nC0s, nC1s );
     Vec_WrdFree( vSims );
 }
@@ -2700,6 +2700,77 @@ Vec_Ptr_t * Gia_ManPtrWrdReadBin( char * pFileName, int fVerbose )
     return p;
 }
 
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManCompareSims( Gia_Man_t * pHie, Gia_Man_t * pFlat, int nWords, int fVerbose )
+{
+    abctime clk = Abc_Clock();
+    Vec_Wrd_t * vSims  = pFlat->vSimsPi = pHie->vSimsPi = Vec_WrdStartRandom( Gia_ManCiNum(pFlat) * nWords );
+    Vec_Wrd_t * vSims0 = Gia_ManSimPatSim( pFlat );
+    Vec_Wrd_t * vSims1 = Gia_ManSimPatSim( pHie );
+    Gia_Obj_t * pObj; int * pSpot, * pSpot2, i, nC0s = 0, nC1s = 0, nUnique = 0, nFound[3] = {0}, nBoundary = 0, nMatched = 0;
+    Vec_Mem_t * vStore = Vec_MemAlloc( nWords, 12 ); // 2^12 N-word entries per page
+    pFlat->vSimsPi = NULL;
+    pHie->vSimsPi = NULL;
+    Vec_WrdFree( vSims );
+
+    printf( "Comparing two AIGs using %d simulation words.\n", nWords );
+    printf( "Hierarchical: " ); Gia_ManPrintStats( pHie, NULL );
+    printf( "Flat:         " ); Gia_ManPrintStats( pFlat, NULL );
+
+    Vec_MemHashAlloc( vStore, 1 << 12 );
+    Gia_ManForEachCand( pFlat, pObj, i )
+    {
+        word * pSim = Vec_WrdEntryP(vSims0, i*nWords);
+        nC0s += Abc_TtIsConst0(pSim, nWords);
+        nC1s += Abc_TtIsConst1(pSim, nWords);
+        Vec_MemHashInsert( vStore, pSim );
+    }
+    nUnique = Vec_MemEntryNum( vStore );
+    printf( "Simulating %d patterns through the second (flat) AIG leads to %d unique objects (%.2f %% out of %d). Const0 = %d. Const1 = %d.\n", 
+        64*nWords, nUnique, 100.0*nUnique/Gia_ManCandNum(pFlat), Gia_ManCandNum(pFlat), nC0s, nC1s );
+
+    assert( Gia_ManCiNum(pFlat) == Gia_ManCiNum(pHie) );
+    Gia_ManForEachCand( pHie, pObj, i ) 
+    {
+        word * pSim = Vec_WrdEntryP(vSims1, i*nWords);
+        pSpot  = Vec_MemHashLookup( vStore, pSim );
+        Abc_TtNot( pSim, nWords );
+        pSpot2 = Vec_MemHashLookup( vStore, pSim );
+        Abc_TtNot( pSim, nWords );
+        nBoundary += Gia_ObjIsBuf(pObj);
+        if ( *pSpot != -1 || *pSpot2 != -1 )
+        {
+            nMatched++;
+            continue;
+        }
+        //Extra_PrintBinary( stdout, (unsigned *)pSim, 64*nWords ); printf("\n");
+        nFound[1] += Gia_ObjIsBuf(pObj);
+        nFound[2]++;
+        //if ( Gia_ObjIsBuf(pObj) )
+        //    printf( "%d(%d) ", i, nBoundary-1 );
+    }
+    Vec_MemHashFree( vStore );
+    Vec_MemFree( vStore );
+    Vec_WrdFree( vSims0 );
+    Vec_WrdFree( vSims1 );
+
+    printf( "The first (hierarchical) AIG has %d (%.2f %%) matches, %d (%.2f %%) mismatches, including %d (%.2f %%) on the boundary.  ", 
+        nMatched,  100.0*nMatched /Abc_MaxInt(1, Gia_ManCandNum(pHie)), 
+        nFound[2], 100.0*nFound[2]/Abc_MaxInt(1, Gia_ManCandNum(pHie)), 
+        nFound[1], 100.0*nFound[1]/Abc_MaxInt(1, nBoundary) );
+    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////