diff options
Diffstat (limited to 'src/aig/saig')
-rw-r--r-- | src/aig/saig/module.make | 1 | ||||
-rw-r--r-- | src/aig/saig/saig.h | 2 | ||||
-rw-r--r-- | src/aig/saig/saigAbs.c | 37 | ||||
-rw-r--r-- | src/aig/saig/saigBmc.c | 14 | ||||
-rw-r--r-- | src/aig/saig/saigInd.c | 174 | ||||
-rw-r--r-- | src/aig/saig/saigLoc.c | 127 |
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 /// |