Procedure to compute truth tables for POs of GIA.

4 files changed, 199 insertions, 2 deletions

diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h
index e56e88aa..a5c075c3 100644
--- a/src/aig/gia/gia.h
+++ b/src/aig/gia/gia.h
@@ -155,6 +155,10 @@ struct Gia_Man_t_
     word           nHashHit;      // hash table hit
     word           nHashMiss;     // hash table miss
     int            fVerbose;      // verbose reports
+    Vec_Wrd_t *    vTtMemory;     // truth table memory
+    int            nTtVars;       // truth table variables
+    int            nTtWords;      // truth table words
+    int            iTtNum;        // truth table current number
 };
 
 
@@ -942,6 +946,7 @@ extern Vec_Int_t *         Gia_VtaConvertToGla( Gia_Man_t * p, Vec_Int_t * vVta
 extern Vec_Int_t *         Gia_VtaConvertFromGla( Gia_Man_t * p, Vec_Int_t * vGla, int nFrames );
 extern Vec_Int_t *         Gia_FlaConvertToGla( Gia_Man_t * p, Vec_Int_t * vFla );
 extern Vec_Int_t *         Gia_GlaConvertToFla( Gia_Man_t * p, Vec_Int_t * vGla );
+extern unsigned *          Gia_ManComputePoTt( Gia_Man_t * p, Gia_Obj_t * pObj );
 
 /*=== giaCTas.c ===========================================================*/
 typedef struct Tas_Man_t_  Tas_Man_t;
diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c
index 61283e09..d610882c 100644
--- a/src/aig/gia/giaMan.c
+++ b/src/aig/gia/giaMan.c
@@ -86,6 +86,7 @@ void Gia_ManStop( Gia_Man_t * p )
     Vec_IntFreeP( &p->vObjClasses );
     Vec_IntFreeP( &p->vLevels );
     Vec_IntFreeP( &p->vTruths );
+    Vec_WrdFreeP( &p->vTtMemory );
     Vec_IntFree( p->vCis );
     Vec_IntFree( p->vCos );
     ABC_FREE( p->pTravIds );
diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c
index 1a6789b5..bef6c229 100644
--- a/src/aig/gia/giaUtil.c
+++ b/src/aig/gia/giaUtil.c
@@ -1431,6 +1431,198 @@ Vec_Int_t * Gia_GlaConvertToFla( Gia_Man_t * p, Vec_Int_t * vGla )
     return vFla;
 }
 
+/**Function*************************************************************
+
+  Synopsis    [Testing the speedup due to grouping POs into batches.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManCollectObjs_rec( Gia_Man_t * p, int iObjId, Vec_Int_t * vObjs, int Limit )
+{
+    Gia_Obj_t * pObj;
+    if ( Vec_IntSize(vObjs) == Limit )
+        return;
+    if ( Gia_ObjIsTravIdCurrentId(p, iObjId) )
+        return;
+    Gia_ObjSetTravIdCurrentId(p, iObjId);
+    pObj = Gia_ManObj( p, iObjId );
+    if ( Gia_ObjIsAnd(pObj) )
+    {
+        Gia_ManCollectObjs_rec( p, Gia_ObjFaninId0p(p, pObj), vObjs, Limit );
+        if ( Vec_IntSize(vObjs) == Limit )
+            return;
+        Gia_ManCollectObjs_rec( p, Gia_ObjFaninId1p(p, pObj), vObjs, Limit );
+        if ( Vec_IntSize(vObjs) == Limit )
+            return;
+    }
+    Vec_IntPush( vObjs, iObjId );
+}
+unsigned * Gia_ManComputePoTruthTables( Gia_Man_t * p, int nBytesMax )
+{
+    int nVars = Gia_ManPiNum(p);
+    int nTruthWords = Abc_TruthWordNum( nVars );
+    int nTruths = nBytesMax / (sizeof(unsigned) * nTruthWords);
+    int nTotalNodes = 0, nRounds = 0;
+    Vec_Int_t * vObjs;
+    Gia_Obj_t * pObj;
+    clock_t clk = clock();
+    int i;
+    printf( "Var = %d. Words = %d. Truths = %d.\n", nVars, nTruthWords, nTruths );
+    vObjs = Vec_IntAlloc( nTruths );
+    Gia_ManIncrementTravId( p );
+    Gia_ManForEachPo( p, pObj, i )
+    {
+        Gia_ManCollectObjs_rec( p, Gia_ObjFaninId0p(p, pObj), vObjs, nTruths );
+        if ( Vec_IntSize(vObjs) == nTruths )
+        {
+            nRounds++;
+//            printf( "%d ", i );
+            nTotalNodes += Vec_IntSize( vObjs );
+            Vec_IntClear( vObjs );
+            Gia_ManIncrementTravId( p );
+        }
+    }
+//    printf( "\n" );
+    nTotalNodes += Vec_IntSize( vObjs );
+    Vec_IntFree( vObjs );
+
+    printf( "Rounds = %d. Objects = %d. Total = %d.   ", nRounds, Gia_ManObjNum(p), nTotalNodes );
+    Abc_PrintTime( 1, "Time", clock() - clk );
+
+    return NULL;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Computing the truth table of one PO.]
+
+  Description [The truth table should be used (or saved into the user's
+  storage) before this procedure is called next time!]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Gia_ManComputePoTt_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
+{
+    word * pTruth0, * pTruth1, * pTruth, * pTruthL;
+    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
+        return pObj->Value;
+    Gia_ObjSetTravIdCurrent(p, pObj);
+    assert( Gia_ObjIsAnd(pObj) );
+    pTruth0 = Vec_WrdArray(p->vTtMemory) + p->nTtWords * Gia_ManComputePoTt_rec( p, Gia_ObjFanin0(pObj) );
+    pTruth1 = Vec_WrdArray(p->vTtMemory) + p->nTtWords * Gia_ManComputePoTt_rec( p, Gia_ObjFanin1(pObj) );
+    assert( p->nTtWords * p->iTtNum < Vec_WrdSize(p->vTtMemory) );
+    pTruth  = Vec_WrdArray(p->vTtMemory) + p->nTtWords * p->iTtNum++;
+    pTruthL = Vec_WrdArray(p->vTtMemory) + p->nTtWords * p->iTtNum;
+    if ( Gia_ObjFaninC0(pObj) )
+    {
+        if ( Gia_ObjFaninC1(pObj) )
+            while ( pTruth < pTruthL )
+                *pTruth++ = ~*pTruth0++ & ~*pTruth1++;
+        else
+            while ( pTruth < pTruthL )
+                *pTruth++ = ~*pTruth0++ &  *pTruth1++;
+    }
+    else
+    {
+        if ( Gia_ObjFaninC1(pObj) )
+            while ( pTruth < pTruthL )
+                *pTruth++ =  *pTruth0++ & ~*pTruth1++;
+        else
+            while ( pTruth < pTruthL )
+                *pTruth++ =  *pTruth0++ &  *pTruth1++;
+    }
+    return p->iTtNum-1;
+}
+unsigned * Gia_ManComputePoTt( Gia_Man_t * p, Gia_Obj_t * pObj )
+{
+    Gia_Obj_t * pTemp;
+    word * pTruth;
+    int i, k;
+    // this procedure works only for primary outputs
+    assert( Gia_ObjIsCo(pObj) );
+    if ( p->vTtMemory == NULL )
+    {
+        word Truth6[7] = {
+            0x0000000000000000,
+            0xAAAAAAAAAAAAAAAA,
+            0xCCCCCCCCCCCCCCCC,
+            0xF0F0F0F0F0F0F0F0,
+            0xFF00FF00FF00FF00,
+            0xFFFF0000FFFF0000,
+            0xFFFFFFFF00000000
+        };
+        p->nTtVars   = Gia_ManPiNum( p );
+        p->nTtWords  = (p->nTtVars <= 6 ? 1 : (1 << (p->nTtVars - 6)));
+        p->vTtMemory = Vec_WrdStart( p->nTtWords * 256 );
+        for ( i = 0; i < 7; i++ )
+            for ( k = 0; k < p->nTtWords; k++ )
+                Vec_WrdWriteEntry( p->vTtMemory, i * p->nTtWords + k, Truth6[i] );
+    }
+    else
+    {
+        // make sure the number of primary inputs did not change 
+        // since the truth table computation storage was prepared
+        assert( p->nTtVars == Gia_ManPiNum(p) );
+    }
+    // mark const and PIs
+    Gia_ManIncrementTravId( p );
+    Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
+    Gia_ManConst0(p)->Value = 0;
+    Gia_ManForEachPi( p, pTemp, i )
+    {
+        Gia_ObjSetTravIdCurrent( p, pTemp );
+        pTemp->Value = i+1;
+    }
+    p->iTtNum = 7;
+    // compute truth table for the fanin node
+    pTruth = Vec_WrdArray(p->vTtMemory) + p->nTtWords * Gia_ManComputePoTt_rec(p, Gia_ObjFanin0(pObj));
+    // complement if needed
+    if ( Gia_ObjFaninC0(pObj) )
+    {
+        word * pTemp = pTruth;
+        assert( p->nTtWords * p->iTtNum < Vec_WrdSize(p->vTtMemory) );
+        pTruth = Vec_WrdArray(p->vTtMemory) + p->nTtWords * p->iTtNum;
+        for ( k = 0; k < p->nTtWords; k++ )
+            pTruth[k] = ~pTemp[k];
+    }
+    return (unsigned *)pTruth;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Testing truth table computation.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManComputePoTtTest( Gia_Man_t * p )
+{
+    Gia_Obj_t * pObj;
+    unsigned * pTruth;
+    clock_t clk = clock();
+    int i;
+    Gia_ManForEachPo( p, pObj, i )
+    {
+        pTruth = Gia_ManComputePoTt( p, pObj );
+//        Extra_PrintHex( stdout, pTruth, Gia_ManPiNum(p) ); printf( "\n" );
+    }
+    Abc_PrintTime( 1, "Time", clock() - clk );
+}
+
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 5e74a943..590e5875 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -28944,8 +28944,7 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
 //    Gia_ManStopP( &pTemp );
 //    Gia_ManSuppSizeTest( pAbc->pGia );
 //    Gia_VtaTest( pAbc->pGia, 10, 100000, 0, 0, 1 );
-
-    Gia_IsoTest( pAbc->pGia, fVerbose );
+//    Gia_IsoTest( pAbc->pGia, fVerbose );
     return 0;
 usage:
     Abc_Print( -2, "usage: &test [-svh]\n" );