summaryrefslogtreecommitdiffstats
path: root/src/sat
diff options
context:
space:
mode:
authorAlan Mishchenko <alanmi@berkeley.edu>2014-05-21 12:41:34 +0900
committerAlan Mishchenko <alanmi@berkeley.edu>2014-05-21 12:41:34 +0900
commitab85108c62757868cba4fdafe9c344869d469879 (patch)
tree46c61989aab6141d0a3411189502bd7d5ce717be /src/sat
parent368de31ae2c92ca02a568f6d96472dc2d54164f2 (diff)
downloadabc-ab85108c62757868cba4fdafe9c344869d469879.tar.gz
abc-ab85108c62757868cba4fdafe9c344869d469879.tar.bz2
abc-ab85108c62757868cba4fdafe9c344869d469879.zip
Simple version of ECO.
Diffstat (limited to 'src/sat')
-rw-r--r--src/sat/bmc/bmcEco.c297
1 files changed, 297 insertions, 0 deletions
diff --git a/src/sat/bmc/bmcEco.c b/src/sat/bmc/bmcEco.c
new file mode 100644
index 00000000..5f0313f5
--- /dev/null
+++ b/src/sat/bmc/bmcEco.c
@@ -0,0 +1,297 @@
+/**CFile****************************************************************
+
+ FileName [bmcEco.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [SAT-based bounded model checking.]
+
+ Synopsis []
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: bmcEco.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "bmc.h"
+#include "sat/cnf/cnf.h"
+#include "sat/bsat/satSolver.h"
+#include "aig/gia/giaAig.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Computes miter for ECO with given root node and fanins.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Gia_Man_t * Bmc_EcoMiter( Gia_Man_t * pGold, Gia_Man_t * pOld, Vec_Int_t * vFans )
+{
+ Gia_Man_t * pNew, * pTemp;
+ Gia_Obj_t * pRoot = Gia_ObjFanin0( Gia_ManPo(pOld, Gia_ManPoNum(pOld)-1) ); // fanin of the last PO
+ Gia_Obj_t * pObj;
+ int i, NewPi, Miter;
+ assert( Gia_ManCiNum(pGold) == Gia_ManCiNum(pOld) );
+ assert( Gia_ManCoNum(pGold) == Gia_ManCoNum(pOld) - 1 );
+ assert( Gia_ObjIsAnd(pRoot) );
+ // create the miter
+ pNew = Gia_ManStart( 3 * Gia_ManObjNum(pGold) );
+ pNew->pName = Abc_UtilStrsav( pGold->pName );
+ Gia_ManHashAlloc( pNew );
+ // copy gold
+ Gia_ManConst0(pGold)->Value = 0;
+ Gia_ManForEachCi( pGold, pObj, i )
+ pObj->Value = Gia_ManAppendCi( pNew );
+ NewPi = Gia_ManAppendCi( pNew );
+ Gia_ManForEachAnd( pGold, pObj, i )
+ pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+ Gia_ManForEachCo( pGold, pObj, i )
+ pObj->Value = Gia_ObjFanin0Copy( pObj );
+ // create onset
+ Gia_ManConst0(pOld)->Value = 0;
+ Gia_ManForEachCi( pOld, pObj, i )
+ pObj->Value = Gia_ManCi(pGold, i)->Value;
+ Gia_ManForEachAnd( pOld, pObj, i )
+ if ( pObj == pRoot )
+ pObj->Value = NewPi;
+ else
+ pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+ Gia_ManForEachCo( pOld, pObj, i )
+ pObj->Value = Gia_ObjFanin0Copy( pObj );
+ Gia_ManForEachCo( pGold, pObj, i )
+ Gia_ManAppendCo( pNew, Gia_ManHashXor(pNew, pObj->Value, Gia_ManCo(pOld, i)->Value) );
+ // create offset
+ Gia_ManForEachAnd( pOld, pObj, i )
+ if ( pObj == pRoot )
+ pObj->Value = Abc_LitNot(NewPi);
+ else
+ pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+ Gia_ManForEachCo( pOld, pObj, i )
+ pObj->Value = Gia_ObjFanin0Copy( pObj );
+ Miter = 0;
+ Gia_ManForEachCo( pGold, pObj, i )
+ Miter = Gia_ManHashOr( pNew, Miter, Gia_ManHashXor(pNew, pObj->Value, Gia_ManCo(pOld, i)->Value) );
+ Gia_ManAppendCo( pNew, Miter );
+ // add outputs for the nodes
+ Gia_ManForEachObjVec( vFans, pOld, pObj, i )
+ Gia_ManAppendCo( pNew, pObj->Value );
+ // cleanup
+ pNew = Gia_ManCleanup( pTemp = pNew );
+ Gia_ManStop( pTemp );
+ assert( Gia_ManPiNum(pNew) == Gia_ManCiNum(pGold) + 1 );
+ assert( Gia_ManPoNum(pNew) == Gia_ManCoNum(pGold) + 1 + Vec_IntSize(vFans) );
+ return pNew;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline Cnf_Dat_t * Cnf_DeriveGiaRemapped( Gia_Man_t * p )
+{
+ Cnf_Dat_t * pCnf;
+ Aig_Man_t * pAig = Gia_ManToAigSimple( p );
+ pAig->nRegs = 0;
+ pCnf = Cnf_Derive( pAig, Aig_ManCoNum(pAig) );
+ Aig_ManStop( pAig );
+ return pCnf;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Solve the enumeration problem.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Bmc_EcoSolve( sat_solver * pSat, int Root, Vec_Int_t * vVars )
+{
+ int nBTLimit = 1000000;
+ Vec_Int_t * vValues = Vec_IntAlloc( Vec_IntSize(vVars) );
+ Vec_Int_t * vLits = Vec_IntAlloc( Vec_IntSize(vVars) );
+ int status, i, Div, iVar, nFinal, * pFinal, nIter = 0, RetValue = 0;
+ int pLits[2], nVars = sat_solver_nvars( pSat );
+ sat_solver_setnvars( pSat, nVars + 1 );
+ pLits[0] = Abc_Var2Lit( Root, 0 ); // F = 1
+ pLits[1] = Abc_Var2Lit( nVars, 0 ); // iNewLit
+ while ( 1 )
+ {
+ // find onset minterm
+ status = sat_solver_solve( pSat, pLits, pLits + 2, nBTLimit, 0, 0, 0 );
+ if ( status == l_Undef )
+ { RetValue = -1; break; }
+ if ( status == l_False )
+ { RetValue = 1; break; }
+ assert( status == l_True );
+ // remember variable values
+ Vec_IntClear( vValues );
+ Vec_IntForEachEntry( vVars, iVar, i )
+ Vec_IntPush( vValues, sat_solver_var_value(pSat, iVar) );
+ // collect divisor literals
+ Vec_IntClear( vLits );
+ Vec_IntPush( vLits, Abc_LitNot(pLits[0]) ); // F = 0
+ Vec_IntForEachEntry( vVars, Div, i )
+ Vec_IntPush( vLits, sat_solver_var_literal(pSat, Div) );
+ // check against offset
+ status = sat_solver_solve( pSat, Vec_IntArray(vLits), Vec_IntArray(vLits) + Vec_IntSize(vLits), nBTLimit, 0, 0, 0 );
+ if ( status == l_Undef )
+ { RetValue = -1; break; }
+ if ( status == l_True )
+ break;
+ assert( status == l_False );
+ // compute cube and add clause
+ nFinal = sat_solver_final( pSat, &pFinal );
+ Vec_IntClear( vLits );
+ Vec_IntPush( vLits, Abc_LitNot(pLits[1]) ); // NOT(iNewLit)
+ printf( "Cube %d : ", nIter );
+ for ( i = 0; i < nFinal; i++ )
+ {
+ if ( pFinal[i] == pLits[0] )
+ continue;
+ Vec_IntPush( vLits, pFinal[i] );
+ iVar = Vec_IntFind( vVars, Abc_Lit2Var(pFinal[i]) ); assert( iVar >= 0 );
+ printf( "%s%d ", Abc_LitIsCompl(pFinal[i]) ? "+":"-", iVar );
+ }
+ printf( "\n" );
+ status = sat_solver_addclause( pSat, Vec_IntArray(vLits), Vec_IntArray(vLits) + Vec_IntSize(vLits) );
+ assert( status );
+ nIter++;
+ }
+// assert( status == l_True );
+ Vec_IntFree( vValues );
+ Vec_IntFree( vLits );
+ return RetValue;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compute the patch function.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Bmc_EcoPatch( Gia_Man_t * p, int nIns, int nOuts )
+{
+ int i, Lit, RetValue, Root;
+ Gia_Obj_t * pObj;
+ Vec_Int_t * vVars;
+ // generate CNF and solver
+ Cnf_Dat_t * pCnf = Cnf_DeriveGiaRemapped( p );
+ sat_solver * pSat = sat_solver_new();
+ sat_solver_setnvars( pSat, pCnf->nVars );
+ // add timeframe clauses
+ for ( i = 0; i < pCnf->nClauses; i++ )
+ if ( !sat_solver_addclause( pSat, pCnf->pClauses[i], pCnf->pClauses[i+1] ) )
+ assert( 0 );
+ // add equality constraints
+ assert( Gia_ManPoNum(p) == nOuts + 1 + nIns );
+ Gia_ManForEachPo( p, pObj, i )
+ {
+ if ( i == nOuts )
+ break;
+ Lit = Abc_Var2Lit( pCnf->pVarNums[Gia_ObjId(p, pObj)], 1 ); // neg lit
+ RetValue = sat_solver_addclause( pSat, &Lit, &Lit + 1 );
+ assert( RetValue );
+ }
+ // add inequality constraint
+ pObj = Gia_ManPo( p, nOuts );
+ Lit = Abc_Var2Lit( pCnf->pVarNums[Gia_ObjId(p, pObj)], 0 ); // pos lit
+ RetValue = sat_solver_addclause( pSat, &Lit, &Lit + 1 );
+ assert( RetValue );
+ // simplify the SAT solver
+ RetValue = sat_solver_simplify( pSat );
+ assert( RetValue );
+ // collect input variables
+ vVars = Vec_IntAlloc( nIns );
+ Gia_ManForEachPo( p, pObj, i )
+ if ( i >= nOuts + 1 )
+ Vec_IntPush( vVars, pCnf->pVarNums[Gia_ObjId(p, pObj)] );
+ assert( Vec_IntSize(vVars) == nIns );
+ // derive the root variable
+ pObj = Gia_ManPi( p, Gia_ManPiNum(p) - 1 );
+ Root = pCnf->pVarNums[Gia_ObjId(p, pObj)];
+ // solve the problem
+ RetValue = Bmc_EcoSolve( pSat, Root, vVars );
+ Vec_IntFree( vVars );
+ return RetValue;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Tests the ECO miter.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Bmc_EcoMiterTest()
+{
+ Vec_Int_t * vFans;
+ Gia_Man_t * pMiter;
+ Gia_Obj_t * pObj;
+ Gia_Man_t * pGold = Gia_AigerRead( "eco_gold.aig", 0, 0 );
+ Gia_Man_t * pOld = Gia_AigerRead( "eco_old.aig", 0, 0 );
+ int i, RetValue;
+ // create ECO miter
+ vFans = Vec_IntAlloc( Gia_ManCiNum(pOld) );
+ Gia_ManForEachCi( pOld, pObj, i )
+ Vec_IntPush( vFans, Gia_ObjId(pOld, pObj) );
+ pMiter = Bmc_EcoMiter( pGold, pOld, vFans );
+ Vec_IntFree( vFans );
+ Gia_AigerWrite( pMiter, "eco_miter.aig", 0, 0 );
+ // find the patch
+ RetValue = Bmc_EcoPatch( pMiter, Gia_ManCiNum(pGold), Gia_ManCoNum(pGold) );
+ if ( RetValue == 1 )
+ printf( "Patch is computed.\n" );
+ if ( RetValue == 0 )
+ printf( "Cannot be patched.\n" );
+ if ( RetValue == -1 )
+ printf( "Resource limit exceeded.\n" );
+ Gia_ManStop( pMiter );
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+