Version abc81013

6 files changed, 220 insertions, 135 deletions

diff --git a/src/aig/saig/module.make b/src/aig/saig/module.make
index c3c0a1b6..48d91438 100644
--- a/src/aig/saig/module.make
+++ b/src/aig/saig/module.make
@@ -3,6 +3,7 @@ SRC +=    src/aig/saig/saigAbs.c \
     src/aig/saig/saigCone.c \
     src/aig/saig/saigDup.c \
     src/aig/saig/saigHaig.c \
+    src/aig/saig/saigInd.c \
     src/aig/saig/saigIoa.c \
     src/aig/saig/saigLoc.c \
     src/aig/saig/saigMiter.c \
diff --git a/src/aig/saig/saig.h b/src/aig/saig/saig.h
index ddae07e0..f0c8fb54 100644
--- a/src/aig/saig/saig.h
+++ b/src/aig/saig/saig.h
@@ -87,6 +87,8 @@ extern Aig_Man_t *       Said_ManDupOrpos( Aig_Man_t * p );
 extern Aig_Man_t *       Saig_ManAbstraction( Aig_Man_t * pAig, Vec_Int_t * vFlops );
 /*=== saigHaig.c ==========================================================*/
 extern Aig_Man_t *       Saig_ManHaigRecord( Aig_Man_t * p, int nIters, int nSteps, int fRetimingOnly, int fAddBugs, int fUseCnf, int fVerbose );
+/*=== saigInd.c ==========================================================*/
+extern int               Saig_ManInduction( Aig_Man_t * p, int nFramesMax, int nConfMax, int fVerbose );
 /*=== saigIoa.c ==========================================================*/
 extern void              Saig_ManDumpBlif( Aig_Man_t * p, char * pFileName );
 extern Aig_Man_t *       Saig_ManReadBlif( char * pFileName );
diff --git a/src/aig/saig/saigAbs.c b/src/aig/saig/saigAbs.c
index 48a26a3c..b1e36fcc 100644
--- a/src/aig/saig/saigAbs.c
+++ b/src/aig/saig/saigAbs.c
@@ -51,7 +51,7 @@ Aig_Man_t * Saig_ManFramesBmcLast( Aig_Man_t * pAig, int nFrames, Aig_Obj_t ***
 {
     Aig_Man_t * pFrames;
     Aig_Obj_t ** ppMap;
-    Aig_Obj_t * pObj, * pObjLi, * pObjLo;
+    Aig_Obj_t * pObj, * pObjLi, * pObjLo, * pResult;
     int i, f;
     assert( Saig_ManRegNum(pAig) > 0 );
     // start the mapping
@@ -61,10 +61,12 @@ Aig_Man_t * Saig_ManFramesBmcLast( Aig_Man_t * pAig, int nFrames, Aig_Obj_t ***
     // create variables for register outputs
     Saig_ManForEachLo( pAig, pObj, i )
     {
-        pObj->pData = Aig_ManConst0( pFrames );
+//        pObj->pData = Aig_ManConst0( pFrames );
+        pObj->pData = Aig_ObjCreatePi( pFrames );
         Saig_ObjSetFrame( ppMap, nFrames, pObj, 0, pObj->pData );
     }
     // add timeframes
+    pResult = Aig_ManConst0(pFrames);
     for ( f = 0; f < nFrames; f++ )
     {
         // map the constant node
@@ -82,14 +84,17 @@ Aig_Man_t * Saig_ManFramesBmcLast( Aig_Man_t * pAig, int nFrames, Aig_Obj_t ***
             pObj->pData = Aig_And( pFrames, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
             Saig_ObjSetFrame( ppMap, nFrames, pObj, f, pObj->pData );
         }
+        // OR the POs
+        Saig_ManForEachPo( pAig, pObj, i )
+            pResult = Aig_Or( pFrames, pResult, Aig_ObjChild0Copy(pObj) );
         // create POs for this frame
         if ( f == nFrames - 1 )
         {
-            Saig_ManForEachPo( pAig, pObj, i )
-            {
-                pObj->pData = Aig_ObjCreatePo( pFrames, Aig_ObjChild0Copy(pObj) );
-                Saig_ObjSetFrame( ppMap, nFrames, pObj, f, pObj->pData );
-            }
+//            Saig_ManForEachPo( pAig, pObj, i )
+//            {
+//               pObj->pData = Aig_ObjCreatePo( pFrames, Aig_ObjChild0Copy(pObj) );
+//               Saig_ObjSetFrame( ppMap, nFrames, pObj, f, pObj->pData );
+//            }
             break;
         }
         // save register inputs
@@ -105,6 +110,7 @@ Aig_Man_t * Saig_ManFramesBmcLast( Aig_Man_t * pAig, int nFrames, Aig_Obj_t ***
             Saig_ObjSetFrame( ppMap, nFrames, pObjLo, f, pObjLo->pData );
         }
     }
+    Aig_ObjCreatePo( pFrames, pResult );
     Aig_ManCleanup( pFrames );
     // remove mapping for the nodes that are no longer there
     for ( i = 0; i < Aig_ManObjNumMax(pAig) * nFrames; i++ )
@@ -124,14 +130,15 @@ Aig_Man_t * Saig_ManFramesBmcLast( Aig_Man_t * pAig, int nFrames, Aig_Obj_t ***
   SeeAlso     []
 
 ***********************************************************************/
-int * Saig_ManFindUnsatVariables( Cnf_Dat_t * pCnf, int nConfMax, int fVerbose )
+int * Saig_ManFindUnsatVariables( Cnf_Dat_t * pCnf, int nRegs, int nConfMax, int fVerbose )
 {
     void * pSatCnf; 
     Intp_Man_t * pManProof;
+    Aig_Obj_t * pObj;
     sat_solver * pSat;
     Vec_Int_t * vCore;
     int * pClause1, * pClause2, * pLit, * pVars, iClause, nVars;
-    int i, RetValue;
+    int i, Lit, RetValue;
     // create the SAT solver
     pSat = sat_solver_new();
     sat_solver_store_alloc( pSat ); 
@@ -145,6 +152,15 @@ int * Saig_ManFindUnsatVariables( Cnf_Dat_t * pCnf, int nConfMax, int fVerbose )
             return NULL;
         }
     }
+    Aig_ManForEachPi( pCnf->pMan, pObj, i )
+    {
+        if ( i == nRegs )
+            break;
+        assert( pCnf->pVarNums[pObj->Id] >= 0 );
+        Lit = toLitCond( pCnf->pVarNums[pObj->Id], 1 );
+        if ( !sat_solver_addclause( pSat, &Lit, &Lit+1 ) )
+            assert( 0 );
+    }
     sat_solver_store_mark_roots( pSat ); 
     // solve the problem
     RetValue = sat_solver_solve( pSat, NULL, NULL, (sint64)nConfMax, (sint64)0, (sint64)0, (sint64)0 );
@@ -240,11 +256,12 @@ Aig_Man_t * Saig_ManProofAbstraction( Aig_Man_t * p, int nFrames, int nConfMax,
         printf( "Performing proof-based abstraction with %d frames and %d max conflicts.\n", nFrames, nConfMax );
     // create the timeframes
     pFrames = Saig_ManFramesBmcLast( p, nFrames, &ppAigToFrames );
+    printf( "AIG nodes = %d. Frames = %d.\n", Aig_ManNodeNum(p), Aig_ManNodeNum(pFrames) );
     // convert them into CNF
 //    pCnf = Cnf_Derive( pFrames, 0 );
     pCnf = Cnf_DeriveSimple( pFrames, 0 );
     // collect CNF variables involved in UNSAT core
-    pUnsatCoreVars = Saig_ManFindUnsatVariables( pCnf, nConfMax, 0 );
+    pUnsatCoreVars = Saig_ManFindUnsatVariables( pCnf, Saig_ManRegNum(p), nConfMax, 0 );
     if ( pUnsatCoreVars == NULL )
     {
         Aig_ManStop( pFrames );
diff --git a/src/aig/saig/saigBmc.c b/src/aig/saig/saigBmc.c
index baf00241..5776cd4a 100644
--- a/src/aig/saig/saigBmc.c
+++ b/src/aig/saig/saigBmc.c
@@ -249,8 +249,10 @@ int Saig_ManBmcSimple( Aig_Man_t * pAig, int nFrames, int nSizeMax, int nConfLim
         {
             Lit = toLitCond( pCnf->pVarNums[pObj->Id], 0 );
             if ( fVerbose )
+            {
                 printf( "Solving output %2d of frame %3d ... \r", 
                     i % Saig_ManPoNum(pAig), i / Saig_ManPoNum(pAig) );
+            }
             clk = clock();
             status = sat_solver_solve( pSat, &Lit, &Lit + 1, (sint64)nConfLimit, (sint64)0, (sint64)0, (sint64)0 );
             if ( fVerbose && (i % Saig_ManPoNum(pAig) == Saig_ManPoNum(pAig) - 1) )
@@ -258,12 +260,22 @@ int Saig_ManBmcSimple( Aig_Man_t * pAig, int nFrames, int nSizeMax, int nConfLim
                 printf( "Solved %2d outputs of frame %3d.  ", 
                     Saig_ManPoNum(pAig), i / Saig_ManPoNum(pAig) );
                 printf( "Conf =%8.0f. Imp =%11.0f. ", (double)pSat->stats.conflicts, (double)pSat->stats.propagations );
-                PRT( "Time", clock() - clkPart );
+                PRT( "T", clock() - clkPart );
                 clkPart = clock();
                 fflush( stdout );
             }
             if ( status == l_False )
             {
+/*
+                Lit = lit_neg( Lit );
+                RetValue = sat_solver_addclause( pSat, &Lit, &Lit + 1 );
+                assert( RetValue );
+                if ( pSat->qtail != pSat->qhead )
+                {
+                    RetValue = sat_solver_simplify(pSat);
+                    assert( RetValue );
+                }
+*/
             }
             else if ( status == l_True )
             {
diff --git a/src/aig/saig/saigInd.c b/src/aig/saig/saigInd.c
new file mode 100644
index 00000000..69c250f6
--- /dev/null
+++ b/src/aig/saig/saigInd.c
@@ -0,0 +1,174 @@
+/**CFile****************************************************************
+
+  FileName    [saigLoc.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Sequential AIG package.]
+
+  Synopsis    [K-step induction for one property only.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: saigLoc.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "saig.h"
+#include "cnf.h"
+#include "satSolver.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Performs localization by unrolling timeframes backward.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Saig_ManInduction( Aig_Man_t * p, int nFramesMax, int nConfMax, int fVerbose )
+{
+    sat_solver * pSat;
+    Aig_Man_t * pAigPart;
+    Cnf_Dat_t * pCnfPart;
+    Vec_Int_t * vTopVarNums;
+    Vec_Ptr_t * vTop, * vBot;
+    Aig_Obj_t * pObjPi, * pObjPiCopy, * pObjPo;
+    int i, f, clk, Lits[2], status, RetValue, nSatVarNum, nConfPrev;
+    assert( Saig_ManPoNum(p) == 1 );
+    Aig_ManSetPioNumbers( p );
+
+    // start the top by including the PO
+    vBot = Vec_PtrAlloc( 100 );
+    vTop = Vec_PtrAlloc( 100 );
+    Vec_PtrPush( vTop, Aig_ManPo(p, 0) );
+    // start the array of CNF variables
+    vTopVarNums = Vec_IntAlloc( 100 );
+    // start the solver
+    pSat = sat_solver_new();
+    sat_solver_setnvars( pSat, 1000 );
+
+    // iterate backward unrolling
+    RetValue = -1;
+    nSatVarNum = 0;
+    if ( fVerbose )
+        printf( "Localization parameters: FramesMax = %5d. ConflictMax = %6d.\n", nFramesMax, nConfMax );
+    for ( f = 0; ; f++ )
+    { 
+        if ( f > 0 )
+        {
+            Aig_ManStop( pAigPart );
+            Cnf_DataFree( pCnfPart );
+        }
+        clk = clock();
+        // get the bottom
+        Aig_SupportNodes( p, (Aig_Obj_t **)Vec_PtrArray(vTop), Vec_PtrSize(vTop), vBot );
+        // derive AIG for the part between top and bottom
+        pAigPart = Aig_ManDupSimpleDfsPart( p, vBot, vTop );
+        // convert it into CNF
+        pCnfPart = Cnf_Derive( pAigPart, Aig_ManPoNum(pAigPart) );
+        Cnf_DataLift( pCnfPart, nSatVarNum );
+        nSatVarNum += pCnfPart->nVars;
+
+        // stitch variables of top and bot
+        assert( Aig_ManPoNum(pAigPart)-1 == Vec_IntSize(vTopVarNums) );
+        Aig_ManForEachPo( pAigPart, pObjPo, i )
+        {
+            if ( i == 0 )
+            {
+                // do not perform inductive strengthening
+//                if ( f > 0 )
+//                    continue;
+                // add topmost literal
+                Lits[0] = toLitCond( pCnfPart->pVarNums[pObjPo->Id], f>0 );
+                if ( !sat_solver_addclause( pSat, Lits, Lits+1 ) )
+                    assert( 0 );
+                continue;
+            }
+            Lits[0] = toLitCond( Vec_IntEntry(vTopVarNums, i-1), 0 );
+            Lits[1] = toLitCond( pCnfPart->pVarNums[pObjPo->Id], 1 );
+            if ( !sat_solver_addclause( pSat, Lits, Lits+2 ) )
+                assert( 0 );
+            Lits[0] = toLitCond( Vec_IntEntry(vTopVarNums, i-1), 1 );
+            Lits[1] = toLitCond( pCnfPart->pVarNums[pObjPo->Id], 0 );
+            if ( !sat_solver_addclause( pSat, Lits, Lits+2 ) )
+                assert( 0 );
+        }
+        // add CNF to the SAT solver
+        for ( i = 0; i < pCnfPart->nClauses; i++ )
+            if ( !sat_solver_addclause( pSat, pCnfPart->pClauses[i], pCnfPart->pClauses[i+1] ) )
+                break;
+        if ( i < pCnfPart->nClauses )
+        {
+//            printf( "SAT solver became UNSAT after adding clauses.\n" );
+            RetValue = 1;
+            break;
+        }
+        // run the SAT solver
+        nConfPrev = pSat->stats.conflicts;
+        status = sat_solver_solve( pSat, NULL, NULL, (sint64)nConfMax, 0, 0, 0 );
+        if ( fVerbose )
+        {
+            printf( "%3d : PI = %5d. PO = %5d. AIG = %5d. Var = %6d. Conf = %6d. ",
+                f+1, Aig_ManPiNum(pAigPart), Aig_ManPoNum(pAigPart), Aig_ManNodeNum(pAigPart), 
+                nSatVarNum, pSat->stats.conflicts-nConfPrev );
+            PRT( "Time", clock() - clk );
+        }
+        if ( status == l_Undef )
+            break;
+        if ( status == l_False )
+        {
+            RetValue = 1;
+            break;
+        }
+        assert( status == l_True );
+        if ( f == nFramesMax - 1 )
+            break;
+        // the problem is SAT - add more clauses
+        // create new set of POs to derive new top
+        Vec_PtrClear( vTop );
+        Vec_PtrPush( vTop, Aig_ManPo(p, 0) );
+        Vec_IntClear( vTopVarNums );
+        Vec_PtrForEachEntry( vBot, pObjPi, i )
+        {
+            assert( Aig_ObjIsPi(pObjPi) );
+            if ( Saig_ObjIsLo(p, pObjPi) )
+            {
+                pObjPiCopy = pObjPi->pData;
+                assert( pObjPiCopy != NULL );
+                Vec_PtrPush( vTop, Saig_ObjLoToLi(p, pObjPi) );
+                Vec_IntPush( vTopVarNums, pCnfPart->pVarNums[pObjPiCopy->Id] );
+            }
+        }
+    }
+//    printf( "Completed %d interations.\n", f+1 );
+    // cleanup
+    sat_solver_delete( pSat );
+    Aig_ManStop( pAigPart );
+    Cnf_DataFree( pCnfPart );
+    Vec_IntFree( vTopVarNums );
+    Vec_PtrFree( vTop );
+    Vec_PtrFree( vBot );
+    return RetValue;
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/aig/saig/saigLoc.c b/src/aig/saig/saigLoc.c
index 60c547dd..edbf231c 100644
--- a/src/aig/saig/saigLoc.c
+++ b/src/aig/saig/saigLoc.c
@@ -6,7 +6,7 @@
 
   PackageName [Sequential AIG package.]
 
-  Synopsis    [Localization package.]
+  Synopsis    [Localization.]
 
   Author      [Alan Mishchenko]
   
@@ -19,8 +19,6 @@
 ***********************************************************************/
 
 #include "saig.h"
-#include "cnf.h"
-#include "satSolver.h"
 
 ////////////////////////////////////////////////////////////////////////
 ///                        DECLARATIONS                              ///
@@ -32,7 +30,7 @@
 
 /**Function*************************************************************
 
-  Synopsis    [Performs localization by unrolling timeframes backward.]
+  Synopsis    []
 
   Description []
                
@@ -41,126 +39,7 @@
   SeeAlso     []
 
 ***********************************************************************/
-int Saig_ManLocalization( Aig_Man_t * p, int nFramesMax, int nConfMax, int fVerbose )
-{
-    sat_solver * pSat;
-    Vec_Int_t * vTopVarNums;
-    Vec_Ptr_t * vTop, * vBot;
-    Cnf_Dat_t * pCnfTop, * pCnfBot;
-    Aig_Man_t * pPartTop, * pPartBot;
-    Aig_Obj_t * pObj, * pObjBot;
-    int i, f, clk, Lits[2], status, RetValue, nSatVarNum, nConfPrev;
-    assert( Saig_ManPoNum(p) == 1 );
-    Aig_ManSetPioNumbers( p );
-
-    // start the top by including the PO
-    vBot = Vec_PtrAlloc( 100 );
-    vTop = Vec_PtrAlloc( 100 );
-    Vec_PtrPush( vTop, Aig_ManPo(p, 0) );
-    // create the manager composed of one PI/PO pair
-    pPartTop = Aig_ManStart( 10 );
-    Aig_ObjCreatePo( pPartTop, Aig_ObjCreatePi(pPartTop) );
-    pCnfTop = Cnf_Derive( pPartTop, 0 );
-    // start the array of CNF variables
-    vTopVarNums = Vec_IntAlloc( 100 );
-    Vec_IntPush( vTopVarNums, pCnfTop->pVarNums[Aig_ManPi(pPartTop,0)->Id] );
-    // start the solver
-    pSat = Cnf_DataWriteIntoSolver( pCnfTop, 1, 0 );
-
-    // iterate backward unrolling
-    RetValue = -1;
-    nSatVarNum = pCnfTop->nVars;
-    if ( fVerbose )
-        printf( "Localization parameters: FramesMax = %5d. ConflictMax = %6d.\n", nFramesMax, nConfMax );
-    for ( f = 0; ; f++ )
-    { 
-        clk = clock();
-        // get the bottom
-        Aig_SupportNodes( p, (Aig_Obj_t **)Vec_PtrArray(vTop), Vec_PtrSize(vTop), vBot );
-        // derive AIG for the part between top and bottom
-        pPartBot = Aig_ManDupSimpleDfsPart( p, vBot, vTop );
-        // convert it into CNF
-        pCnfBot = Cnf_Derive( pPartBot, Aig_ManPoNum(pPartBot) );
-        Cnf_DataLift( pCnfBot, nSatVarNum );
-        nSatVarNum += pCnfBot->nVars;
-        // stitch variables of top and bot
-        assert( Aig_ManPoNum(pPartBot) == Vec_IntSize(vTopVarNums) );
-        Aig_ManForEachPo( pPartBot, pObjBot, i )
-        {
-            Lits[0] = toLitCond( Vec_IntEntry(vTopVarNums, i),   0 );
-            Lits[1] = toLitCond( pCnfBot->pVarNums[pObjBot->Id], 1 );
-            if ( !sat_solver_addclause( pSat, Lits, Lits+2 ) )
-                assert( 0 );
-            Lits[0] = toLitCond( Vec_IntEntry(vTopVarNums, i),   1 );
-            Lits[1] = toLitCond( pCnfBot->pVarNums[pObjBot->Id], 0 );
-            if ( !sat_solver_addclause( pSat, Lits, Lits+2 ) )
-                assert( 0 );
-        }
-        // add CNF to the SAT solver
-        for ( i = 0; i < pCnfBot->nClauses; i++ )
-            if ( !sat_solver_addclause( pSat, pCnfBot->pClauses[i], pCnfBot->pClauses[i+1] ) )
-                break;
-        if ( i < pCnfBot->nClauses )
-        {
-//            printf( "SAT solver became UNSAT after adding clauses.\n" );
-            RetValue = 1;
-            break;
-        }
-        // run the SAT solver
-        nConfPrev = pSat->stats.conflicts;
-        status = sat_solver_solve( pSat, NULL, NULL, (sint64)nConfMax, 0, 0, 0 );
-        if ( fVerbose )
-        {
-            printf( "%3d : PI = %5d. PO = %5d. AIG = %5d. Var = %6d. Conf = %6d. ",
-                f+1, Aig_ManPiNum(pPartBot), Aig_ManPoNum(pPartBot), Aig_ManNodeNum(pPartBot), 
-                nSatVarNum, pSat->stats.conflicts-nConfPrev );
-            PRT( "Time", clock() - clk );
-        }
-        if ( status == l_Undef )
-            break;
-        if ( status == l_False )
-        {
-            RetValue = 1;
-            break;
-        }
-        assert( status == l_True );
-        if ( f == nFramesMax - 1 )
-            break;
-        // the problem is SAT - add more clauses
-        // create new set of POs to derive new top
-        Vec_PtrClear( vTop );
-        Vec_IntClear( vTopVarNums );
-        Vec_PtrForEachEntry( vBot, pObj, i )
-        {
-            assert( Aig_ObjIsPi(pObj) );
-            if ( Saig_ObjIsLo(p, pObj) )
-            {
-                pObjBot = pObj->pData;
-                assert( pObjBot != NULL );
-                Vec_PtrPush( vTop, Saig_ObjLoToLi(p, pObj) );
-                Vec_IntPush( vTopVarNums, pCnfBot->pVarNums[pObjBot->Id] );
-            }
-        }
-        // remove old top and replace it by bottom
-        Aig_ManStop( pPartTop );
-        pPartTop = pPartBot;
-        pPartBot = NULL;
-        Cnf_DataFree( pCnfTop );
-        pCnfTop = pCnfBot;
-        pCnfBot = NULL;
-    }
-//    printf( "Completed %d interations.\n", f+1 );
-    // cleanup
-    sat_solver_delete( pSat );
-    Aig_ManStop( pPartTop );
-    Cnf_DataFree( pCnfTop );
-    Aig_ManStop( pPartBot );
-    Cnf_DataFree( pCnfBot );
-    Vec_IntFree( vTopVarNums );
-    Vec_PtrFree( vTop );
-    Vec_PtrFree( vBot );
-    return RetValue;
-}
+
 
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///