diff options
Diffstat (limited to 'src/sat/bmc')
-rw-r--r-- | src/sat/bmc/bmcEco.c | 297 |
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 + |