summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--abclib.dsp4
-rw-r--r--src/aig/gia/gia.h14
-rw-r--r--src/aig/gia/giaEquiv.c2
-rw-r--r--src/aig/gia/giaSatoko.c2
-rw-r--r--src/aig/gia/giaUtil.c19
-rw-r--r--src/base/abci/abc.c2
-rw-r--r--src/base/wlc/wlcSim.c22
-rw-r--r--src/misc/util/utilTruth.h16
-rw-r--r--src/proof/cec/cecSat.c1003
-rw-r--r--src/proof/cec/module.make1
-rw-r--r--src/sat/bmc/bmcGen.c18
-rw-r--r--src/sat/satoko/cdb.h6
-rw-r--r--src/sat/satoko/cnf_reader.c2
-rw-r--r--src/sat/satoko/satoko.h8
-rw-r--r--src/sat/satoko/solver.c10
-rw-r--r--src/sat/satoko/solver.h6
-rw-r--r--src/sat/satoko/solver_api.c65
-rw-r--r--src/sat/satoko/types.h1
-rw-r--r--src/sat/satoko/utils/heap.h5
-rw-r--r--src/sat/satoko/watch_list.h12
20 files changed, 1172 insertions, 46 deletions
diff --git a/abclib.dsp b/abclib.dsp
index 23c57506..99ade15e 100644
--- a/abclib.dsp
+++ b/abclib.dsp
@@ -5027,6 +5027,10 @@ SOURCE=.\src\proof\cec\cecPat.c
# End Source File
# Begin Source File
+SOURCE=.\src\proof\cec\cecSat.c
+# End Source File
+# Begin Source File
+
SOURCE=.\src\proof\cec\cecSeq.c
# End Source File
# Begin Source File
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h
index c183432a..10804850 100644
--- a/src/aig/gia/gia.h
+++ b/src/aig/gia/gia.h
@@ -194,6 +194,7 @@ struct Gia_Man_t_
int MappedDelay; // delay after mapping
// bit-parallel simulation
int iPatsPi;
+ int nSimWords;
Vec_Wrd_t * vSims;
Vec_Wrd_t * vSimsPi;
Vec_Int_t * vClassOld;
@@ -982,24 +983,26 @@ static inline void Gia_ObjSetNext( Gia_Man_t * p, int Id, int Num ) { p
static inline int Gia_ObjIsConst( Gia_Man_t * p, int Id ) { return Gia_ObjRepr(p, Id) == 0; }
static inline int Gia_ObjIsHead( Gia_Man_t * p, int Id ) { return Gia_ObjRepr(p, Id) == GIA_VOID && Gia_ObjNext(p, Id) > 0; }
-static inline int Gia_ObjIsNone( Gia_Man_t * p, int Id ) { return Gia_ObjRepr(p, Id) == GIA_VOID && Gia_ObjNext(p, Id) == 0; }
-static inline int Gia_ObjIsTail( Gia_Man_t * p, int Id ) { return (Gia_ObjRepr(p, Id) > 0 && Gia_ObjRepr(p, Id) != GIA_VOID) && Gia_ObjNext(p, Id) == 0; }
+static inline int Gia_ObjIsNone( Gia_Man_t * p, int Id ) { return Gia_ObjRepr(p, Id) == GIA_VOID && Gia_ObjNext(p, Id) <= 0; }
+static inline int Gia_ObjIsTail( Gia_Man_t * p, int Id ) { return (Gia_ObjRepr(p, Id) > 0 && Gia_ObjRepr(p, Id) != GIA_VOID) && Gia_ObjNext(p, Id) <= 0; }
static inline int Gia_ObjIsClass( Gia_Man_t * p, int Id ) { return (Gia_ObjRepr(p, Id) > 0 && Gia_ObjRepr(p, Id) != GIA_VOID) || Gia_ObjNext(p, Id) > 0; }
static inline int Gia_ObjHasSameRepr( Gia_Man_t * p, int i, int k ) { assert( k ); return i? (Gia_ObjRepr(p, i) == Gia_ObjRepr(p, k) && Gia_ObjRepr(p, i) != GIA_VOID) : Gia_ObjRepr(p, k) == 0; }
static inline int Gia_ObjIsFailedPair( Gia_Man_t * p, int i, int k ) { assert( k ); return i? (Gia_ObjFailed(p, i) || Gia_ObjFailed(p, k)) : Gia_ObjFailed(p, k); }
-static inline int Gia_ClassIsPair( Gia_Man_t * p, int i ) { assert( Gia_ObjIsHead(p, i) ); assert( Gia_ObjNext(p, i) ); return Gia_ObjNext(p, Gia_ObjNext(p, i)) == 0; }
+static inline int Gia_ClassIsPair( Gia_Man_t * p, int i ) { assert( Gia_ObjIsHead(p, i) ); assert( Gia_ObjNext(p, i) ); return Gia_ObjNext(p, Gia_ObjNext(p, i)) <= 0; }
static inline void Gia_ClassUndoPair( Gia_Man_t * p, int i ) { assert( Gia_ClassIsPair(p,i) ); Gia_ObjSetRepr(p, Gia_ObjNext(p, i), GIA_VOID); Gia_ObjSetNext(p, i, 0); }
#define Gia_ManForEachConst( p, i ) \
for ( i = 1; i < Gia_ManObjNum(p); i++ ) if ( !Gia_ObjIsConst(p, i) ) {} else
#define Gia_ManForEachClass( p, i ) \
for ( i = 1; i < Gia_ManObjNum(p); i++ ) if ( !Gia_ObjIsHead(p, i) ) {} else
+#define Gia_ManForEachClass0( p, i ) \
+ for ( i = 0; i < Gia_ManObjNum(p); i++ ) if ( !Gia_ObjIsHead(p, i) ) {} else
#define Gia_ManForEachClassReverse( p, i ) \
for ( i = Gia_ManObjNum(p) - 1; i > 0; i-- ) if ( !Gia_ObjIsHead(p, i) ) {} else
#define Gia_ClassForEachObj( p, i, iObj ) \
- for ( assert(Gia_ObjIsHead(p, i)), iObj = i; iObj; iObj = Gia_ObjNext(p, iObj) )
+ for ( assert(Gia_ObjIsHead(p, i)), iObj = i; iObj > 0; iObj = Gia_ObjNext(p, iObj) )
#define Gia_ClassForEachObj1( p, i, iObj ) \
- for ( assert(Gia_ObjIsHead(p, i)), iObj = Gia_ObjNext(p, i); iObj; iObj = Gia_ObjNext(p, iObj) )
+ for ( assert(Gia_ObjIsHead(p, i)), iObj = Gia_ObjNext(p, i); iObj > 0; iObj = Gia_ObjNext(p, iObj) )
static inline int Gia_ObjFoffsetId( Gia_Man_t * p, int Id ) { return Vec_IntEntry( p->vFanout, Id ); }
@@ -1585,6 +1588,7 @@ extern void Gia_ManSwapPos( Gia_Man_t * p, int i );
extern Vec_Int_t * Gia_ManSaveValue( Gia_Man_t * p );
extern void Gia_ManLoadValue( Gia_Man_t * p, Vec_Int_t * vValues );
extern Vec_Int_t * Gia_ManFirstFanouts( Gia_Man_t * p );
+extern void Gia_ManDetectMuxes( Gia_Man_t * p );
/*=== giaCTas.c ===========================================================*/
typedef struct Tas_Man_t_ Tas_Man_t;
diff --git a/src/aig/gia/giaEquiv.c b/src/aig/gia/giaEquiv.c
index 1b0bce07..f41db898 100644
--- a/src/aig/gia/giaEquiv.c
+++ b/src/aig/gia/giaEquiv.c
@@ -485,7 +485,7 @@ void Gia_ManEquivPrintClasses( Gia_Man_t * p, int fVerbose, float Mem )
if ( fVerbose )
{
// int Ent;
- Abc_Print( 1, "Const0 = " );
+ Abc_Print( 1, "Const0 (%d) = ", Counter0 );
Gia_ManForEachConst( p, i )
Abc_Print( 1, "%d ", i );
Abc_Print( 1, "\n" );
diff --git a/src/aig/gia/giaSatoko.c b/src/aig/gia/giaSatoko.c
index 7cbc4184..5e04502d 100644
--- a/src/aig/gia/giaSatoko.c
+++ b/src/aig/gia/giaSatoko.c
@@ -87,7 +87,7 @@ satoko_t * Gia_ManSatokoInit( Cnf_Dat_t * pCnf, satoko_opts_t * opts )
//sat_solver_setnvars( pSat, p->nVars );
for ( i = 0; i < pCnf->nClauses; i++ )
{
- if ( !satoko_add_clause( pSat, (unsigned *)pCnf->pClauses[i], pCnf->pClauses[i+1]-pCnf->pClauses[i] ) )
+ if ( !satoko_add_clause( pSat, pCnf->pClauses[i], pCnf->pClauses[i+1]-pCnf->pClauses[i] ) )
{
satoko_destroy( pSat );
return NULL;
diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c
index c7af642e..d100b6c1 100644
--- a/src/aig/gia/giaUtil.c
+++ b/src/aig/gia/giaUtil.c
@@ -2050,6 +2050,25 @@ void Gia_AigerWriteLut( Gia_Man_t * p, char * pFileName )
Vec_WrdFree( vTruths );
}
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Gia_ManDetectMuxes( Gia_Man_t * p )
+{
+ Gia_Obj_t * pObj = NULL, * pNodeT, * pNodeE; int i;
+ Gia_ManForEachObj( p, pObj, i );
+ if ( Gia_ObjIsAnd(pObj) && Gia_ObjRecognizeMux(pObj, &pNodeT, &pNodeE) )
+ pObj->fMark0 = 1;
+}
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 52684f8c..466af66a 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -43019,7 +43019,7 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
// Jf_ManTestCnf( pAbc->pGia );
// Gia_ManCheckFalseTest( pAbc->pGia, nFrames );
// Gia_ParTest( pAbc->pGia, nWords, nProcs );
-
+//Cec2_ManSimulateTest( pAbc->pGia );
// printf( "\nThis command is currently disabled.\n\n" );
return 0;
usage:
diff --git a/src/base/wlc/wlcSim.c b/src/base/wlc/wlcSim.c
index 20ac8c61..e2fcd1f8 100644
--- a/src/base/wlc/wlcSim.c
+++ b/src/base/wlc/wlcSim.c
@@ -43,13 +43,13 @@ ABC_NAMESPACE_IMPL_START
***********************************************************************/
static inline word * Wlc_ObjSim( Gia_Man_t * p, int iObj )
{
- return Vec_WrdEntryP( p->vSims, p->iPatsPi * iObj );
+ return Vec_WrdEntryP( p->vSims, p->nSimWords * iObj );
}
static inline void Wlc_ObjSimPi( Gia_Man_t * p, int iObj )
{
int w;
word * pSim = Wlc_ObjSim( p, iObj );
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSim[w] = Gia_ManRandomW( 0 );
}
static inline void Wlc_ObjSimRo( Gia_Man_t * p, int iObj )
@@ -57,7 +57,7 @@ static inline void Wlc_ObjSimRo( Gia_Man_t * p, int iObj )
int w;
word * pSimRo = Wlc_ObjSim( p, iObj );
word * pSimRi = Wlc_ObjSim( p, Gia_ObjRoToRiId(p, iObj) );
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSimRo[w] = pSimRi[w];
}
static inline void Wlc_ObjSimCo( Gia_Man_t * p, int iObj )
@@ -67,10 +67,10 @@ static inline void Wlc_ObjSimCo( Gia_Man_t * p, int iObj )
word * pSimCo = Wlc_ObjSim( p, iObj );
word * pSimDri = Wlc_ObjSim( p, Gia_ObjFaninId0(pObj, iObj) );
if ( Gia_ObjFaninC0(pObj) )
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSimCo[w] = ~pSimDri[w];
else
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSimCo[w] = pSimDri[w];
}
static inline void Wlc_ObjSimAnd( Gia_Man_t * p, int iObj )
@@ -81,16 +81,16 @@ static inline void Wlc_ObjSimAnd( Gia_Man_t * p, int iObj )
word * pSim0 = Wlc_ObjSim( p, Gia_ObjFaninId0(pObj, iObj) );
word * pSim1 = Wlc_ObjSim( p, Gia_ObjFaninId1(pObj, iObj) );
if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSim[w] = ~pSim0[w] & ~pSim1[w];
else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSim[w] = ~pSim0[w] & pSim1[w];
else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSim[w] = pSim0[w] & ~pSim1[w];
else
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSim[w] = pSim0[w] & pSim1[w];
}
@@ -135,7 +135,7 @@ Vec_Ptr_t * Wlc_NtkSimulate( Wlc_Ntk_t * p, Vec_Int_t * vNodes, int nWords, int
// allocate simulation info for one timeframe
Vec_WrdFreeP( &pGia->vSims );
pGia->vSims = Vec_WrdStart( Gia_ManObjNum(pGia) * nWords );
- pGia->iPatsPi = nWords;
+ pGia->nSimWords = nWords;
// allocate resulting simulation info
vRes = Vec_PtrAlloc( Vec_IntSize(vNodes) );
Wlc_NtkForEachObjVec( vNodes, p, pWlcObj, i )
@@ -188,7 +188,7 @@ Vec_Ptr_t * Wlc_NtkSimulate( Wlc_Ntk_t * p, Vec_Int_t * vNodes, int nWords, int
printf( "Replaced %d dangling internal bits with constant 0.\n", Counter );
}
Vec_WrdFreeP( &pGia->vSims );
- pGia->iPatsPi = 0;
+ pGia->nSimWords = 0;
Gia_ManStop( pGia );
return vRes;
}
diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h
index d77ed64d..e04ffbc9 100644
--- a/src/misc/util/utilTruth.h
+++ b/src/misc/util/utilTruth.h
@@ -1631,6 +1631,14 @@ static inline int Abc_TtFindFirstBit( word * pIn, int nVars )
return 64*w + Abc_Tt6FirstBit(pIn[w]);
return -1;
}
+static inline int Abc_TtFindFirstBit2( word * pIn, int nWords )
+{
+ int w;
+ for ( w = 0; w < nWords; w++ )
+ if ( pIn[w] )
+ return 64*w + Abc_Tt6FirstBit(pIn[w]);
+ return -1;
+}
static inline int Abc_TtFindFirstDiffBit( word * pIn1, word * pIn2, int nVars )
{
int w, nWords = Abc_TtWordNum(nVars);
@@ -1639,6 +1647,14 @@ static inline int Abc_TtFindFirstDiffBit( word * pIn1, word * pIn2, int nVars )
return 64*w + Abc_Tt6FirstBit(pIn1[w] ^ pIn2[w]);
return -1;
}
+static inline int Abc_TtFindFirstDiffBit2( word * pIn1, word * pIn2, int nWords )
+{
+ int w;
+ for ( w = 0; w < nWords; w++ )
+ if ( pIn1[w] ^ pIn2[w] )
+ return 64*w + Abc_Tt6FirstBit(pIn1[w] ^ pIn2[w]);
+ return -1;
+}
static inline int Abc_TtFindFirstZero( word * pIn, int nVars )
{
int w, nWords = Abc_TtWordNum(nVars);
diff --git a/src/proof/cec/cecSat.c b/src/proof/cec/cecSat.c
new file mode 100644
index 00000000..97bbb7d3
--- /dev/null
+++ b/src/proof/cec/cecSat.c
@@ -0,0 +1,1003 @@
+/**CFile****************************************************************
+
+ FileName [cecSat.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Combinational equivalence checking.]
+
+ Synopsis [Detection of structural isomorphism.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: cecSat.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "aig/gia/gia.h"
+#include "misc/util/utilTruth.h"
+#include "sat/satoko/satoko.h"
+#include "sat/satoko/solver.h"
+
+ABC_NAMESPACE_IMPL_START
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+// sweeping manager
+typedef struct Cec2_Par_t_ Cec2_Par_t;
+struct Cec2_Par_t_
+{
+ int nSimWords; // simulation words
+ int nSimRounds; // simulation rounds
+ int nConfLimit; // SAT solver conflict limit
+ int fIsMiter; // this is a miter
+ int fUseCones; // use logic cones
+ int fVeryVerbose; // verbose stats
+ int fVerbose; // verbose stats
+};
+
+// SAT solving manager
+typedef struct Cec2_Man_t_ Cec2_Man_t;
+struct Cec2_Man_t_
+{
+ Cec2_Par_t * pPars; // parameters
+ Gia_Man_t * pAig; // user's AIG
+ Gia_Man_t * pNew; // internal AIG
+ // SAT solving
+ satoko_t * pSat; // SAT solver
+ Vec_Ptr_t * vFrontier; // CNF construction
+ Vec_Ptr_t * vFanins; // CNF construction
+ Vec_Wrd_t * vSims; // CI simulation info
+ Vec_Int_t * vNodesNew; // nodes
+ Vec_Int_t * vSatVars; // nodes
+ Vec_Int_t * vObjSatPairs; // nodes
+ Vec_Int_t * vCexTriples; // nodes
+ // statistics
+ int nSatSat;
+ int nSatUnsat;
+ int nSatUndec;
+ abctime timeSatSat;
+ abctime timeSatUnsat;
+ abctime timeSatUndec;
+ abctime timeSim;
+ abctime timeRefine;
+ abctime timeExtra;
+ abctime timeStart;
+};
+
+static inline int Cec2_ObjSatId( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Gia_ObjCopyArray(p, Gia_ObjId(p, pObj)); }
+static inline int Cec2_ObjSetSatId( Gia_Man_t * p, Gia_Obj_t * pObj, int Num ) { assert(Cec2_ObjSatId(p, pObj) == -1); Gia_ObjSetCopyArray(p, Gia_ObjId(p, pObj), Num); return Num; }
+static inline void Cec2_ObjCleanSatId( Gia_Man_t * p, Gia_Obj_t * pObj ) { assert(Cec2_ObjSatId(p, pObj) != -1); Gia_ObjSetCopyArray(p, Gia_ObjId(p, pObj), -1); }
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Sets parameter defaults.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cec2_SetDefaultParams( Cec2_Par_t * p )
+{
+ memset( p, 0, sizeof(Cec2_Par_t) );
+ p->nSimWords = 8; // simulation words
+ p->nSimRounds = 4; // simulation rounds
+ p->nConfLimit = 1000; // conflict limit at a node
+ p->fIsMiter = 0; // this is a miter
+ p->fUseCones = 1; // use logic cones
+ p->fVeryVerbose = 0; // verbose stats
+ p->fVerbose = 1; // verbose stats
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adds clauses to the solver.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cec2_AddClausesMux( Gia_Man_t * p, Gia_Obj_t * pNode, satoko_t * pSat )
+{
+ int fPolarFlip = 0;
+ Gia_Obj_t * pNodeI, * pNodeT, * pNodeE;
+ int pLits[4], RetValue, VarF, VarI, VarT, VarE, fCompT, fCompE;
+
+ assert( !Gia_IsComplement( pNode ) );
+ assert( pNode->fMark0 );
+ // get nodes (I = if, T = then, E = else)
+ pNodeI = Gia_ObjRecognizeMux( pNode, &pNodeT, &pNodeE );
+ // get the variable numbers
+ VarF = Cec2_ObjSatId(p, pNode);
+ VarI = Cec2_ObjSatId(p, pNodeI);
+ VarT = Cec2_ObjSatId(p, Gia_Regular(pNodeT));
+ VarE = Cec2_ObjSatId(p, Gia_Regular(pNodeE));
+ // get the complementation flags
+ fCompT = Gia_IsComplement(pNodeT);
+ fCompE = Gia_IsComplement(pNodeE);
+
+ // f = ITE(i, t, e)
+
+ // i' + t' + f
+ // i' + t + f'
+ // i + e' + f
+ // i + e + f'
+
+ // create four clauses
+ pLits[0] = Abc_Var2Lit(VarI, 1);
+ pLits[1] = Abc_Var2Lit(VarT, 1^fCompT);
+ pLits[2] = Abc_Var2Lit(VarF, 0);
+ if ( fPolarFlip )
+ {
+ if ( pNodeI->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( Gia_Regular(pNodeT)->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ if ( pNode->fPhase ) pLits[2] = Abc_LitNot( pLits[2] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 3 );
+ assert( RetValue );
+ pLits[0] = Abc_Var2Lit(VarI, 1);
+ pLits[1] = Abc_Var2Lit(VarT, 0^fCompT);
+ pLits[2] = Abc_Var2Lit(VarF, 1);
+ if ( fPolarFlip )
+ {
+ if ( pNodeI->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( Gia_Regular(pNodeT)->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ if ( pNode->fPhase ) pLits[2] = Abc_LitNot( pLits[2] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 3 );
+ assert( RetValue );
+ pLits[0] = Abc_Var2Lit(VarI, 0);
+ pLits[1] = Abc_Var2Lit(VarE, 1^fCompE);
+ pLits[2] = Abc_Var2Lit(VarF, 0);
+ if ( fPolarFlip )
+ {
+ if ( pNodeI->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( Gia_Regular(pNodeE)->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ if ( pNode->fPhase ) pLits[2] = Abc_LitNot( pLits[2] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 3 );
+ assert( RetValue );
+ pLits[0] = Abc_Var2Lit(VarI, 0);
+ pLits[1] = Abc_Var2Lit(VarE, 0^fCompE);
+ pLits[2] = Abc_Var2Lit(VarF, 1);
+ if ( fPolarFlip )
+ {
+ if ( pNodeI->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( Gia_Regular(pNodeE)->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ if ( pNode->fPhase ) pLits[2] = Abc_LitNot( pLits[2] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 3 );
+ assert( RetValue );
+
+ // two additional clauses
+ // t' & e' -> f'
+ // t & e -> f
+
+ // t + e + f'
+ // t' + e' + f
+
+ if ( VarT == VarE )
+ {
+// assert( fCompT == !fCompE );
+ return;
+ }
+
+ pLits[0] = Abc_Var2Lit(VarT, 0^fCompT);
+ pLits[1] = Abc_Var2Lit(VarE, 0^fCompE);
+ pLits[2] = Abc_Var2Lit(VarF, 1);
+ if ( fPolarFlip )
+ {
+ if ( Gia_Regular(pNodeT)->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( Gia_Regular(pNodeE)->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ if ( pNode->fPhase ) pLits[2] = Abc_LitNot( pLits[2] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 3 );
+ assert( RetValue );
+ pLits[0] = Abc_Var2Lit(VarT, 1^fCompT);
+ pLits[1] = Abc_Var2Lit(VarE, 1^fCompE);
+ pLits[2] = Abc_Var2Lit(VarF, 0);
+ if ( fPolarFlip )
+ {
+ if ( Gia_Regular(pNodeT)->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( Gia_Regular(pNodeE)->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ if ( pNode->fPhase ) pLits[2] = Abc_LitNot( pLits[2] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 3 );
+ assert( RetValue );
+}
+void Cec2_AddClausesSuper( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Ptr_t * vSuper, satoko_t * pSat )
+{
+ int fPolarFlip = 0;
+ Gia_Obj_t * pFanin;
+ int * pLits, nLits, RetValue, i;
+ assert( !Gia_IsComplement(pNode) );
+ assert( Gia_ObjIsAnd( pNode ) );
+ // create storage for literals
+ nLits = Vec_PtrSize(vSuper) + 1;
+ pLits = ABC_ALLOC( int, nLits );
+ // suppose AND-gate is A & B = C
+ // add !A => !C or A + !C
+ Vec_PtrForEachEntry( Gia_Obj_t *, vSuper, pFanin, i )
+ {
+ pLits[0] = Abc_Var2Lit(Cec2_ObjSatId(p, Gia_Regular(pFanin)), Gia_IsComplement(pFanin));
+ pLits[1] = Abc_Var2Lit(Cec2_ObjSatId(p, pNode), 1);
+ if ( fPolarFlip )
+ {
+ if ( Gia_Regular(pFanin)->fPhase ) pLits[0] = Abc_LitNot( pLits[0] );
+ if ( pNode->fPhase ) pLits[1] = Abc_LitNot( pLits[1] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, 2 );
+ assert( RetValue );
+ }
+ // add A & B => C or !A + !B + C
+ Vec_PtrForEachEntry( Gia_Obj_t *, vSuper, pFanin, i )
+ {
+ pLits[i] = Abc_Var2Lit(Cec2_ObjSatId(p, Gia_Regular(pFanin)), !Gia_IsComplement(pFanin));
+ if ( fPolarFlip )
+ {
+ if ( Gia_Regular(pFanin)->fPhase ) pLits[i] = Abc_LitNot( pLits[i] );
+ }
+ }
+ pLits[nLits-1] = Abc_Var2Lit(Cec2_ObjSatId(p, pNode), 0);
+ if ( fPolarFlip )
+ {
+ if ( pNode->fPhase ) pLits[nLits-1] = Abc_LitNot( pLits[nLits-1] );
+ }
+ RetValue = satoko_add_clause( pSat, pLits, nLits );
+ assert( RetValue );
+ ABC_FREE( pLits );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adds clauses and returns CNF variable of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cec2_CollectSuper_rec( Gia_Obj_t * pObj, Vec_Ptr_t * vSuper, int fFirst, int fUseMuxes )
+{
+ // if the new node is complemented or a PI, another gate begins
+ if ( Gia_IsComplement(pObj) || Gia_ObjIsCi(pObj) ||
+ (!fFirst && Gia_ObjValue(pObj) > 1) ||
+ (fUseMuxes && pObj->fMark0) )
+ {
+ Vec_PtrPushUnique( vSuper, pObj );
+ return;
+ }
+ // go through the branches
+ Cec2_CollectSuper_rec( Gia_ObjChild0(pObj), vSuper, 0, fUseMuxes );
+ Cec2_CollectSuper_rec( Gia_ObjChild1(pObj), vSuper, 0, fUseMuxes );
+}
+void Cec2_CollectSuper( Gia_Obj_t * pObj, int fUseMuxes, Vec_Ptr_t * vSuper )
+{
+ assert( !Gia_IsComplement(pObj) );
+ assert( !Gia_ObjIsCi(pObj) );
+ Vec_PtrClear( vSuper );
+ Cec2_CollectSuper_rec( pObj, vSuper, 1, fUseMuxes );
+}
+void Cec2_ObjAddToFrontier( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Ptr_t * vFrontier, satoko_t * pSat )
+{
+ assert( !Gia_IsComplement(pObj) );
+ assert( !Gia_ObjIsConst0(pObj) );
+ if ( Cec2_ObjSatId(p, pObj) >= 0 )
+ return;
+ assert( Cec2_ObjSatId(p, pObj) == -1 );
+ Cec2_ObjSetSatId( p, pObj, satoko_add_variable(pSat, 0) );
+ if ( Gia_ObjIsAnd(pObj) )
+ Vec_PtrPush( vFrontier, pObj );
+}
+int Cec2_ObjGetCnfVar( Cec2_Man_t * p, int iObj )
+{
+ Gia_Obj_t * pNode, * pFanin;
+ Gia_Obj_t * pObj = Gia_ManObj(p->pNew, iObj);
+ int i, k, fUseMuxes = 1;
+ // quit if CNF is ready
+ if ( Cec2_ObjSatId(p->pNew,pObj) >= 0 )
+ return Cec2_ObjSatId(p->pNew,pObj);
+ assert( iObj > 0 );
+ if ( Gia_ObjIsCi(pObj) )
+ return Cec2_ObjSetSatId( p->pNew, pObj, satoko_add_variable(p->pSat, 0) );
+ assert( Gia_ObjIsAnd(pObj) );
+ // start the frontier
+ Vec_PtrClear( p->vFrontier );
+ Cec2_ObjAddToFrontier( p->pNew, pObj, p->vFrontier, p->pSat );
+ // explore nodes in the frontier
+ Vec_PtrForEachEntry( Gia_Obj_t *, p->vFrontier, pNode, i )
+ {
+ // create the supergate
+ assert( Cec2_ObjSatId(p->pNew,pNode) >= 0 );
+ if ( fUseMuxes && pNode->fMark0 )
+ {
+ Vec_PtrClear( p->vFanins );
+ Vec_PtrPushUnique( p->vFanins, Gia_ObjFanin0( Gia_ObjFanin0(pNode) ) );
+ Vec_PtrPushUnique( p->vFanins, Gia_ObjFanin0( Gia_ObjFanin1(pNode) ) );
+ Vec_PtrPushUnique( p->vFanins, Gia_ObjFanin1( Gia_ObjFanin0(pNode) ) );
+ Vec_PtrPushUnique( p->vFanins, Gia_ObjFanin1( Gia_ObjFanin1(pNode) ) );
+ Vec_PtrForEachEntry( Gia_Obj_t *, p->vFanins, pFanin, k )
+ Cec2_ObjAddToFrontier( p->pNew, Gia_Regular(pFanin), p->vFrontier, p->pSat );
+ Cec2_AddClausesMux( p->pNew, pNode, p->pSat );
+ }
+ else
+ {
+ Cec2_CollectSuper( pNode, fUseMuxes, p->vFanins );
+ Vec_PtrForEachEntry( Gia_Obj_t *, p->vFanins, pFanin, k )
+ Cec2_ObjAddToFrontier( p->pNew, Gia_Regular(pFanin), p->vFrontier, p->pSat );
+ Cec2_AddClausesSuper( p->pNew, pNode, p->vFanins, p->pSat );
+ }
+ assert( Vec_PtrSize(p->vFanins) > 1 );
+ }
+ return Cec2_ObjSatId(p->pNew,pObj);
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Internal simulation APIs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline word * Cec2_ObjSim( Gia_Man_t * p, int iObj )
+{
+ return Vec_WrdEntryP( p->vSims, p->nSimWords * iObj );
+}
+static inline void Cec2_ObjSimSetInputBit( Gia_Man_t * p, int iObj, int Bit )
+{
+ word * pSim = Cec2_ObjSim( p, iObj );
+ if ( Abc_InfoHasBit( (unsigned*)pSim, p->iPatsPi ) != Bit )
+ Abc_InfoXorBit( (unsigned*)pSim, p->iPatsPi );
+}
+static inline void Cec2_ObjSimRo( Gia_Man_t * p, int iObj )
+{
+ int w;
+ word * pSimRo = Cec2_ObjSim( p, iObj );
+ word * pSimRi = Cec2_ObjSim( p, Gia_ObjRoToRiId(p, iObj) );
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSimRo[w] = pSimRi[w];
+}
+static inline void Cec2_ObjSimCo( Gia_Man_t * p, int iObj )
+{
+ int w;
+ Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
+ word * pSimCo = Cec2_ObjSim( p, iObj );
+ word * pSimDri = Cec2_ObjSim( p, Gia_ObjFaninId0(pObj, iObj) );
+ if ( Gia_ObjFaninC0(pObj) )
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSimCo[w] = ~pSimDri[w];
+ else
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSimCo[w] = pSimDri[w];
+}
+static inline void Cec2_ObjSimAnd( Gia_Man_t * p, int iObj )
+{
+ int w;
+ Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
+ word * pSim = Cec2_ObjSim( p, iObj );
+ word * pSim0 = Cec2_ObjSim( p, Gia_ObjFaninId0(pObj, iObj) );
+ word * pSim1 = Cec2_ObjSim( p, Gia_ObjFaninId1(pObj, iObj) );
+ if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSim[w] = ~pSim0[w] & ~pSim1[w];
+ else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSim[w] = ~pSim0[w] & pSim1[w];
+ else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSim[w] = pSim0[w] & ~pSim1[w];
+ else
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSim[w] = pSim0[w] & pSim1[w];
+}
+static inline int Cec2_ObjSimEqual( Gia_Man_t * p, int iObj0, int iObj1 )
+{
+ int w;
+ word * pSim0 = Cec2_ObjSim( p, iObj0 );
+ word * pSim1 = Cec2_ObjSim( p, iObj1 );
+ if ( (pSim0[0] & 1) == (pSim1[0] & 1) )
+ {
+ for ( w = 0; w < p->nSimWords; w++ )
+ if ( pSim0[w] != pSim1[w] )
+ return 0;
+ return 1;
+ }
+ else
+ {
+ for ( w = 0; w < p->nSimWords; w++ )
+ if ( pSim0[w] != ~pSim1[w] )
+ return 0;
+ return 1;
+ }
+}
+static inline void Cec2_ObjSimCi( Gia_Man_t * p, int iObj )
+{
+ int w;
+ word * pSim = Cec2_ObjSim( p, iObj );
+ for ( w = 0; w < p->nSimWords; w++ )
+ pSim[w] = Gia_ManRandomW( 0 );
+ pSim[0] <<= 1;
+}
+void Cec2_ManSimulateCis( Gia_Man_t * p )
+{
+ int i, Id;
+ Gia_ManForEachCiId( p, Id, i )
+ Cec2_ObjSimCi( p, Id );
+ p->iPatsPi = 1;
+}
+Abc_Cex_t * Cec2_ManDeriveCex( Gia_Man_t * p, int iOut, int iPat )
+{
+ Abc_Cex_t * pCex;
+ int i, Id;
+ pCex = Abc_CexAlloc( 0, Gia_ManCiNum(p), 1 );
+ pCex->iPo = iOut;
+ if ( iPat == -1 )
+ return pCex;
+ Gia_ManForEachCiId( p, Id, i )
+ if ( Abc_InfoHasBit((unsigned *)Cec2_ObjSim(p, Id), iPat) )
+ Abc_InfoSetBit( pCex->pData, i );
+ return pCex;
+}
+int Cec2_ManSimulateCos( Gia_Man_t * p )
+{
+ int i, Id;
+ // check outputs and generate CEX if they fail
+ Gia_ManForEachCoId( p, Id, i )
+ {
+ Cec2_ObjSimCo( p, Id );
+ if ( Cec2_ObjSimEqual(p, Id, 0) )
+ continue;
+ p->pCexSeq = Cec2_ManDeriveCex( p, i, Abc_TtFindFirstBit2(Cec2_ObjSim(p, Id), p->nSimWords) );
+ return 0;
+ }
+ return 1;
+}
+void Cec2_ManSaveCis( Gia_Man_t * p )
+{
+ int w, i, Id;
+ assert( p->vSimsPi != NULL );
+ for ( w = 0; w < p->nSimWords; w++ )
+ Gia_ManForEachCiId( p, Id, i )
+ Vec_WrdPush( p->vSimsPi, Cec2_ObjSim(p, Id)[w] );
+}
+void Cec2_ManSimulate( Gia_Man_t * p, Vec_Int_t * vTriples, Cec2_Man_t * pMan )
+{
+ extern void Cec2_ManSimClassRefineOne( Gia_Man_t * p, int iRepr );
+ abctime clk = Abc_Clock();
+ Gia_Obj_t * pObj;
+ int i, iRepr, iObj, Entry;
+ //Cec2_ManSaveCis( p );
+ Gia_ManForEachAnd( p, pObj, i )
+ Cec2_ObjSimAnd( p, i );
+ pMan->timeSim += Abc_Clock() - clk;
+ if ( p->pReprs == NULL )
+ return;
+ if ( vTriples )
+ {
+ Vec_IntForEachEntryTriple( vTriples, iRepr, iObj, Entry, i )
+ {
+ word * pSim0 = Cec2_ObjSim( p, iRepr );
+ word * pSim1 = Cec2_ObjSim( p, iObj );
+ int iPat = Abc_Lit2Var(Entry);
+ int fPhase = Abc_LitIsCompl(Entry);
+ if ( (fPhase ^ Abc_InfoHasBit((unsigned *)pSim0, iPat)) == Abc_InfoHasBit((unsigned *)pSim1, iPat) )
+ printf( "ERROR: Pattern %d did not disprove pair %d and %d.\n", iPat, iRepr, iObj );
+ }
+ }
+ clk = Abc_Clock();
+ Gia_ManForEachClass0( p, i )
+ Cec2_ManSimClassRefineOne( p, i );
+ pMan->timeRefine += Abc_Clock() - clk;
+}
+void Cec2_ManSimAlloc( Gia_Man_t * p, int nWords )
+{
+ Vec_WrdFreeP( &p->vSims );
+ Vec_WrdFreeP( &p->vSimsPi );
+ p->vSims = Vec_WrdStart( Gia_ManObjNum(p) * nWords );
+ p->vSimsPi = Vec_WrdAlloc( Gia_ManCiNum(p) * nWords * 4 ); // storage for CI patterns
+ p->nSimWords = nWords;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Computes hash key of the simulation info.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Cec2_ManSimHashKey( word * pSim, int nSims, int nTableSize )
+{
+ static int s_Primes[16] = {
+ 1291, 1699, 1999, 2357, 2953, 3313, 3907, 4177,
+ 4831, 5147, 5647, 6343, 6899, 7103, 7873, 8147 };
+ unsigned uHash = 0, * pSimU = (unsigned *)pSim;
+ int i, nSimsU = 2 * nSims;
+ if ( pSimU[0] & 1 )
+ for ( i = 0; i < nSimsU; i++ )
+ uHash ^= ~pSimU[i] * s_Primes[i & 0xf];
+ else
+ for ( i = 0; i < nSimsU; i++ )
+ uHash ^= pSimU[i] * s_Primes[i & 0xf];
+ return (int)(uHash % nTableSize);
+
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creating initial equivalence classes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cec2_ManSimClassRefineOne( Gia_Man_t * p, int iRepr )
+{
+ int iObj, iPrev = iRepr, iPrev2, iRepr2;
+ Gia_ClassForEachObj1( p, iRepr, iRepr2 )
+ if ( Cec2_ObjSimEqual(p, iRepr, iRepr2) )
+ iPrev = iRepr2;
+ else
+ break;
+ if ( iRepr2 <= 0 ) // no refinement
+ return;
+ // relink remaining nodes of the class
+ // nodes that are equal to iRepr, remain in the class of iRepr
+ // nodes that are not equal to iRepr, move to the class of iRepr2
+ Gia_ObjSetRepr( p, iRepr2, GIA_VOID );
+ iPrev2 = iRepr2;
+ for ( iObj = Gia_ObjNext(p, iRepr2); iObj > 0; iObj = Gia_ObjNext(p, iObj) )
+ {
+ if ( Cec2_ObjSimEqual(p, iRepr, iObj) ) // remains with iRepr
+ {
+ Gia_ObjSetNext( p, iPrev, iObj );
+ iPrev = iObj;
+ }
+ else // moves to iRepr2
+ {
+ Gia_ObjSetRepr( p, iObj, iRepr2 );
+ Gia_ObjSetNext( p, iPrev2, iObj );
+ iPrev2 = iObj;
+ }
+ }
+ Gia_ObjSetNext( p, iPrev, -1 );
+ Gia_ObjSetNext( p, iPrev2, -1 );
+}
+void Cec2_ManCreateClasses( Gia_Man_t * p, Cec2_Man_t * pMan )
+{
+ abctime clk;
+ Gia_Obj_t * pObj;
+ int nWords = p->nSimWords;
+ int * pTable, nTableSize, i, Key;
+ // allocate representation
+ ABC_FREE( p->pReprs );
+ ABC_FREE( p->pNexts );
+ p->pReprs = ABC_CALLOC( Gia_Rpr_t, Gia_ManObjNum(p) );
+ p->pNexts = ABC_FALLOC( int, Gia_ManObjNum(p) );
+ // hash each node by its simulation info
+ nTableSize = Abc_PrimeCudd( Gia_ManObjNum(p) );
+ pTable = ABC_FALLOC( int, nTableSize );
+ Gia_ManForEachObj( p, pObj, i )
+ {
+ p->pReprs[i].iRepr = GIA_VOID;
+ if ( Gia_ObjIsCo(pObj) )
+ continue;
+ Key = Cec2_ManSimHashKey( Cec2_ObjSim(p, i), nWords, nTableSize );
+ assert( Key >= 0 && Key < nTableSize );
+ if ( pTable[Key] == -1 )
+ pTable[Key] = i;
+ else
+ Gia_ObjSetRepr( p, i, pTable[Key] );
+ }
+ // create classes
+ for ( i = Gia_ManObjNum(p) - 1; i >= 0; i-- )
+ {
+ int iRepr = Gia_ObjRepr(p, i);
+ if ( iRepr == GIA_VOID )
+ continue;
+ Gia_ObjSetNext( p, i, Gia_ObjNext(p, iRepr) );
+ Gia_ObjSetNext( p, iRepr, i );
+ }
+ ABC_FREE( pTable );
+ clk = Abc_Clock();
+ Gia_ManForEachClass0( p, i )
+ Cec2_ManSimClassRefineOne( p, i );
+ pMan->timeRefine += Abc_Clock() - clk;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Cec2_Man_t * Cec2_ManCreate( Gia_Man_t * pAig, Cec2_Par_t * pPars )
+{
+ Cec2_Man_t * p;
+ Gia_Obj_t * pObj; int i;
+ //assert( Gia_ManRegNum(pAig) == 0 );
+ p = ABC_CALLOC( Cec2_Man_t, 1 );
+ memset( p, 0, sizeof(Cec2_Man_t) );
+ p->timeStart = Abc_Clock();
+ p->pPars = pPars;
+ p->pAig = pAig;
+ // create new manager
+ p->pNew = Gia_ManStart( Gia_ManObjNum(pAig) );
+ Gia_ManFillValue( pAig );
+ Gia_ManConst0(pAig)->Value = 0;
+ Gia_ManForEachCi( pAig, pObj, i )
+ pObj->Value = Gia_ManAppendCi( p->pNew );
+ Gia_ManHashAlloc( p->pNew );
+ Vec_IntFill( &p->pNew->vCopies, Gia_ManObjNum(p->pNew), -1 );
+ // SAT solving
+ p->pSat = satoko_create();
+ p->vFrontier = Vec_PtrAlloc( 1000 );
+ p->vFanins = Vec_PtrAlloc( 100 );
+ p->vNodesNew = Vec_IntAlloc( 100 );
+ p->vSatVars = Vec_IntAlloc( 100 );
+ p->vObjSatPairs = Vec_IntAlloc( 100 );
+ p->vCexTriples = Vec_IntAlloc( 100 );
+ // remember pointer to the solver in the AIG manager
+ pAig->pData = p->pSat;
+ return p;
+}
+void Cec2_ManDestroy( Cec2_Man_t * p )
+{
+ if ( p->pPars->fVerbose )
+ {
+ abctime timeTotal = Abc_Clock() - p->timeStart;
+ abctime timeSat = p->timeSatSat + p->timeSatUnsat + p->timeSatUndec;
+ abctime timeOther = timeTotal - timeSat - p->timeSim - p->timeRefine - p->timeExtra;
+// Abc_Print( 1, "%d\n", p->Num );
+ ABC_PRTP( "SAT solving", timeSat, timeTotal );
+ ABC_PRTP( " sat ", p->timeSatSat, timeTotal );
+ ABC_PRTP( " unsat ", p->timeSatUnsat, timeTotal );
+ ABC_PRTP( " fail ", p->timeSatUndec, timeTotal );
+ ABC_PRTP( "Simulation ", p->timeSim, timeTotal );
+ ABC_PRTP( "Refinement ", p->timeRefine, timeTotal );
+ ABC_PRTP( "Rollback ", p->timeExtra, timeTotal );
+ ABC_PRTP( "Other ", timeOther, timeTotal );
+ ABC_PRTP( "TOTAL ", timeTotal, timeTotal );
+ fflush( stdout );
+ }
+
+ Vec_WrdFreeP( &p->pAig->vSims );
+ //Vec_WrdFreeP( &p->pAig->vSimsPi );
+ Gia_ManCleanMark01( p->pAig );
+ satoko_destroy( p->pSat );
+ Gia_ManStopP( &p->pNew );
+ Vec_PtrFreeP( &p->vFrontier );
+ Vec_PtrFreeP( &p->vFanins );
+ Vec_IntFreeP( &p->vNodesNew );
+ Vec_IntFreeP( &p->vSatVars );
+ Vec_IntFreeP( &p->vObjSatPairs );
+ Vec_IntFreeP( &p->vCexTriples );
+ ABC_FREE( p );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Verify counter-example.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Cec2_ManVerify_rec( Gia_Man_t * p, int iObj, satoko_t * pSat )
+{
+ int Value0, Value1;
+ Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
+ if ( iObj == 0 ) return 0;
+ if ( Gia_ObjIsTravIdCurrentId(p, iObj) )
+ return pObj->fMark1;
+ Gia_ObjSetTravIdCurrentId(p, iObj);
+ if ( Gia_ObjIsCi(pObj) )
+ return pObj->fMark1 = var_polarity(pSat, Cec2_ObjSatId(p, pObj)) == LIT_TRUE;
+ assert( Gia_ObjIsAnd(pObj) );
+ Value0 = Cec2_ManVerify_rec( p, Gia_ObjFaninId0(pObj, iObj), pSat ) ^ Gia_ObjFaninC0(pObj);
+ Value1 = Cec2_ManVerify_rec( p, Gia_ObjFaninId1(pObj, iObj), pSat ) ^ Gia_ObjFaninC1(pObj);
+ return pObj->fMark1 = Value0 & Value1;
+}
+void Cec2_ManVerify( Gia_Man_t * p, int iObj0, int iObj1, int fPhase, satoko_t * pSat )
+{
+// int val0 = var_polarity(pSat, Cec2_ObjSatId(p, Gia_ManObj(p, iObj0))) == LIT_TRUE;
+// int val1 = var_polarity(pSat, Cec2_ObjSatId(p, Gia_ManObj(p, iObj1))) == LIT_TRUE;
+ int Value0, Value1;
+ Gia_ManIncrementTravId( p );
+ Value0 = Cec2_ManVerify_rec( p, iObj0, pSat );
+ Value1 = Cec2_ManVerify_rec( p, iObj1, pSat );
+ if ( (Value0 ^ Value1) == fPhase )
+ printf( "CEX verification FAILED for obj %d and obj %d.\n", iObj0, iObj1 );
+// else
+// printf( "CEX verification succeeded for obj %d and obj %d.\n", iObj0, iObj1 );;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Internal simulation APIs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cec2_ManCollect_rec( Cec2_Man_t * p, int iObj )
+{
+ Gia_Obj_t * pObj;
+ if ( Gia_ObjIsTravIdCurrentId(p->pNew, iObj) )
+ return;
+ Gia_ObjSetTravIdCurrentId(p->pNew, iObj);
+ pObj = Gia_ManObj( p->pNew, iObj );
+ if ( Cec2_ObjSatId(p->pNew, pObj) >= 0 )
+ {
+ Vec_IntPush( p->vNodesNew, iObj );
+ Vec_IntPush( p->vSatVars, Cec2_ObjSatId(p->pNew, pObj) );
+ }
+ if ( !iObj )
+ return;
+ if ( Gia_ObjIsAnd(pObj) )
+ {
+ Cec2_ManCollect_rec( p, Gia_ObjFaninId0(pObj, iObj) );
+ Cec2_ManCollect_rec( p, Gia_ObjFaninId1(pObj, iObj) );
+ }
+ else
+ {
+ assert( Cec2_ObjSatId(p->pNew, pObj) >= 0 );
+ Vec_IntPushTwo( p->vObjSatPairs, Gia_ManCiIdToId(p->pAig, Gia_ObjCioId(pObj)), Cec2_ObjSatId(p->pNew, pObj) ); // SAT var
+ }
+}
+int Cec2_ManSolveTwo( Cec2_Man_t * p, int iObj0, int iObj1, int fPhase )
+{
+ Gia_Obj_t * pObj;
+ int status, i, iVar0, iVar1;
+ if (iObj1 < iObj0)
+ iObj1 ^= iObj0, iObj0 ^= iObj1, iObj1 ^= iObj0;
+ assert( iObj0 < iObj1 );
+ assert( p->pPars->fUseCones || solver_varnum(p->pSat) == 0 );
+ if ( !iObj0 && Cec2_ObjSatId(p->pNew, Gia_ManConst0(p->pNew)) == -1 )
+ Cec2_ObjSetSatId( p->pNew, Gia_ManConst0(p->pNew), satoko_add_variable(p->pSat, 0) );
+ iVar0 = Cec2_ObjGetCnfVar( p, iObj0 );
+ iVar1 = Cec2_ObjGetCnfVar( p, iObj1 );
+ // collect inputs and internal nodes
+ Vec_IntClear( p->vNodesNew );
+ Vec_IntClear( p->vSatVars );
+ Vec_IntClear( p->vObjSatPairs );
+ Gia_ManIncrementTravId( p->pNew );
+ Cec2_ManCollect_rec( p, iObj0 );
+ Cec2_ManCollect_rec( p, iObj1 );
+//printf( "%d ", Vec_IntSize(p->vNodesNew) );
+ // solve direct
+ if ( p->pPars->fUseCones ) satoko_mark_cone( p->pSat, Vec_IntArray(p->vSatVars), Vec_IntSize(p->vSatVars) );
+ satoko_assump_push( p->pSat, Abc_Var2Lit(iVar0, 1) );
+ satoko_assump_push( p->pSat, Abc_Var2Lit(iVar1, fPhase) );
+ status = satoko_solve( p->pSat );
+ satoko_assump_pop( p->pSat );
+ satoko_assump_pop( p->pSat );
+ if ( status == SATOKO_UNSAT && iObj0 > 0 )
+ {
+ // solve reverse
+ satoko_assump_push( p->pSat, Abc_Var2Lit(iVar0, 0) );
+ satoko_assump_push( p->pSat, Abc_Var2Lit(iVar1, !fPhase) );
+ status = satoko_solve( p->pSat );
+ satoko_assump_pop( p->pSat );
+ satoko_assump_pop( p->pSat );
+ }
+ if ( p->pPars->fUseCones ) satoko_unmark_cone( p->pSat, Vec_IntArray(p->vSatVars), Vec_IntSize(p->vSatVars) );
+ //if ( status == SATOKO_SAT )
+ // Cec2_ManVerify( p->pNew, iObj0, iObj1, fPhase, p->pSat );
+ if ( p->pPars->fUseCones )
+ return status;
+ Gia_ManForEachObjVec( p->vNodesNew, p->pNew, pObj, i )
+ Cec2_ObjCleanSatId( p->pNew, pObj );
+ return status;
+}
+
+int Cec2_ManSweepNode( Cec2_Man_t * p, int iObj )
+{
+ abctime clk = Abc_Clock();
+ int i, IdAig, IdSat, status, RetValue = 1;
+ Gia_Obj_t * pObj = Gia_ManObj( p->pAig, iObj );
+ Gia_Obj_t * pRepr = Gia_ObjReprObj( p->pAig, iObj );
+ int fCompl = Abc_LitIsCompl(pObj->Value) ^ Abc_LitIsCompl(pRepr->Value) ^ pObj->fPhase ^ pRepr->fPhase;
+ status = Cec2_ManSolveTwo( p, Abc_Lit2Var(pRepr->Value), Abc_Lit2Var(pObj->Value), fCompl );
+ if ( status == SATOKO_SAT )
+ {
+ p->nSatSat++;
+ p->pAig->iPatsPi = (p->pAig->iPatsPi == 64 * p->pAig->nSimWords - 1) ? 1 : p->pAig->iPatsPi + 1;
+ assert( p->pAig->iPatsPi > 0 && p->pAig->iPatsPi < 64 * p->pAig->nSimWords );
+ Vec_IntForEachEntryDouble( p->vObjSatPairs, IdAig, IdSat, i )
+ Cec2_ObjSimSetInputBit( p->pAig, IdAig, var_polarity(p->pSat, IdSat) == LIT_TRUE );
+ RetValue = 0;
+ p->timeSatSat += Abc_Clock() - clk;
+ }
+ else if ( status == SATOKO_UNSAT )
+ {
+ p->nSatUnsat++;
+ pObj->Value = Abc_LitNotCond( pRepr->Value, fCompl );
+ Gia_ObjSetProved( p->pAig, iObj );
+ p->timeSatUnsat += Abc_Clock() - clk;
+ }
+ else
+ {
+ p->nSatUndec++;
+ assert( status == SATOKO_UNDEC );
+ Gia_ObjSetFailed( p->pAig, iObj );
+ assert( 0 );
+ p->timeSatUndec += Abc_Clock() - clk;
+ }
+ if ( p->pPars->fUseCones )
+ return RetValue;
+ clk = Abc_Clock();
+ satoko_rollback( p->pSat );
+ p->timeExtra += Abc_Clock() - clk;
+ p->pSat->stats.n_conflicts = 0;
+ return RetValue;
+}
+void Cec2_ManPrintStats( Gia_Man_t * p, Cec2_Par_t * pPars, Cec2_Man_t * pMan )
+{
+ if ( !pPars->fVerbose )
+ return;
+ printf( "S =%5d ", pMan ? pMan->nSatSat : 0 );
+ printf( "U =%5d ", pMan ? pMan->nSatUnsat : 0 );
+ printf( "F =%5d ", pMan ? pMan->nSatUndec : 0 );
+ Gia_ManEquivPrintClasses( p, pPars->fVeryVerbose, 0 );
+}
+int Cec2_ManPerformSweeping( Gia_Man_t * p, Cec2_Par_t * pPars )
+{
+ Cec2_Man_t * pMan = Cec2_ManCreate( p, pPars );
+ Gia_Obj_t * pObj, * pRepr, * pObjNew;
+ int i, Iter, fDisproved = 1;
+
+ // check if any output trivially fails under all-0 pattern
+ Gia_ManSetPhase( p );
+ if ( pPars->fIsMiter )
+ {
+ Gia_ManForEachCo( p, pObj, i )
+ if ( pObj->fPhase )
+ {
+ p->pCexSeq = Cec2_ManDeriveCex( p, i, -1 );
+ return 0;
+ }
+ }
+
+ // simulate one round and create classes
+ Cec2_ManSimAlloc( p, pPars->nSimWords );
+ Cec2_ManSimulateCis( p );
+ Cec2_ManSimulate( p, NULL, pMan );
+ if ( pPars->fIsMiter && !Cec2_ManSimulateCos(p) ) // cex detected
+ return 0;
+ Cec2_ManCreateClasses( p, pMan );
+ Cec2_ManPrintStats( p, pPars, pMan );
+
+ // perform additinal simulation
+ for ( i = 0; i < pPars->nSimRounds; i++ )
+ {
+ Cec2_ManSimulateCis( p );
+ Cec2_ManSimulate( p, NULL, pMan );
+ if ( pPars->fIsMiter && !Cec2_ManSimulateCos(p) ) // cex detected
+ return 0;
+ Cec2_ManPrintStats( p, pPars, pMan );
+ }
+ // perform sweeping
+ //pMan = Cec2_ManCreate( p, pPars );
+ for ( Iter = 0; fDisproved; Iter++ )
+ {
+ fDisproved = 0;
+ Cec2_ManSimulateCis( p );
+ Vec_IntClear( pMan->vCexTriples );
+ Gia_ManForEachAnd( p, pObj, i )
+ {
+ pObj->fMark1 = Gia_ObjFanin0(pObj)->fMark1 || Gia_ObjFanin1(pObj)->fMark1;
+ if ( pObj->fMark1 ) // skip nodes in the TFO of a disproved one
+ continue;
+ if ( ~pObj->Value ) // skip swept nodes
+ continue;
+ if ( !~Gia_ObjFanin0(pObj)->Value || !~Gia_ObjFanin1(pObj)->Value ) // skip fanouts of non-swept nodes
+ continue;
+ assert( !Gia_ObjProved(p, i) && !Gia_ObjFailed(p, i) );
+ // duplicate the node
+ pObj->Value = Gia_ManHashAnd( pMan->pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+ if ( Vec_IntSize(&pMan->pNew->vCopies) == Abc_Lit2Var(pObj->Value) )
+ {
+ pObjNew = Gia_ManObj( pMan->pNew, Abc_Lit2Var(pObj->Value) );
+ pObjNew->fMark0 = Gia_ObjIsMuxType( pObjNew );
+ Gia_ObjSetPhase( pMan->pNew, pObjNew );
+ Vec_IntPush( &pMan->pNew->vCopies, -1 );
+ }
+ assert( Vec_IntSize(&pMan->pNew->vCopies) == Gia_ManObjNum(pMan->pNew) );
+ pRepr = Gia_ObjReprObj( p, i );
+ if ( pRepr == NULL || pRepr->fMark1 || !~pRepr->Value )
+ continue;
+ if ( Abc_Lit2Var(pObj->Value) == Abc_Lit2Var(pRepr->Value) )
+ {
+ assert( (pObj->Value ^ pRepr->Value) == (pObj->fPhase ^ pRepr->fPhase) );
+ Gia_ObjSetProved( p, i );
+ continue;
+ }
+ if ( Cec2_ManSweepNode(pMan, i) )
+ continue;
+ pObj->Value = ~0;
+ //Vec_IntPushThree( pMan->vCexTriples, Gia_ObjId(p, pRepr), i, Abc_Var2Lit(p->iPatsPi, pObj->fPhase ^ pRepr->fPhase) );
+ // mark nodes as disproved
+ fDisproved = 1;
+ //if ( Iter > 5 )
+ continue;
+ if ( Gia_ObjIsAnd(pRepr) )
+ pRepr->fMark1 = 1;
+ pObj->fMark1 = 1;
+ }
+ if ( fDisproved )
+ {
+ //printf( "The number of pattern = %d.\n", p->iPatsPi );
+ Cec2_ManSimulate( p, pMan->vCexTriples, pMan );
+ if ( pPars->fIsMiter && !Cec2_ManSimulateCos(p) ) // cex detected
+ break;
+ }
+ Cec2_ManPrintStats( p, pPars, pMan );
+ }
+ Cec2_ManDestroy( pMan );
+ //Gia_ManEquivPrintClasses( p, 1, 0 );
+ return p->pCexSeq ? 0 : 1;
+}
+void Cec2_ManSimulateTest( Gia_Man_t * p )
+{
+ //abctime clk = Abc_Clock();
+ Cec2_Par_t Pars, * pPars = &Pars;
+ Cec2_SetDefaultParams( pPars );
+// Gia_ManComputeGiaEquivs( p, 100000, 0 );
+// Gia_ManEquivPrintClasses( p, 1, 0 );
+ Cec2_ManPerformSweeping( p, pPars );
+ //Abc_PrintTime( 1, "SAT sweeping time", Abc_Clock() - clk );
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/proof/cec/module.make b/src/proof/cec/module.make
index 82e0de74..38106e5e 100644
--- a/src/proof/cec/module.make
+++ b/src/proof/cec/module.make
@@ -6,6 +6,7 @@ SRC += src/proof/cec/cecCec.c \
src/proof/cec/cecIso.c \
src/proof/cec/cecMan.c \
src/proof/cec/cecPat.c \
+ src/proof/cec/cecSat.c \
src/proof/cec/cecSeq.c \
src/proof/cec/cecSolve.c \
src/proof/cec/cecSplit.c \
diff --git a/src/sat/bmc/bmcGen.c b/src/sat/bmc/bmcGen.c
index 5d84ce87..460c9fec 100644
--- a/src/sat/bmc/bmcGen.c
+++ b/src/sat/bmc/bmcGen.c
@@ -46,13 +46,13 @@ ABC_NAMESPACE_IMPL_START
***********************************************************************/
static inline word * Gia_ManMoObj( Gia_Man_t * p, int iObj )
{
- return Vec_WrdEntryP( p->vSims, iObj * p->iPatsPi );
+ return Vec_WrdEntryP( p->vSims, iObj * p->nSimWords );
}
static inline void Gia_ManMoSetCi( Gia_Man_t * p, int iObj )
{
int w;
word * pSims = Gia_ManMoObj( p, iObj );
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = Gia_ManRandomW( 0 );
}
static inline void Gia_ManMoSimAnd( Gia_Man_t * p, int iObj )
@@ -65,19 +65,19 @@ static inline void Gia_ManMoSimAnd( Gia_Man_t * p, int iObj )
if ( Gia_ObjFaninC0(pObj) )
{
if ( Gia_ObjFaninC1(pObj) )
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = ~(pSims0[w] | pSims1[w]);
else
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = ~pSims0[w] & pSims1[w];
}
else
{
if ( Gia_ObjFaninC1(pObj) )
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = pSims0[w] & ~pSims1[w];
else
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = pSims0[w] & pSims1[w];
}
}
@@ -89,12 +89,12 @@ static inline void Gia_ManMoSetCo( Gia_Man_t * p, int iObj )
word * pSims0 = Gia_ManMoObj( p, Gia_ObjFaninId0(pObj, iObj) );
if ( Gia_ObjFaninC0(pObj) )
{
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = ~pSims0[w];
}
else
{
- for ( w = 0; w < p->iPatsPi; w++ )
+ for ( w = 0; w < p->nSimWords; w++ )
pSims[w] = pSims0[w];
}
}
@@ -102,7 +102,7 @@ void Gia_ManMoFindSimulate( Gia_Man_t * p, int nWords )
{
int i, iObj;
Gia_ManRandomW( 1 );
- p->iPatsPi = nWords;
+ p->nSimWords = nWords;
if ( p->vSims )
Vec_WrdFill( p->vSims, nWords * Gia_ManObjNum(p), 0 );
else
diff --git a/src/sat/satoko/cdb.h b/src/sat/satoko/cdb.h
index 28686ff2..32b0bf93 100644
--- a/src/sat/satoko/cdb.h
+++ b/src/sat/satoko/cdb.h
@@ -81,6 +81,12 @@ static inline void cdb_remove(struct cdb *p, struct clause *clause)
p->wasted += clause->size;
}
+static inline void cdb_clear(struct cdb *p)
+{
+ p->wasted = 0;
+ p->size = 0;
+}
+
static inline unsigned cdb_capacity(struct cdb *p)
{
return p->cap;
diff --git a/src/sat/satoko/cnf_reader.c b/src/sat/satoko/cnf_reader.c
index 9fbbda65..adb9a47b 100644
--- a/src/sat/satoko/cnf_reader.c
+++ b/src/sat/satoko/cnf_reader.c
@@ -141,7 +141,7 @@ int satoko_parse_dimacs(char *fname, satoko_t **solver)
return -1;
}
read_clause(&token, lits);
- if (!satoko_add_clause(p, vec_uint_data(lits), vec_uint_size(lits))) {
+ if (!satoko_add_clause(p, (int*)vec_uint_data(lits), vec_uint_size(lits))) {
vec_uint_print(lits);
return 0;
}
diff --git a/src/sat/satoko/satoko.h b/src/sat/satoko/satoko.h
index 88070eac..a0c4d216 100644
--- a/src/sat/satoko/satoko.h
+++ b/src/sat/satoko/satoko.h
@@ -80,12 +80,14 @@ struct satoko_stats {
//===------------------------------------------------------------------------===
extern satoko_t *satoko_create(void);
extern void satoko_destroy(satoko_t *);
+extern void satoko_reset(satoko_t *);
+
extern void satoko_default_opts(satoko_opts_t *);
extern void satoko_configure(satoko_t *, satoko_opts_t *);
extern int satoko_parse_dimacs(char *, satoko_t **);
-extern void satoko_add_variable(satoko_t *, char);
-extern int satoko_add_clause(satoko_t *, unsigned *, unsigned);
-extern void satoko_assump_push(satoko_t *s, unsigned);
+extern int satoko_add_variable(satoko_t *, char);
+extern int satoko_add_clause(satoko_t *, int *, int);
+extern void satoko_assump_push(satoko_t *s, int);
extern void satoko_assump_pop(satoko_t *s);
extern int satoko_simplify(satoko_t *);
extern int satoko_solve(satoko_t *);
diff --git a/src/sat/satoko/solver.c b/src/sat/satoko/solver.c
index 21a4860d..af3dcffb 100644
--- a/src/sat/satoko/solver.c
+++ b/src/sat/satoko/solver.c
@@ -195,7 +195,7 @@ static inline unsigned solver_decide(solver_t *s)
if (solver_has_marks(s) && !var_mark(s, next_var))
next_var = UNDEF;
}
- return var2lit(next_var, vec_char_at(s->polarity, next_var));
+ return var2lit(next_var, var_polarity(s, next_var));
}
static inline void solver_new_decision(solver_t *s, unsigned lit)
@@ -362,13 +362,14 @@ static inline void solver_handle_conflict(solver_t *s, unsigned confl_cref)
static inline void solver_analyze_final(solver_t *s, unsigned lit)
{
- unsigned i;
+ int i;
+ vec_uint_clear(s->final_conflict);
vec_uint_push_back(s->final_conflict, lit);
if (solver_dlevel(s) == 0)
return;
vec_char_assign(s->seen, lit2var(lit), 1);
- for (i = vec_uint_size(s->trail) - 1; i <= vec_uint_at(s->trail_lim, 0); i--) {
+ for (i = (int) vec_uint_size(s->trail) - 1; i >= (int) vec_uint_at(s->trail_lim, 0); i--) {
unsigned var = lit2var(vec_uint_at(s->trail, i));
if (vec_char_at(s->seen, var)) {
@@ -396,6 +397,9 @@ static inline void solver_garbage_collect(solver_t *s)
unsigned *array;
struct cdb *new_cdb = cdb_alloc(cdb_capacity(s->all_clauses) - cdb_wasted(s->all_clauses));
+ if (s->book_cdb)
+ s->book_cdb = 0;
+
for (i = 0; i < 2 * vec_char_size(s->assigns); i++) {
struct watcher *w;
watch_list_foreach(s->watches, w, i)
diff --git a/src/sat/satoko/solver.h b/src/sat/satoko/solver.h
index 68cc97dc..33f8ce88 100644
--- a/src/sat/satoko/solver.h
+++ b/src/sat/satoko/solver.h
@@ -95,6 +95,7 @@ struct solver_t_ {
/* Bookmark */
unsigned book_cl_orig; /* Bookmark for orignal problem clauses vector */
unsigned book_cl_lrnt; /* Bookmark for learnt clauses vector */
+ unsigned book_cdb; /* Bookmark clause database size */
unsigned book_vars; /* Bookmark number of variables */
unsigned book_trail; /* Bookmark trail size */
@@ -132,6 +133,11 @@ static inline char var_value(solver_t *s, unsigned var)
return vec_char_at(s->assigns, var);
}
+static inline char var_polarity(solver_t *s, unsigned var)
+{
+ return vec_char_at(s->polarity, var);
+}
+
static inline unsigned var_dlevel(solver_t *s, unsigned var)
{
return vec_uint_at(s->levels, var);
diff --git a/src/sat/satoko/solver_api.c b/src/sat/satoko/solver_api.c
index 9cad0a14..3cb9f3d3 100644
--- a/src/sat/satoko/solver_api.c
+++ b/src/sat/satoko/solver_api.c
@@ -216,7 +216,7 @@ int satoko_simplify(solver_t * s)
return SATOKO_OK;
}
-void satoko_add_variable(solver_t *s, char sign)
+int satoko_add_variable(solver_t *s, char sign)
{
unsigned var = vec_act_size(s->activity);
vec_wl_push(s->watches);
@@ -231,9 +231,10 @@ void satoko_add_variable(solver_t *s, char sign)
heap_insert(s->var_order, var);
if (s->marks)
vec_char_push_back(s->marks, 0);
+ return var;
}
-int satoko_add_clause(solver_t *s, unsigned *lits, unsigned size)
+int satoko_add_clause(solver_t *s, int *lits, int size)
{
unsigned i, j;
unsigned prev_lit;
@@ -248,10 +249,10 @@ int satoko_add_clause(solver_t *s, unsigned *lits, unsigned size)
vec_uint_clear(s->temp_lits);
j = 0;
prev_lit = UNDEF;
- for (i = 0; i < size; i++) {
- if (lits[i] == lit_neg(prev_lit) || lit_value(s, lits[i]) == LIT_TRUE)
+ for (i = 0; i < (unsigned)size; i++) {
+ if ((unsigned)lits[i] == lit_neg(prev_lit) || lit_value(s, lits[i]) == LIT_TRUE)
return SATOKO_OK;
- else if (lits[i] != prev_lit && var_value(s, lit2var(lits[i])) == VAR_UNASSING) {
+ else if ((unsigned)lits[i] != prev_lit && var_value(s, lit2var(lits[i])) == VAR_UNASSING) {
prev_lit = lits[i];
vec_uint_push_back(s->temp_lits, lits[i]);
}
@@ -269,7 +270,7 @@ int satoko_add_clause(solver_t *s, unsigned *lits, unsigned size)
return SATOKO_OK;
}
-void satoko_assump_push(solver_t *s, unsigned lit)
+void satoko_assump_push(solver_t *s, int lit)
{
vec_uint_push_back(s->assumptions, lit);
}
@@ -329,6 +330,43 @@ void satoko_unbookmark(satoko_t *s)
{
s->book_cl_orig = 0;
s->book_cl_lrnt = 0;
+ s->book_cdb = 0;
+ s->book_vars = 0;
+ s->book_trail = 0;
+}
+
+void satoko_reset(satoko_t *s)
+{
+ vec_uint_clear(s->assumptions);
+ vec_uint_clear(s->final_conflict);
+ cdb_clear(s->all_clauses);
+ vec_uint_clear(s->originals);
+ vec_uint_clear(s->learnts);
+ vec_wl_clean(s->watches);
+ vec_act_clear(s->activity);
+ heap_clear(s->var_order);
+ vec_uint_clear(s->levels);
+ vec_uint_clear(s->reasons);
+ vec_char_clear(s->assigns);
+ vec_char_clear(s->polarity);
+ vec_uint_clear(s->trail);
+ vec_uint_clear(s->trail_lim);
+ b_queue_clean(s->bq_lbd);
+ b_queue_clean(s->bq_trail);
+ vec_uint_clear(s->temp_lits);
+ vec_char_clear(s->seen);
+ vec_uint_clear(s->tagged);
+ vec_uint_clear(s->stack);
+ vec_uint_clear(s->last_dlevel);
+ vec_uint_clear(s->stamps);
+ s->var_act_inc = VAR_ACT_INIT_INC;
+ s->clause_act_inc = CLAUSE_ACT_INIT_INC;
+ s->n_confl_bfr_reduce = s->opts.n_conf_fst_reduce;
+ s->RC1 = 1;
+ s->RC2 = s->opts.n_conf_fst_reduce;
+ s->book_cl_orig = 0;
+ s->book_cl_lrnt = 0;
+ s->book_cdb = 0;
s->book_vars = 0;
s->book_trail = 0;
}
@@ -341,6 +379,11 @@ void satoko_rollback(satoko_t *s)
struct clause **cl_to_remove;
assert(solver_dlevel(s) == 0);
+ if (!s->book_vars) {
+ satoko_reset(s);
+ return;
+ }
+
cl_to_remove = satoko_alloc(struct clause *, n_originals + n_learnts);
/* Mark clauses */
vec_uint_foreach_start(s->originals, cref, i, s->book_cl_orig)
@@ -351,18 +394,28 @@ void satoko_rollback(satoko_t *s)
clause_unwatch(s, cdb_cref(s->all_clauses, (unsigned *)cl_to_remove[i]));
cl_to_remove[i]->f_mark = 1;
}
+ satoko_free(cl_to_remove);
vec_uint_shrink(s->originals, s->book_cl_orig);
vec_uint_shrink(s->learnts, s->book_cl_lrnt);
/* Shrink variable related vectors */
+ for (i = s->book_vars; i < 2 * vec_char_size(s->assigns); i++) {
+ vec_wl_at(s->watches, i)->size = 0;
+ vec_wl_at(s->watches, i)->n_bin = 0;
+ }
+ s->watches->size = s->book_vars;
vec_act_shrink(s->activity, s->book_vars);
vec_uint_shrink(s->levels, s->book_vars);
vec_uint_shrink(s->reasons, s->book_vars);
+ vec_uint_shrink(s->stamps, s->book_vars);
vec_char_shrink(s->assigns, s->book_vars);
+ vec_char_shrink(s->seen, s->book_vars);
vec_char_shrink(s->polarity, s->book_vars);
solver_rebuild_order(s);
/* Rewind solver and cancel level 0 assignments to the trail */
solver_cancel_until(s, 0);
vec_uint_shrink(s->trail, s->book_trail);
+ if (s->book_cdb)
+ s->all_clauses->size = s->book_cdb;
s->book_cl_orig = 0;
s->book_cl_lrnt = 0;
s->book_vars = 0;
diff --git a/src/sat/satoko/types.h b/src/sat/satoko/types.h
index 9c47ca7c..06c190ab 100644
--- a/src/sat/satoko/types.h
+++ b/src/sat/satoko/types.h
@@ -26,6 +26,7 @@ typedef vec_sdbl_t vec_act_t ;
#define vec_act_free(vec) vec_sdbl_free(vec)
#define vec_act_size(vec) vec_sdbl_size(vec)
#define vec_act_data(vec) vec_sdbl_data(vec)
+#define vec_act_clear(vec) vec_sdbl_clear(vec)
#define vec_act_shrink(vec, size) vec_sdbl_shrink(vec, size)
#define vec_act_at(vec, idx) vec_sdbl_at(vec, idx)
#define vec_act_push_back(vec, value) vec_sdbl_push_back(vec, value)
diff --git a/src/sat/satoko/utils/heap.h b/src/sat/satoko/utils/heap.h
index 8b1d8f4b..391b8a7e 100644
--- a/src/sat/satoko/utils/heap.h
+++ b/src/sat/satoko/utils/heap.h
@@ -158,10 +158,7 @@ static inline void heap_build(heap_t *p, vec_uint_t *entries)
static inline void heap_clear(heap_t *p)
{
- unsigned i;
- int entry;
- vec_int_foreach(p->indices, entry, i)
- vec_int_assign(p->indices, i, -1);
+ vec_int_clear(p->indices);
vec_uint_clear(p->data);
}
diff --git a/src/sat/satoko/watch_list.h b/src/sat/satoko/watch_list.h
index 49f419f2..1bcbf3b4 100644
--- a/src/sat/satoko/watch_list.h
+++ b/src/sat/satoko/watch_list.h
@@ -154,12 +154,22 @@ static inline vec_wl_t *vec_wl_alloc(unsigned cap)
static inline void vec_wl_free(vec_wl_t *vec_wl)
{
unsigned i;
- for (i = 0; i < vec_wl->size; i++)
+ for (i = 0; i < vec_wl->cap; i++)
watch_list_free(vec_wl->watch_lists + i);
satoko_free(vec_wl->watch_lists);
satoko_free(vec_wl);
}
+static inline void vec_wl_clean(vec_wl_t *vec_wl)
+{
+ unsigned i;
+ for (i = 0; i < vec_wl->size; i++) {
+ vec_wl->watch_lists[i].size = 0;
+ vec_wl->watch_lists[i].n_bin = 0;
+ }
+ vec_wl->size = 0;
+}
+
static inline void vec_wl_push(vec_wl_t *vec_wl)
{
if (vec_wl->size == vec_wl->cap) {
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-07 20:30:12 +0000