New command &genqbf to dump the QBF miter for ind inv computation.

3 files changed, 241 insertions, 2 deletions

diff --git a/src/aig/gia/giaQbf.c b/src/aig/gia/giaQbf.c
index b7d678b3..1fcdd8c5 100644
--- a/src/aig/gia/giaQbf.c
+++ b/src/aig/gia/giaQbf.c
@@ -56,6 +56,126 @@ extern Cnf_Dat_t * Mf_ManGenerateCnf( Gia_Man_t * pGia, int nLutSize, int fCnfOb
 
 /**Function*************************************************************
 
+  Synopsis    [Generating QBF miter to solve the induction problem.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_GenCollectFlopIndexes( char * pStr, int nLutNum, int nLutSize, int nFlops )
+{
+    int nDups;
+    char * pTemp;
+    Vec_Int_t * vFlops;
+    assert( nLutSize * nLutNum <= nFlops );
+    if ( pStr == NULL )
+        return Vec_IntStartNatural( nLutNum * nLutSize );
+    vFlops = Vec_IntAlloc( nLutNum * nLutSize );
+    pTemp = strtok( pStr, ", " );
+    while ( pTemp )
+    {
+        int iFlop = atoi(pTemp);
+        if ( iFlop >= nFlops )
+        {
+            printf( "Flop index (%d) exceeds the number of flops (%d).\n", iFlop, nFlops );
+            break;
+        }
+        Vec_IntPush( vFlops, iFlop );
+        pTemp = strtok( NULL, ", " );
+    }
+    if ( Vec_IntSize(vFlops) != nLutNum * nLutSize )
+    {
+        printf( "Gia_GenCollectFlopIndexes: Expecting %d flop indexes (instead of %d).\n", nLutNum * nLutSize, Vec_IntSize(vFlops) );
+        Vec_IntFree( vFlops );
+        return NULL;
+    }
+    nDups = Vec_IntCountDuplicates(vFlops);
+    if ( nDups )
+    {
+        printf( "Gia_GenCollectFlopIndexes: There are %d duplicated flops in the list.\n", nDups );
+        Vec_IntFree( vFlops );
+        return NULL;
+    }
+    return vFlops;
+}
+int Gia_GenCreateMux_rec( Gia_Man_t * pNew, int * pCtrl, int nCtrl, Vec_Int_t * vData, int Shift )
+{
+    int iLit0, iLit1;
+    if ( nCtrl == 0 )
+        return Vec_IntEntry( vData, Shift );
+    iLit0 = Gia_GenCreateMux_rec( pNew, pCtrl, nCtrl-1, vData, Shift );
+    iLit1 = Gia_GenCreateMux_rec( pNew, pCtrl, nCtrl-1, vData, Shift + (1<<(nCtrl-1)) );
+    return Gia_ManHashMux( pNew, pCtrl[nCtrl-1], iLit1, iLit0 );
+}
+Vec_Int_t * Gia_GenCreateMuxes( Gia_Man_t * p, Gia_Man_t * pNew, Vec_Int_t * vFlops, int nLutNum, int nLutSize, Vec_Int_t * vParLits, int fUseRi )
+{
+    Vec_Int_t * vLits = Vec_IntAlloc( nLutNum );
+    int i, k, iMux, iFlop, pCtrl[16];
+    int nPars = nLutNum * (1 << nLutSize);
+    // add MUXes for each group of flops
+    assert( Vec_IntSize(vFlops) == nLutNum * nLutSize );
+    for ( i = 0; i < nLutNum; i++ )
+    {
+        for ( k = 0; k < nLutSize; k++ )
+        {
+            iFlop = Vec_IntEntry(vFlops, i * nLutSize + k);
+            assert( iFlop >= 0 && iFlop < Gia_ManRegNum(p) );
+            if ( fUseRi )
+                pCtrl[k] = Gia_ManRi(p, iFlop)->Value;
+            else
+                pCtrl[k] = Gia_ManRo(p, iFlop)->Value;
+        }
+        iMux = Gia_GenCreateMux_rec( pNew, pCtrl, nLutSize, vParLits, i * (1 << nLutSize) );
+        Vec_IntPush( vLits, iMux );
+    }
+    return vLits;
+}
+Gia_Man_t * Gia_GenQbfMiter( Gia_Man_t * p, int nFrames, int nLutNum, int nLutSize, char * pStr, int fVerbose )
+{
+    Gia_Obj_t * pObj; 
+    Gia_Man_t * pTemp, * pNew;
+    int i, iMiter, nPars = nLutNum * (1 << nLutSize);
+    Vec_Int_t * vLits0, * vLits1, * vParLits;
+    Vec_Int_t * vFlops = Gia_GenCollectFlopIndexes( pStr, nLutNum, nLutSize, Gia_ManRegNum(p) );
+    // collect parameter literals (data vars)
+    vParLits = Vec_IntAlloc( nPars );
+    for ( i = 0; i < nPars; i++ )
+        Vec_IntPush( vParLits, i ? Abc_Var2Lit(i+1, 0) : 1 );
+    // create new manager
+    pNew = Gia_ManStart( Gia_ManObjNum(p) );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    Gia_ManHashAlloc( pNew );
+    Gia_ManConst0(p)->Value = 0;
+    for ( i = 0; i < nPars; i++ )
+        Gia_ManAppendCi( pNew );
+    Gia_ManForEachCi( p, pObj, i )
+        pObj->Value = Gia_ManAppendCi( pNew );
+    Gia_ManForEachAnd( p, pObj, i )
+        pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+    Gia_ManForEachCo( p, pObj, i )
+        pObj->Value = Gia_ObjFanin0Copy(pObj);
+    vLits0 = Gia_GenCreateMuxes( p, pNew, vFlops, nLutNum, nLutSize, vParLits, 0 );
+    vLits1 = Gia_GenCreateMuxes( p, pNew, vFlops, nLutNum, nLutSize, vParLits, 1 );
+    // create miter output
+    iMiter = Gia_ManHashAnd( pNew, Vec_IntEntry(vLits0, 0), Abc_LitNot(Vec_IntEntry(vLits1, 0)) );
+    iMiter = Gia_ManHashAnd( pNew, Abc_LitNot(iMiter), Abc_Var2Lit(1, 0) );
+    Gia_ManAppendCo( pNew, iMiter );
+    // cleanup
+    Vec_IntFree( vLits0 );
+    Vec_IntFree( vLits1 );
+    Vec_IntFree( vFlops );
+    Vec_IntFree( vParLits );
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    return pNew;
+}
+
+/**Function*************************************************************
+
   Synopsis    [Naive way to enumerate SAT assignments.]
 
   Description []
@@ -455,10 +575,11 @@ int Gia_QbfSolve( Gia_Man_t * pGia, int nPars, int nIterLimit, int nConfLimit, i
     }
     if ( RetValue == 0 )
     {
+        int nZeros = Vec_IntCountZero( p->vValues );
         printf( "Parameters: " );
         assert( Vec_IntSize(p->vValues) == nPars );
         Vec_IntPrintBinary( p->vValues );
-        printf( "\n" );
+        printf( "  Statistics: 0=%d 1=%d\n", nZeros, Vec_IntSize(p->vValues) - nZeros );
     }
     if ( RetValue == -1 && nTimeOut && (Abc_Clock() - p->clkStart)/CLOCKS_PER_SEC >= nTimeOut )
         printf( "The problem timed out after %d sec.  ", nTimeOut );
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index d99c9c0e..88fd8393 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -438,6 +438,7 @@ static int Abc_CommandAbc9ICheck             ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandAbc9SatTest            ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9FFTest             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Qbf                ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandAbc9GenQbf             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9SatFx              ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Inse               ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Maxi               ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -1046,6 +1047,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "ABC9",         "&sattest",      Abc_CommandAbc9SatTest,      0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&fftest",       Abc_CommandAbc9FFTest,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&qbf",          Abc_CommandAbc9Qbf,          0 );
+    Cmd_CommandAdd( pAbc, "ABC9",         "&genqbf",       Abc_CommandAbc9GenQbf,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&satfx",        Abc_CommandAbc9SatFx,        0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&inse",         Abc_CommandAbc9Inse,         0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&maxi",         Abc_CommandAbc9Maxi,         0 );
@@ -36763,6 +36765,121 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandAbc9GenQbf( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern Gia_Man_t * Gia_GenQbfMiter( Gia_Man_t * pGia, int nFrames, int nLutNum, int nLutSize, char * pStr, int fVerbose );
+    int nFrames   =    1;
+    int nLutNum   =    1;
+    int nLutSize  =    6;
+    char * pStr   = NULL;
+    int fVerbose  =    0;
+    int c;
+    Gia_Man_t * pTemp;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "FKNSvh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'F':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-F\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nFrames = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nFrames < 0 )
+                goto usage;
+            break;
+        case 'K':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-K\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nLutSize = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nLutSize < 0 )
+                goto usage;
+            break;
+        case 'N':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-N\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nLutNum = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nLutNum < 0 )
+                goto usage;
+            break;
+        case 'S':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-N\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            pStr = Abc_UtilStrsav(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( pStr == NULL )
+                goto usage;
+            break;
+        case 'v':
+            fVerbose ^= 1;
+            break;
+        case 'h':
+            goto usage;
+        default:
+            goto usage;
+        }
+    }
+    if ( pAbc->pGia == NULL )
+    {
+        Abc_Print( -1, "There is no current GIA.\n" );
+        return 1;
+    }
+    if ( Gia_ManRegNum(pAbc->pGia) == 0 )
+    {
+        Abc_Print( -1, "Works only for sequential networks.\n" );
+        return 1;
+    }
+    if ( Gia_ManRegNum(pAbc->pGia) < nLutSize * nLutNum )
+    {
+        Abc_Print( -1, "The number of flops (%d) is less than required (%d).\n", Gia_ManRegNum(pAbc->pGia), nLutSize * nLutNum );
+        return 1;
+    }
+    if ( nFrames != 1 || nLutNum != 1 )
+    {
+        Abc_Print( -1, "Currently this commands works for one frame and one LUT.\n" );
+        return 1;
+    }
+    pTemp = Gia_GenQbfMiter( pAbc->pGia, nFrames, nLutNum, nLutSize, pStr, fVerbose );
+    Abc_FrameUpdateGia( pAbc, pTemp );
+    ABC_FREE( pStr );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: &genqbf [-FKN num] [-vh]\n" );
+    Abc_Print( -2, "\t         generates QBF miter for computing an inductive invariant\n" );
+    Abc_Print( -2, "\t-F num : the number of time frames for induction [default = %d]\n", nFrames );
+    Abc_Print( -2, "\t-K num : the LUT size [default = %d]\n", nLutSize );
+    Abc_Print( -2, "\t-N num : the number of LUTs [default = %d]\n", nLutNum );
+    Abc_Print( -2, "\t-v     : toggle verbose output [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h     : print the command usage\n");
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandAbc9SatFx( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     extern int Bmc_FxCompute( Gia_Man_t * p );
diff --git a/src/base/abci/abcQbf.c b/src/base/abci/abcQbf.c
index 81c80b13..aa67ad74 100644
--- a/src/base/abci/abcQbf.c
+++ b/src/base/abci/abcQbf.c
@@ -202,9 +202,10 @@ clkV = Abc_Clock() - clkV;
     // report the results
     if ( fFound )
     {
+        int nZeros = Vec_IntCountZero( vPiValues );
         printf( "Parameters: " );
         Abc_NtkVectorPrintPars( vPiValues, nPars );
-        printf( "\n" );
+        printf( "  Statistics: 0=%d 1=%d\n", nZeros, Vec_IntSize(vPiValues) - nZeros );
         printf( "Solved after %d interations.  ", nIters );
     }
     else if ( nIters == nItersMax )