diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2012-09-15 23:27:46 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2012-09-15 23:27:46 -0700 |
commit | 69bbfa98564efc7a8b865f06b01c0e404ac1e658 (patch) | |
tree | 188c18f4c23b986b1b1647738e4e14fe63513ec5 /src/aig/saig | |
parent | ec95f569dd543d6a6acc8b9910cb605f14e59e61 (diff) | |
download | abc-69bbfa98564efc7a8b865f06b01c0e404ac1e658.tar.gz abc-69bbfa98564efc7a8b865f06b01c0e404ac1e658.tar.bz2 abc-69bbfa98564efc7a8b865f06b01c0e404ac1e658.zip |
Created new abstraction package from the code that was all over the place.
Diffstat (limited to 'src/aig/saig')
-rw-r--r-- | src/aig/saig/module.make | 13 | ||||
-rw-r--r-- | src/aig/saig/saig.h | 26 | ||||
-rw-r--r-- | src/aig/saig/saigAbs.c | 133 | ||||
-rw-r--r-- | src/aig/saig/saigAbsCba.c | 874 | ||||
-rw-r--r-- | src/aig/saig/saigAbsPba.c | 374 | ||||
-rw-r--r-- | src/aig/saig/saigAbsStart.c | 310 | ||||
-rw-r--r-- | src/aig/saig/saigAbsVfa.c | 329 | ||||
-rw-r--r-- | src/aig/saig/saigSimExt.c | 556 | ||||
-rw-r--r-- | src/aig/saig/saigSimExt2.c | 481 |
9 files changed, 1 insertions, 3095 deletions
diff --git a/src/aig/saig/module.make b/src/aig/saig/module.make index 42e3c090..edf5798e 100644 --- a/src/aig/saig/module.make +++ b/src/aig/saig/module.make @@ -1,9 +1,4 @@ -SRC += src/aig/saig/saigAbs.c \ - src/aig/saig/saigAbsCba.c \ - src/aig/saig/saigAbsPba.c \ - src/aig/saig/saigAbsStart.c \ - src/aig/saig/saigAbsVfa.c \ - src/aig/saig/saigBmc.c \ +SRC += src/aig/saig/saigBmc.c \ src/aig/saig/saigBmc2.c \ src/aig/saig/saigBmc3.c \ src/aig/saig/saigCexMin.c \ @@ -12,9 +7,6 @@ SRC += src/aig/saig/saigAbs.c \ src/aig/saig/saigConstr2.c \ src/aig/saig/saigDual.c \ src/aig/saig/saigDup.c \ - src/aig/saig/saigGlaCba.c \ - src/aig/saig/saigGlaPba.c \ - src/aig/saig/saigGlaPba2.c \ src/aig/saig/saigHaig.c \ src/aig/saig/saigInd.c \ src/aig/saig/saigIoa.c \ @@ -24,13 +16,10 @@ SRC += src/aig/saig/saigAbs.c \ src/aig/saig/saigMiter.c \ src/aig/saig/saigOutDec.c \ src/aig/saig/saigPhase.c \ - src/aig/saig/saigRefSat.c \ src/aig/saig/saigRetFwd.c \ src/aig/saig/saigRetMin.c \ src/aig/saig/saigRetStep.c \ src/aig/saig/saigScl.c \ - src/aig/saig/saigSimExt.c \ - src/aig/saig/saigSimExt2.c \ src/aig/saig/saigSimFast.c \ src/aig/saig/saigSimMv.c \ src/aig/saig/saigSimSeq.c \ diff --git a/src/aig/saig/saig.h b/src/aig/saig/saig.h index e7cdea90..8823dcac 100644 --- a/src/aig/saig/saig.h +++ b/src/aig/saig/saig.h @@ -27,7 +27,6 @@ //////////////////////////////////////////////////////////////////////// #include "aig/aig/aig.h" -#include "aig/gia/giaAbs.h" ABC_NAMESPACE_HEADER_START @@ -35,10 +34,6 @@ ABC_NAMESPACE_HEADER_START /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// -#define SAIG_ZER 1 -#define SAIG_ONE 2 -#define SAIG_UND 3 - //////////////////////////////////////////////////////////////////////// /// BASIC TYPES /// //////////////////////////////////////////////////////////////////////// @@ -131,20 +126,6 @@ static inline int Saig_ObjRegId( Aig_Man_t * p, Aig_Obj_t * pObj ) { /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -/*=== sswAbs.c ==========================================================*/ -extern Vec_Int_t * Saig_ManClasses2Flops( Vec_Int_t * vFlopClasses ); -extern Vec_Int_t * Saig_ManFlops2Classes( int nRegs, Vec_Int_t * vFlops ); -extern Abc_Cex_t * Saig_ManCexRemap( Aig_Man_t * p, Aig_Man_t * pAbs, Abc_Cex_t * pCexAbs ); -/*=== sswAbsCba.c ==========================================================*/ -extern Vec_Int_t * Saig_ManCbaFilterFlops( Aig_Man_t * pAig, Abc_Cex_t * pAbsCex, Vec_Int_t * vFlopClasses, Vec_Int_t * vAbsFfsToAdd, int nFfsToSelect ); -extern Abc_Cex_t * Saig_ManCbaFindCexCareBits( Aig_Man_t * pAig, Abc_Cex_t * pCex, int nInputs, int fVerbose ); -extern Vec_Int_t * Saig_ManCbaFilterInputs( Aig_Man_t * pAig, int iFirstFlopPi, Abc_Cex_t * pCex, int fVerbose ); -extern Vec_Int_t * Saig_ManCbaPerform( Aig_Man_t * pAig, int nInputs, Saig_ParBmc_t * pPars ); -/*=== sswAbsPba.c ==========================================================*/ -extern Vec_Int_t * Saig_ManPbaDerive( Aig_Man_t * pAig, int nInputs, int nStart, int nFrames, int nConfLimit, int nTimeLimit, int fVerbose, int * piFrame ); -/*=== sswAbsStart.c ==========================================================*/ -extern int Saig_ManCexRefineStep( Aig_Man_t * p, Vec_Int_t * vFlops, Vec_Int_t * vFlopClasses, Abc_Cex_t * pCex, int nFfToAddMax, int fTryFour, int fSensePath, int fVerbose ); -extern Vec_Int_t * Saig_ManCexAbstractionFlops( Aig_Man_t * p, Gia_ParAbs_t * pPars ); /*=== saigBmc.c ==========================================================*/ extern int Saig_ManBmcSimple( Aig_Man_t * pAig, int nFrames, int nSizeMax, int nBTLimit, int fRewrite, int fVerbose, int * piFrame, int nCofFanLit ); extern int Saig_BmcPerform( Aig_Man_t * pAig, int nStart, int nFramesMax, int nNodesMax, int nTimeOut, int nConfMaxOne, int nConfMaxAll, int fVerbose, int fVerbOverwrite, int * piFrames, int fSilent ); @@ -203,8 +184,6 @@ extern int Saig_ManDemiterNew( Aig_Man_t * pMan ); extern Aig_Man_t * Saig_ManDecPropertyOutput( Aig_Man_t * pAig, int nLits, int fVerbose ); /*=== saigPhase.c ==========================================================*/ extern Aig_Man_t * Saig_ManPhaseAbstract( Aig_Man_t * p, Vec_Int_t * vInits, int nFrames, int nPref, int fIgnore, int fPrint, int fVerbose ); -/*=== saigRefSat.c ==========================================================*/ -extern Vec_Int_t * Saig_ManExtendCounterExampleTest3( Aig_Man_t * pAig, int iFirstFlopPi, Abc_Cex_t * pCex, int fVerbose ); /*=== saigRetFwd.c ==========================================================*/ extern void Saig_ManMarkAutonomous( Aig_Man_t * p ); extern Aig_Man_t * Saig_ManRetimeForward( Aig_Man_t * p, int nMaxIters, int fVerbose ); @@ -215,11 +194,6 @@ extern Aig_Man_t * Saig_ManRetimeMinArea( Aig_Man_t * p, int nMaxIters, in extern int Saig_ManRetimeSteps( Aig_Man_t * p, int nSteps, int fForward, int fAddBugs ); /*=== saigScl.c ==========================================================*/ extern void Saig_ManReportUselessRegisters( Aig_Man_t * pAig ); -/*=== saigSimExt.c ==========================================================*/ -extern Vec_Int_t * Saig_ManExtendCounterExample( Aig_Man_t * p, int iFirstPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ); -extern Vec_Int_t * Saig_ManExtendCounterExampleTest( Aig_Man_t * p, int iFirstPi, Abc_Cex_t * pCex, int fTryFour, int fVerbose ); -/*=== saigSimExt.c ==========================================================*/ -extern Vec_Int_t * Saig_ManExtendCounterExampleTest2( Aig_Man_t * p, int iFirstPi, Abc_Cex_t * pCex, int fVerbose ); /*=== saigSimMv.c ==========================================================*/ extern Vec_Ptr_t * Saig_MvManSimulate( Aig_Man_t * pAig, int nFramesSymb, int nFramesSatur, int fVerbose, int fVeryVerbose ); /*=== saigStrSim.c ==========================================================*/ diff --git a/src/aig/saig/saigAbs.c b/src/aig/saig/saigAbs.c deleted file mode 100644 index f30963a8..00000000 --- a/src/aig/saig/saigAbs.c +++ /dev/null @@ -1,133 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigAbs.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [Intergrated abstraction procedure.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigAbs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Transform flop map into flop list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManClasses2Flops( Vec_Int_t * vFlopClasses ) -{ - Vec_Int_t * vFlops; - int i, Entry; - vFlops = Vec_IntAlloc( 100 ); - Vec_IntForEachEntry( vFlopClasses, Entry, i ) - if ( Entry ) - Vec_IntPush( vFlops, i ); - return vFlops; -} - -/**Function************************************************************* - - Synopsis [Transform flop list into flop map.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManFlops2Classes( int nRegs, Vec_Int_t * vFlops ) -{ - Vec_Int_t * vFlopClasses; - int i, Entry; - vFlopClasses = Vec_IntStart( nRegs ); - Vec_IntForEachEntry( vFlops, Entry, i ) - Vec_IntWriteEntry( vFlopClasses, Entry, 1 ); - return vFlopClasses; -} - -/**Function************************************************************* - - Synopsis [Derive a new counter-example.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Cex_t * Saig_ManCexRemap( Aig_Man_t * p, Aig_Man_t * pAbs, Abc_Cex_t * pCexAbs ) -{ - Abc_Cex_t * pCex; - Aig_Obj_t * pObj; - int i, f; - if ( !Saig_ManVerifyCex( pAbs, pCexAbs ) ) - printf( "Saig_ManCexRemap(): The initial counter-example is invalid.\n" ); -// else -// printf( "Saig_ManCexRemap(): The initial counter-example is correct.\n" ); - // start the counter-example - pCex = Abc_CexAlloc( Aig_ManRegNum(p), Saig_ManPiNum(p), pCexAbs->iFrame+1 ); - pCex->iFrame = pCexAbs->iFrame; - pCex->iPo = pCexAbs->iPo; - // copy the bit data - for ( f = 0; f <= pCexAbs->iFrame; f++ ) - { - Saig_ManForEachPi( pAbs, pObj, i ) - { - if ( i == Saig_ManPiNum(p) ) - break; - if ( Abc_InfoHasBit( pCexAbs->pData, pCexAbs->nRegs + pCexAbs->nPis * f + i ) ) - Abc_InfoSetBit( pCex->pData, pCex->nRegs + pCex->nPis * f + i ); - } - } - // verify the counter example - if ( !Saig_ManVerifyCex( p, pCex ) ) - { - printf( "Saig_ManCexRemap(): Counter-example is invalid.\n" ); - Abc_CexFree( pCex ); - pCex = NULL; - } - else - { - Abc_Print( 1, "Counter-example verification is successful.\n" ); - Abc_Print( 1, "Output %d of miter \"%s\" was asserted in frame %d. \n", pCex->iPo, p->pName, pCex->iFrame ); - } - return pCex; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/saig/saigAbsCba.c b/src/aig/saig/saigAbsCba.c deleted file mode 100644 index 8f2cafaa..00000000 --- a/src/aig/saig/saigAbsCba.c +++ /dev/null @@ -1,874 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigAbsCba.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [CEX-based abstraction.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigAbsCba.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.h" -#include "aig/gia/giaAig.h" -#include "aig/ioa/ioa.h" - -ABC_NAMESPACE_IMPL_START - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -// local manager -typedef struct Saig_ManCba_t_ Saig_ManCba_t; -struct Saig_ManCba_t_ -{ - // user data - Aig_Man_t * pAig; // user's AIG - Abc_Cex_t * pCex; // user's CEX - int nInputs; // the number of first inputs to skip - int fVerbose; // verbose flag - // unrolling - Aig_Man_t * pFrames; // unrolled timeframes - Vec_Int_t * vMapPiF2A; // mapping of frame PIs into real PIs - // additional information - Vec_Vec_t * vReg2Frame; // register to frame mapping - Vec_Vec_t * vReg2Value; // register to value mapping -}; - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - - -/**Function************************************************************* - - Synopsis [Selects the best flops from the given array.] - - Description [Selects the best 'nFfsToSelect' flops among the array - 'vAbsFfsToAdd' of flops that should be added to the abstraction. - To this end, this procedure simulates the original AIG (pAig) using - the given CEX (pAbsCex), which was detected for the abstraction.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManCbaFilterFlops( Aig_Man_t * pAig, Abc_Cex_t * pAbsCex, Vec_Int_t * vFlopClasses, Vec_Int_t * vAbsFfsToAdd, int nFfsToSelect ) -{ - Aig_Obj_t * pObj, * pObjRi, * pObjRo; - Vec_Int_t * vMapEntries, * vFlopCosts, * vFlopAddCosts, * vFfsToAddBest; - int i, k, f, Entry, iBit, * pPerm; - assert( Aig_ManRegNum(pAig) == Vec_IntSize(vFlopClasses) ); - assert( Vec_IntSize(vAbsFfsToAdd) > nFfsToSelect ); - // map previously abstracted flops into their original numbers - vMapEntries = Vec_IntAlloc( Vec_IntSize(vFlopClasses) ); - Vec_IntForEachEntry( vFlopClasses, Entry, i ) - if ( Entry == 0 ) - Vec_IntPush( vMapEntries, i ); - // simulate one frame at a time - assert( Saig_ManPiNum(pAig) + Vec_IntSize(vMapEntries) == pAbsCex->nPis ); - vFlopCosts = Vec_IntStart( Vec_IntSize(vMapEntries) ); - // initialize the flops - Aig_ManCleanMarkB(pAig); - Aig_ManConst1(pAig)->fMarkB = 1; - Saig_ManForEachLo( pAig, pObj, i ) - pObj->fMarkB = 0; - for ( f = 0; f < pAbsCex->iFrame; f++ ) - { - // override the flop values according to the cex - iBit = pAbsCex->nRegs + f * pAbsCex->nPis + Saig_ManPiNum(pAig); - Vec_IntForEachEntry( vMapEntries, Entry, k ) - Saig_ManLo(pAig, Entry)->fMarkB = Abc_InfoHasBit(pAbsCex->pData, iBit + k); - // simulate - Aig_ManForEachNode( pAig, pObj, k ) - pObj->fMarkB = (Aig_ObjFanin0(pObj)->fMarkB ^ Aig_ObjFaninC0(pObj)) & - (Aig_ObjFanin1(pObj)->fMarkB ^ Aig_ObjFaninC1(pObj)); - Aig_ManForEachCo( pAig, pObj, k ) - pObj->fMarkB = Aig_ObjFanin0(pObj)->fMarkB ^ Aig_ObjFaninC0(pObj); - // transfer - Saig_ManForEachLiLo( pAig, pObjRi, pObjRo, k ) - pObjRo->fMarkB = pObjRi->fMarkB; - // compare - iBit = pAbsCex->nRegs + (f + 1) * pAbsCex->nPis + Saig_ManPiNum(pAig); - Vec_IntForEachEntry( vMapEntries, Entry, k ) - if ( Saig_ManLi(pAig, Entry)->fMarkB != (unsigned)Abc_InfoHasBit(pAbsCex->pData, iBit + k) ) - Vec_IntAddToEntry( vFlopCosts, k, 1 ); - } -// Vec_IntForEachEntry( vFlopCosts, Entry, i ) -// printf( "%d ", Entry ); -// printf( "\n" ); - // remap the cost - vFlopAddCosts = Vec_IntAlloc( Vec_IntSize(vAbsFfsToAdd) ); - Vec_IntForEachEntry( vAbsFfsToAdd, Entry, i ) - Vec_IntPush( vFlopAddCosts, -Vec_IntEntry(vFlopCosts, Entry) ); - // sort the flops - pPerm = Abc_MergeSortCost( Vec_IntArray(vFlopAddCosts), Vec_IntSize(vFlopAddCosts) ); - // shrink the array - vFfsToAddBest = Vec_IntAlloc( nFfsToSelect ); - for ( i = 0; i < nFfsToSelect; i++ ) - { -// printf( "%d ", Vec_IntEntry(vFlopAddCosts, pPerm[i]) ); - Vec_IntPush( vFfsToAddBest, Vec_IntEntry(vAbsFfsToAdd, pPerm[i]) ); - } -// printf( "\n" ); - // cleanup - ABC_FREE( pPerm ); - Vec_IntFree( vMapEntries ); - Vec_IntFree( vFlopCosts ); - Vec_IntFree( vFlopAddCosts ); - Aig_ManCleanMarkB(pAig); - // return the computed flops - return vFfsToAddBest; -} - - -/**Function************************************************************* - - Synopsis [Duplicate with literals.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Aig_Man_t * Saig_ManDupWithCubes( Aig_Man_t * pAig, Vec_Vec_t * vReg2Value ) -{ - Vec_Int_t * vLevel; - Aig_Man_t * pAigNew; - Aig_Obj_t * pObj, * pMiter; - int i, k, Lit; - assert( pAig->nConstrs == 0 ); - // start the new manager - pAigNew = Aig_ManStart( Aig_ManNodeNum(pAig) + Vec_VecSizeSize(vReg2Value) ); - pAigNew->pName = Abc_UtilStrsav( pAig->pName ); - // map the constant node - Aig_ManConst1(pAig)->pData = Aig_ManConst1( pAigNew ); - // create variables for PIs - Aig_ManForEachCi( pAig, pObj, i ) - pObj->pData = Aig_ObjCreateCi( pAigNew ); - // add internal nodes of this frame - Aig_ManForEachNode( pAig, pObj, i ) - pObj->pData = Aig_And( pAigNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) ); - // create POs for cubes - Vec_VecForEachLevelInt( vReg2Value, vLevel, i ) - { - pMiter = Aig_ManConst1( pAigNew ); - Vec_IntForEachEntry( vLevel, Lit, k ) - { - pObj = Saig_ManLi( pAig, Abc_Lit2Var(Lit) ); - pMiter = Aig_And( pAigNew, pMiter, Aig_NotCond(Aig_ObjChild0Copy(pObj), Abc_LitIsCompl(Lit)) ); - } - Aig_ObjCreateCo( pAigNew, pMiter ); - } - // transfer to register outputs - Saig_ManForEachLi( pAig, pObj, i ) - Aig_ObjCreateCo( pAigNew, Aig_ObjChild0Copy(pObj) ); - // finalize - Aig_ManCleanup( pAigNew ); - Aig_ManSetRegNum( pAigNew, Aig_ManRegNum(pAig) ); - return pAigNew; -} - -/**Function************************************************************* - - Synopsis [Maps array of frame PI IDs into array of additional PI IDs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManCbaReason2Inputs( Saig_ManCba_t * p, Vec_Int_t * vReasons ) -{ - Vec_Int_t * vOriginal, * vVisited; - int i, Entry; - vOriginal = Vec_IntAlloc( Saig_ManPiNum(p->pAig) ); - vVisited = Vec_IntStart( Saig_ManPiNum(p->pAig) ); - Vec_IntForEachEntry( vReasons, Entry, i ) - { - int iInput = Vec_IntEntry( p->vMapPiF2A, 2*Entry ); - assert( iInput >= p->nInputs && iInput < Aig_ManCiNum(p->pAig) ); - if ( Vec_IntEntry(vVisited, iInput) == 0 ) - Vec_IntPush( vOriginal, iInput - p->nInputs ); - Vec_IntAddToEntry( vVisited, iInput, 1 ); - } - Vec_IntFree( vVisited ); - return vOriginal; -} - -/**Function************************************************************* - - Synopsis [Creates the counter-example.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Cex_t * Saig_ManCbaReason2Cex( Saig_ManCba_t * p, Vec_Int_t * vReasons ) -{ - Abc_Cex_t * pCare; - int i, Entry, iInput, iFrame; - pCare = Abc_CexDup( p->pCex, p->pCex->nRegs ); - memset( pCare->pData, 0, sizeof(unsigned) * Abc_BitWordNum(pCare->nBits) ); - Vec_IntForEachEntry( vReasons, Entry, i ) - { - assert( Entry >= 0 && Entry < Aig_ManCiNum(p->pFrames) ); - iInput = Vec_IntEntry( p->vMapPiF2A, 2*Entry ); - iFrame = Vec_IntEntry( p->vMapPiF2A, 2*Entry+1 ); - Abc_InfoSetBit( pCare->pData, pCare->nRegs + pCare->nPis * iFrame + iInput ); - } -/* - for ( iFrame = 0; iFrame <= pCare->iFrame; iFrame++ ) - { - int Count = 0; - for ( i = 0; i < pCare->nPis; i++ ) - Count += Abc_InfoHasBit(pCare->pData, pCare->nRegs + pCare->nPis * iFrame + i); - printf( "%d ", Count ); - } -printf( "\n" ); -*/ - return pCare; -} - -/**Function************************************************************* - - Synopsis [Returns reasons for the property to fail.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManCbaFindReason_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Int_t * vPrios, Vec_Int_t * vReasons ) -{ - if ( Aig_ObjIsTravIdCurrent(p, pObj) ) - return; - Aig_ObjSetTravIdCurrent(p, pObj); - if ( Aig_ObjIsConst1(pObj) ) - return; - if ( Aig_ObjIsCi(pObj) ) - { - Vec_IntPush( vReasons, Aig_ObjCioId(pObj) ); - return; - } - assert( Aig_ObjIsNode(pObj) ); - if ( pObj->fPhase ) - { - Saig_ManCbaFindReason_rec( p, Aig_ObjFanin0(pObj), vPrios, vReasons ); - Saig_ManCbaFindReason_rec( p, Aig_ObjFanin1(pObj), vPrios, vReasons ); - } - else - { - int fPhase0 = Aig_ObjFaninC0(pObj) ^ Aig_ObjFanin0(pObj)->fPhase; - int fPhase1 = Aig_ObjFaninC1(pObj) ^ Aig_ObjFanin1(pObj)->fPhase; - assert( !fPhase0 || !fPhase1 ); - if ( !fPhase0 && fPhase1 ) - Saig_ManCbaFindReason_rec( p, Aig_ObjFanin0(pObj), vPrios, vReasons ); - else if ( fPhase0 && !fPhase1 ) - Saig_ManCbaFindReason_rec( p, Aig_ObjFanin1(pObj), vPrios, vReasons ); - else - { - int iPrio0 = Vec_IntEntry( vPrios, Aig_ObjFaninId0(pObj) ); - int iPrio1 = Vec_IntEntry( vPrios, Aig_ObjFaninId1(pObj) ); - if ( iPrio0 <= iPrio1 ) - Saig_ManCbaFindReason_rec( p, Aig_ObjFanin0(pObj), vPrios, vReasons ); - else - Saig_ManCbaFindReason_rec( p, Aig_ObjFanin1(pObj), vPrios, vReasons ); - } - } -} - -/**Function************************************************************* - - Synopsis [Returns reasons for the property to fail.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManCbaFindReason( Saig_ManCba_t * p ) -{ - Aig_Obj_t * pObj; - Vec_Int_t * vPrios, * vReasons; - int i; - - // set PI values according to CEX - vPrios = Vec_IntStartFull( Aig_ManObjNumMax(p->pFrames) ); - Aig_ManConst1(p->pFrames)->fPhase = 1; - Aig_ManForEachCi( p->pFrames, pObj, i ) - { - int iInput = Vec_IntEntry( p->vMapPiF2A, 2*i ); - int iFrame = Vec_IntEntry( p->vMapPiF2A, 2*i+1 ); - pObj->fPhase = Abc_InfoHasBit( p->pCex->pData, p->pCex->nRegs + p->pCex->nPis * iFrame + iInput ); - Vec_IntWriteEntry( vPrios, Aig_ObjId(pObj), i ); - } - - // traverse and set the priority - Aig_ManForEachNode( p->pFrames, pObj, i ) - { - int fPhase0 = Aig_ObjFaninC0(pObj) ^ Aig_ObjFanin0(pObj)->fPhase; - int fPhase1 = Aig_ObjFaninC1(pObj) ^ Aig_ObjFanin1(pObj)->fPhase; - int iPrio0 = Vec_IntEntry( vPrios, Aig_ObjFaninId0(pObj) ); - int iPrio1 = Vec_IntEntry( vPrios, Aig_ObjFaninId1(pObj) ); - pObj->fPhase = fPhase0 && fPhase1; - if ( fPhase0 && fPhase1 ) // both are one - Vec_IntWriteEntry( vPrios, Aig_ObjId(pObj), Abc_MaxInt(iPrio0, iPrio1) ); - else if ( !fPhase0 && fPhase1 ) - Vec_IntWriteEntry( vPrios, Aig_ObjId(pObj), iPrio0 ); - else if ( fPhase0 && !fPhase1 ) - Vec_IntWriteEntry( vPrios, Aig_ObjId(pObj), iPrio1 ); - else // both are zero - Vec_IntWriteEntry( vPrios, Aig_ObjId(pObj), Abc_MinInt(iPrio0, iPrio1) ); - } - // check the property output - pObj = Aig_ManCo( p->pFrames, 0 ); - pObj->fPhase = Aig_ObjFaninC0(pObj) ^ Aig_ObjFanin0(pObj)->fPhase; - assert( !pObj->fPhase ); - - // select the reason - vReasons = Vec_IntAlloc( 100 ); - Aig_ManIncrementTravId( p->pFrames ); - Saig_ManCbaFindReason_rec( p->pFrames, Aig_ObjFanin0(pObj), vPrios, vReasons ); - Vec_IntFree( vPrios ); -// assert( !Aig_ObjIsTravIdCurrent(p->pFrames, Aig_ManConst1(p->pFrames)) ); - return vReasons; -} - - -/**Function************************************************************* - - Synopsis [Collect nodes in the unrolled timeframes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManCbaUnrollCollect_rec( Aig_Man_t * pAig, Aig_Obj_t * pObj, Vec_Int_t * vObjs, Vec_Int_t * vRoots ) -{ - if ( Aig_ObjIsTravIdCurrent(pAig, pObj) ) - return; - Aig_ObjSetTravIdCurrent(pAig, pObj); - if ( Aig_ObjIsCo(pObj) ) - Saig_ManCbaUnrollCollect_rec( pAig, Aig_ObjFanin0(pObj), vObjs, vRoots ); - else if ( Aig_ObjIsNode(pObj) ) - { - Saig_ManCbaUnrollCollect_rec( pAig, Aig_ObjFanin0(pObj), vObjs, vRoots ); - Saig_ManCbaUnrollCollect_rec( pAig, Aig_ObjFanin1(pObj), vObjs, vRoots ); - } - if ( vRoots && Saig_ObjIsLo( pAig, pObj ) ) - Vec_IntPush( vRoots, Aig_ObjId( Saig_ObjLoToLi(pAig, pObj) ) ); - Vec_IntPush( vObjs, Aig_ObjId(pObj) ); -} - -/**Function************************************************************* - - Synopsis [Derive unrolled timeframes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Aig_Man_t * Saig_ManCbaUnrollWithCex( Aig_Man_t * pAig, Abc_Cex_t * pCex, int nInputs, Vec_Int_t ** pvMapPiF2A, Vec_Vec_t ** pvReg2Frame ) -{ - Aig_Man_t * pFrames; // unrolled timeframes - Vec_Vec_t * vFrameCos; // the list of COs per frame - Vec_Vec_t * vFrameObjs; // the list of objects per frame - Vec_Int_t * vRoots, * vObjs; - Aig_Obj_t * pObj; - int i, f; - // sanity checks - assert( Saig_ManPiNum(pAig) == pCex->nPis ); -// assert( Saig_ManRegNum(pAig) == pCex->nRegs ); - assert( pCex->iPo >= 0 && pCex->iPo < Saig_ManPoNum(pAig) ); - - // map PIs of the unrolled frames into PIs of the original design - *pvMapPiF2A = Vec_IntAlloc( 1000 ); - - // collect COs and Objs visited in each frame - vFrameCos = Vec_VecStart( pCex->iFrame+1 ); - vFrameObjs = Vec_VecStart( pCex->iFrame+1 ); - // initialized the topmost frame - pObj = Aig_ManCo( pAig, pCex->iPo ); - Vec_VecPushInt( vFrameCos, pCex->iFrame, Aig_ObjId(pObj) ); - for ( f = pCex->iFrame; f >= 0; f-- ) - { - // collect nodes starting from the roots - Aig_ManIncrementTravId( pAig ); - vRoots = Vec_VecEntryInt( vFrameCos, f ); - Aig_ManForEachObjVec( vRoots, pAig, pObj, i ) - Saig_ManCbaUnrollCollect_rec( pAig, pObj, - Vec_VecEntryInt(vFrameObjs, f), - (Vec_Int_t *)(f ? Vec_VecEntry(vFrameCos, f-1) : NULL) ); - } - - // derive unrolled timeframes - pFrames = Aig_ManStart( 10000 ); - pFrames->pName = Abc_UtilStrsav( pAig->pName ); - pFrames->pSpec = Abc_UtilStrsav( pAig->pSpec ); - // initialize the flops - if ( Saig_ManRegNum(pAig) == pCex->nRegs ) - { - Saig_ManForEachLo( pAig, pObj, i ) - pObj->pData = Aig_NotCond( Aig_ManConst1(pFrames), !Abc_InfoHasBit(pCex->pData, i) ); - } - else // this is the case when synthesis was applied, assume all-0 init state - { - Saig_ManForEachLo( pAig, pObj, i ) - pObj->pData = Aig_NotCond( Aig_ManConst1(pFrames), 1 ); - } - // iterate through the frames - for ( f = 0; f <= pCex->iFrame; f++ ) - { - // construct - vObjs = Vec_VecEntryInt( vFrameObjs, f ); - Aig_ManForEachObjVec( vObjs, pAig, pObj, i ) - { - if ( Aig_ObjIsNode(pObj) ) - pObj->pData = Aig_And( pFrames, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) ); - else if ( Aig_ObjIsCo(pObj) ) - pObj->pData = Aig_ObjChild0Copy(pObj); - else if ( Aig_ObjIsConst1(pObj) ) - pObj->pData = Aig_ManConst1(pFrames); - else if ( Saig_ObjIsPi(pAig, pObj) ) - { - if ( Aig_ObjCioId(pObj) < nInputs ) - { - int iBit = pCex->nRegs + f * pCex->nPis + Aig_ObjCioId(pObj); - pObj->pData = Aig_NotCond( Aig_ManConst1(pFrames), !Abc_InfoHasBit(pCex->pData, iBit) ); - } - else - { - pObj->pData = Aig_ObjCreateCi( pFrames ); - Vec_IntPush( *pvMapPiF2A, Aig_ObjCioId(pObj) ); - Vec_IntPush( *pvMapPiF2A, f ); - } - } - } - if ( f == pCex->iFrame ) - break; - // transfer - vRoots = Vec_VecEntryInt( vFrameCos, f ); - Aig_ManForEachObjVec( vRoots, pAig, pObj, i ) - { - Saig_ObjLiToLo( pAig, pObj )->pData = pObj->pData; - if ( *pvReg2Frame ) - { - Vec_VecPushInt( *pvReg2Frame, f, Aig_ObjId(pObj) ); // record LO - Vec_VecPushInt( *pvReg2Frame, f, Aig_ObjToLit((Aig_Obj_t *)pObj->pData) ); // record its literal - } - } - } - // create output - pObj = Aig_ManCo( pAig, pCex->iPo ); - Aig_ObjCreateCo( pFrames, Aig_Not((Aig_Obj_t *)pObj->pData) ); - Aig_ManSetRegNum( pFrames, 0 ); - // cleanup - Vec_VecFree( vFrameCos ); - Vec_VecFree( vFrameObjs ); - // finallize - Aig_ManCleanup( pFrames ); - // return - return pFrames; -} - -/**Function************************************************************* - - Synopsis [Creates refinement manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Saig_ManCba_t * Saig_ManCbaStart( Aig_Man_t * pAig, Abc_Cex_t * pCex, int nInputs, int fVerbose ) -{ - Saig_ManCba_t * p; - p = ABC_CALLOC( Saig_ManCba_t, 1 ); - p->pAig = pAig; - p->pCex = pCex; - p->nInputs = nInputs; - p->fVerbose = fVerbose; - return p; -} - -/**Function************************************************************* - - Synopsis [Destroys refinement manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManCbaStop( Saig_ManCba_t * p ) -{ - Vec_VecFreeP( &p->vReg2Frame ); - Vec_VecFreeP( &p->vReg2Value ); - Aig_ManStopP( &p->pFrames ); - Vec_IntFreeP( &p->vMapPiF2A ); - ABC_FREE( p ); -} - -/**Function************************************************************* - - Synopsis [Destroys refinement manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManCbaShrink( Saig_ManCba_t * p ) -{ - Aig_Man_t * pManNew; - Aig_Obj_t * pObjLi, * pObjFrame; - Vec_Int_t * vLevel, * vLevel2; - int f, k, ObjId, Lit; - // assuming that important objects are labeled in Saig_ManCbaFindReason() - Vec_VecForEachLevelInt( p->vReg2Frame, vLevel, f ) - { - Vec_IntForEachEntryDouble( vLevel, ObjId, Lit, k ) - { - pObjFrame = Aig_ManObj( p->pFrames, Abc_Lit2Var(Lit) ); - if ( pObjFrame == NULL || (!Aig_ObjIsConst1(pObjFrame) && !Aig_ObjIsTravIdCurrent(p->pFrames, pObjFrame)) ) - continue; - pObjLi = Aig_ManObj( p->pAig, ObjId ); - assert( Saig_ObjIsLi(p->pAig, pObjLi) ); - Vec_VecPushInt( p->vReg2Value, f, Abc_Var2Lit( Aig_ObjCioId(pObjLi) - Saig_ManPoNum(p->pAig), Abc_LitIsCompl(Lit) ^ !pObjFrame->fPhase ) ); - } - } - // print statistics - Vec_VecForEachLevelInt( p->vReg2Frame, vLevel, k ) - { - vLevel2 = Vec_VecEntryInt( p->vReg2Value, k ); - printf( "Level = %4d StateBits = %4d (%6.2f %%) CareBits = %4d (%6.2f %%)\n", k, - Vec_IntSize(vLevel)/2, 100.0 * (Vec_IntSize(vLevel)/2) / Aig_ManRegNum(p->pAig), - Vec_IntSize(vLevel2), 100.0 * Vec_IntSize(vLevel2) / Aig_ManRegNum(p->pAig) ); - } - // try reducing the frames - pManNew = Saig_ManDupWithCubes( p->pAig, p->vReg2Value ); - Ioa_WriteAiger( pManNew, "aigcube.aig", 0, 0 ); - Aig_ManStop( pManNew ); -} - -static inline void Saig_ObjCexMinSet0( Aig_Obj_t * pObj ) { pObj->fMarkA = 1; pObj->fMarkB = 0; } -static inline void Saig_ObjCexMinSet1( Aig_Obj_t * pObj ) { pObj->fMarkA = 0; pObj->fMarkB = 1; } -static inline void Saig_ObjCexMinSetX( Aig_Obj_t * pObj ) { pObj->fMarkA = 1; pObj->fMarkB = 1; } - -static inline int Saig_ObjCexMinGet0( Aig_Obj_t * pObj ) { return pObj->fMarkA && !pObj->fMarkB; } -static inline int Saig_ObjCexMinGet1( Aig_Obj_t * pObj ) { return !pObj->fMarkA && pObj->fMarkB; } -static inline int Saig_ObjCexMinGetX( Aig_Obj_t * pObj ) { return pObj->fMarkA && pObj->fMarkB; } - -static inline int Saig_ObjCexMinGet0Fanin0( Aig_Obj_t * pObj ) { return (Saig_ObjCexMinGet1(Aig_ObjFanin0(pObj)) && Aig_ObjFaninC0(pObj)) || (Saig_ObjCexMinGet0(Aig_ObjFanin0(pObj)) && !Aig_ObjFaninC0(pObj)); } -static inline int Saig_ObjCexMinGet1Fanin0( Aig_Obj_t * pObj ) { return (Saig_ObjCexMinGet0(Aig_ObjFanin0(pObj)) && Aig_ObjFaninC0(pObj)) || (Saig_ObjCexMinGet1(Aig_ObjFanin0(pObj)) && !Aig_ObjFaninC0(pObj)); } - -static inline int Saig_ObjCexMinGet0Fanin1( Aig_Obj_t * pObj ) { return (Saig_ObjCexMinGet1(Aig_ObjFanin1(pObj)) && Aig_ObjFaninC1(pObj)) || (Saig_ObjCexMinGet0(Aig_ObjFanin1(pObj)) && !Aig_ObjFaninC1(pObj)); } -static inline int Saig_ObjCexMinGet1Fanin1( Aig_Obj_t * pObj ) { return (Saig_ObjCexMinGet0(Aig_ObjFanin1(pObj)) && Aig_ObjFaninC1(pObj)) || (Saig_ObjCexMinGet1(Aig_ObjFanin1(pObj)) && !Aig_ObjFaninC1(pObj)); } - -static inline void Saig_ObjCexMinSim( Aig_Obj_t * pObj ) -{ - if ( Aig_ObjIsAnd(pObj) ) - { - if ( Saig_ObjCexMinGet0Fanin0(pObj) || Saig_ObjCexMinGet0Fanin1(pObj) ) - Saig_ObjCexMinSet0( pObj ); - else if ( Saig_ObjCexMinGet1Fanin0(pObj) && Saig_ObjCexMinGet1Fanin1(pObj) ) - Saig_ObjCexMinSet1( pObj ); - else - Saig_ObjCexMinSetX( pObj ); - } - else if ( Aig_ObjIsCo(pObj) ) - { - if ( Saig_ObjCexMinGet0Fanin0(pObj) ) - Saig_ObjCexMinSet0( pObj ); - else if ( Saig_ObjCexMinGet1Fanin0(pObj) ) - Saig_ObjCexMinSet1( pObj ); - else - Saig_ObjCexMinSetX( pObj ); - } - else assert( 0 ); -} - -static inline void Saig_ObjCexMinPrint( Aig_Obj_t * pObj ) -{ - if ( Saig_ObjCexMinGet0(pObj) ) - printf( "0" ); - else if ( Saig_ObjCexMinGet1(pObj) ) - printf( "1" ); - else if ( Saig_ObjCexMinGetX(pObj) ) - printf( "X" ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManCexVerifyUsingTernary( Aig_Man_t * pAig, Abc_Cex_t * pCex, Abc_Cex_t * pCare ) -{ - Aig_Obj_t * pObj, * pObjRi, * pObjRo; - int i, f, iBit = 0; - assert( pCex->iFrame == pCare->iFrame ); - assert( pCex->nBits == pCare->nBits ); - assert( pCex->iPo < Saig_ManPoNum(pAig) ); - Saig_ObjCexMinSet1( Aig_ManConst1(pAig) ); - // set flops to the init state - Saig_ManForEachLo( pAig, pObj, i ) - { - assert( !Abc_InfoHasBit(pCex->pData, iBit) ); - assert( !Abc_InfoHasBit(pCare->pData, iBit) ); -// if ( Abc_InfoHasBit(pCare->pData, iBit++) ) - Saig_ObjCexMinSet0( pObj ); -// else -// Saig_ObjCexMinSetX( pObj ); - } - iBit = pCex->nRegs; - for ( f = 0; f <= pCex->iFrame; f++ ) - { - // init inputs - Saig_ManForEachPi( pAig, pObj, i ) - { - if ( Abc_InfoHasBit(pCare->pData, iBit++) ) - { - if ( Abc_InfoHasBit(pCex->pData, iBit-1) ) - Saig_ObjCexMinSet1( pObj ); - else - Saig_ObjCexMinSet0( pObj ); - } - else - Saig_ObjCexMinSetX( pObj ); - } - // simulate internal nodes - Aig_ManForEachNode( pAig, pObj, i ) - Saig_ObjCexMinSim( pObj ); - // simulate COs - Aig_ManForEachCo( pAig, pObj, i ) - Saig_ObjCexMinSim( pObj ); -/* - Aig_ManForEachObj( pAig, pObj, i ) - { - Aig_ObjPrint(pAig, pObj); - printf( " Value = " ); - Saig_ObjCexMinPrint( pObj ); - printf( "\n" ); - } -*/ - // transfer - Saig_ManForEachLiLo( pAig, pObjRi, pObjRo, i ) - pObjRo->fMarkA = pObjRi->fMarkA, - pObjRo->fMarkB = pObjRi->fMarkB; - } - assert( iBit == pCex->nBits ); - return Saig_ObjCexMinGet1( Aig_ManCo( pAig, pCex->iPo ) ); -} - -/**Function************************************************************* - - Synopsis [SAT-based refinement of the counter-example.] - - Description [The first parameter (nInputs) indicates how many first - primary inputs to skip without considering as care candidates.] - - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Cex_t * Saig_ManCbaFindCexCareBits( Aig_Man_t * pAig, Abc_Cex_t * pCex, int nInputs, int fVerbose ) -{ - Saig_ManCba_t * p; - Vec_Int_t * vReasons; - Abc_Cex_t * pCare; - clock_t clk = clock(); - - clk = clock(); - p = Saig_ManCbaStart( pAig, pCex, nInputs, fVerbose ); - -// p->vReg2Frame = Vec_VecStart( pCex->iFrame ); -// p->vReg2Value = Vec_VecStart( pCex->iFrame ); - p->pFrames = Saig_ManCbaUnrollWithCex( pAig, pCex, nInputs, &p->vMapPiF2A, &p->vReg2Frame ); - vReasons = Saig_ManCbaFindReason( p ); - if ( p->vReg2Frame ) - Saig_ManCbaShrink( p ); - - -//if ( fVerbose ) -//Aig_ManPrintStats( p->pFrames ); - - if ( fVerbose ) - { - Vec_Int_t * vRes = Saig_ManCbaReason2Inputs( p, vReasons ); - printf( "Frame PIs = %4d (essential = %4d) AIG PIs = %4d (essential = %4d) ", - Aig_ManCiNum(p->pFrames), Vec_IntSize(vReasons), - Saig_ManPiNum(p->pAig) - p->nInputs, Vec_IntSize(vRes) ); - Vec_IntFree( vRes ); -ABC_PRT( "Time", clock() - clk ); - } - - pCare = Saig_ManCbaReason2Cex( p, vReasons ); - Vec_IntFree( vReasons ); - Saig_ManCbaStop( p ); - -if ( fVerbose ) -{ -printf( "Real " ); -Abc_CexPrintStats( pCex ); -} -if ( fVerbose ) -{ -printf( "Care " ); -Abc_CexPrintStats( pCare ); -} -/* - // verify the reduced counter-example using ternary simulation - if ( !Saig_ManCexVerifyUsingTernary( pAig, pCex, pCare ) ) - printf( "Saig_ManCbaFindCexCareBits(): Minimized counter-example verification has failed!!!\n" ); - else if ( fVerbose ) - printf( "Saig_ManCbaFindCexCareBits(): Minimized counter-example verification is successful.\n" ); -*/ - Aig_ManCleanMarkAB( pAig ); - return pCare; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManCbaFilterInputs( Aig_Man_t * pAig, int iFirstFlopPi, Abc_Cex_t * pCex, int fVerbose ) -{ - Saig_ManCba_t * p; - Vec_Int_t * vRes, * vReasons; - clock_t clk; - if ( Saig_ManPiNum(pAig) != pCex->nPis ) - { - printf( "Saig_ManCbaFilterInputs(): The PI count of AIG (%d) does not match that of cex (%d).\n", - Aig_ManCiNum(pAig), pCex->nPis ); - return NULL; - } - -clk = clock(); - p = Saig_ManCbaStart( pAig, pCex, iFirstFlopPi, fVerbose ); - p->pFrames = Saig_ManCbaUnrollWithCex( pAig, pCex, iFirstFlopPi, &p->vMapPiF2A, &p->vReg2Frame ); - vReasons = Saig_ManCbaFindReason( p ); - vRes = Saig_ManCbaReason2Inputs( p, vReasons ); - if ( fVerbose ) - { - printf( "Frame PIs = %4d (essential = %4d) AIG PIs = %4d (essential = %4d) ", - Aig_ManCiNum(p->pFrames), Vec_IntSize(vReasons), - Saig_ManPiNum(p->pAig) - p->nInputs, Vec_IntSize(vRes) ); -ABC_PRT( "Time", clock() - clk ); - } - - Vec_IntFree( vReasons ); - Saig_ManCbaStop( p ); - return vRes; -} - - - - -/**Function************************************************************* - - Synopsis [Checks the abstracted model for a counter-example.] - - Description [Returns the array of abstracted flops that should be added - to the abstraction.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManCbaPerform( Aig_Man_t * pAbs, int nInputs, Saig_ParBmc_t * pPars ) -{ - Vec_Int_t * vAbsFfsToAdd; - int RetValue; - clock_t clk = clock(); -// assert( pAbs->nRegs > 0 ); - // perform BMC - RetValue = Saig_ManBmcScalable( pAbs, pPars ); - if ( RetValue == -1 ) // time out - nothing to add - { - printf( "Resource limit is reached during BMC.\n" ); - assert( pAbs->pSeqModel == NULL ); - return Vec_IntAlloc( 0 ); - } - if ( pAbs->pSeqModel == NULL ) - { - printf( "BMC did not detect a CEX with the given depth.\n" ); - return Vec_IntAlloc( 0 ); - } - if ( pPars->fVerbose ) - Abc_CexPrintStats( pAbs->pSeqModel ); - // CEX is detected - refine the flops - vAbsFfsToAdd = Saig_ManCbaFilterInputs( pAbs, nInputs, pAbs->pSeqModel, pPars->fVerbose ); - if ( Vec_IntSize(vAbsFfsToAdd) == 0 ) - { - Vec_IntFree( vAbsFfsToAdd ); - return NULL; - } - if ( pPars->fVerbose ) - { - printf( "Adding %d registers to the abstraction (total = %d). ", - Vec_IntSize(vAbsFfsToAdd), Aig_ManRegNum(pAbs)+Vec_IntSize(vAbsFfsToAdd) ); - Abc_PrintTime( 1, "Time", clock() - clk ); - } - return vAbsFfsToAdd; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/saig/saigAbsPba.c b/src/aig/saig/saigAbsPba.c deleted file mode 100644 index 34e1decf..00000000 --- a/src/aig/saig/saigAbsPba.c +++ /dev/null @@ -1,374 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigAbsPba.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [Proof-based abstraction.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigAbsPba.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.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 [Collect nodes in the unrolled timeframes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManUnrollForPba_rec( Aig_Man_t * pAig, Aig_Obj_t * pObj, Vec_Int_t * vObjs, Vec_Int_t * vRoots ) -{ - if ( Aig_ObjIsTravIdCurrent(pAig, pObj) ) - return; - Aig_ObjSetTravIdCurrent(pAig, pObj); - if ( Aig_ObjIsCo(pObj) ) - Saig_ManUnrollForPba_rec( pAig, Aig_ObjFanin0(pObj), vObjs, vRoots ); - else if ( Aig_ObjIsNode(pObj) ) - { - Saig_ManUnrollForPba_rec( pAig, Aig_ObjFanin0(pObj), vObjs, vRoots ); - Saig_ManUnrollForPba_rec( pAig, Aig_ObjFanin1(pObj), vObjs, vRoots ); - } - if ( vRoots && Saig_ObjIsLo( pAig, pObj ) ) - Vec_IntPush( vRoots, Aig_ObjId( Saig_ObjLoToLi(pAig, pObj) ) ); - Vec_IntPush( vObjs, Aig_ObjId(pObj) ); -} - -/**Function************************************************************* - - Synopsis [Derives unrolled timeframes for PBA.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Aig_Man_t * Saig_ManUnrollForPba( Aig_Man_t * pAig, int nStart, int nFrames, Vec_Int_t ** pvPiVarMap ) -{ - Aig_Man_t * pFrames; // unrolled timeframes - Vec_Vec_t * vFrameCos; // the list of COs per frame - Vec_Vec_t * vFrameObjs; // the list of objects per frame - Vec_Int_t * vRoots, * vObjs; - Aig_Obj_t * pObj, * pObjNew; - int i, f; - assert( nStart <= nFrames ); - // collect COs and Objs visited in each frame - vFrameCos = Vec_VecStart( nFrames ); - vFrameObjs = Vec_VecStart( nFrames ); - for ( f = nFrames-1; f >= 0; f-- ) - { - // add POs of this frame - vRoots = Vec_VecEntryInt( vFrameCos, f ); - Saig_ManForEachPo( pAig, pObj, i ) - Vec_IntPush( vRoots, Aig_ObjId(pObj) ); - // collect nodes starting from the roots - Aig_ManIncrementTravId( pAig ); - Aig_ManForEachObjVec( vRoots, pAig, pObj, i ) - Saig_ManUnrollForPba_rec( pAig, pObj, - Vec_VecEntryInt( vFrameObjs, f ), - (Vec_Int_t *)(f ? Vec_VecEntry(vFrameCos, f-1) : NULL) ); - } - // derive unrolled timeframes - pFrames = Aig_ManStart( 10000 ); - pFrames->pName = Abc_UtilStrsav( pAig->pName ); - pFrames->pSpec = Abc_UtilStrsav( pAig->pSpec ); - // create activation variables - Saig_ManForEachLo( pAig, pObj, i ) - Aig_ObjCreateCi( pFrames ); - // initialize the flops - Saig_ManForEachLo( pAig, pObj, i ) - pObj->pData = Aig_Mux( pFrames, Aig_ManCi(pFrames,i), Aig_ObjCreateCi(pFrames), Aig_ManConst0(pFrames) ); - // iterate through the frames - *pvPiVarMap = Vec_IntStartFull( nFrames * Saig_ManPiNum(pAig) ); - pObjNew = Aig_ManConst0(pFrames); - for ( f = 0; f < nFrames; f++ ) - { - // construct - vObjs = Vec_VecEntryInt( vFrameObjs, f ); - Aig_ManForEachObjVec( vObjs, pAig, pObj, i ) - { - if ( Aig_ObjIsNode(pObj) ) - pObj->pData = Aig_And( pFrames, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) ); - else if ( Aig_ObjIsCo(pObj) ) - pObj->pData = Aig_ObjChild0Copy(pObj); - else if ( Saig_ObjIsPi(pAig, pObj) ) - { - Vec_IntWriteEntry( *pvPiVarMap, f * Saig_ManPiNum(pAig) + Aig_ObjCioId(pObj), Aig_ManCiNum(pFrames) ); - pObj->pData = Aig_ObjCreateCi( pFrames ); - } - else if ( Aig_ObjIsConst1(pObj) ) - pObj->pData = Aig_ManConst1(pFrames); - else if ( !Saig_ObjIsLo(pAig, pObj) ) - assert( 0 ); - } - // create output - if ( f >= nStart ) - { - Saig_ManForEachPo( pAig, pObj, i ) - pObjNew = Aig_Or( pFrames, pObjNew, (Aig_Obj_t *)pObj->pData ); - } - // transfer - if ( f == nFrames - 1 ) - break; - vRoots = Vec_VecEntryInt( vFrameCos, f ); - Aig_ManForEachObjVec( vRoots, pAig, pObj, i ) - { - if ( Saig_ObjIsLi(pAig, pObj) ) - { - int iFlopNum = Aig_ObjCioId(pObj) - Saig_ManPoNum(pAig); - assert( iFlopNum >= 0 && iFlopNum < Aig_ManRegNum(pAig) ); - Saig_ObjLiToLo(pAig, pObj)->pData = Aig_Mux( pFrames, Aig_ManCi(pFrames,iFlopNum), Aig_ObjCreateCi(pFrames), (Aig_Obj_t *)pObj->pData ); - } - } - } - // cleanup - Vec_VecFree( vFrameCos ); - Vec_VecFree( vFrameObjs ); - // create output - Aig_ObjCreateCo( pFrames, pObjNew ); - Aig_ManSetRegNum( pFrames, 0 ); - // finallize - Aig_ManCleanup( pFrames ); - return pFrames; -} - -/**Function************************************************************* - - Synopsis [Derives the counter-example from the SAT solver.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Cex_t * Saig_ManPbaDeriveCex( Aig_Man_t * pAig, sat_solver * pSat, Cnf_Dat_t * pCnf, int nFrames, Vec_Int_t * vPiVarMap ) -{ - Abc_Cex_t * pCex; - Aig_Obj_t * pObj, * pObjRi, * pObjRo; - int i, f, Entry, iBit = 0; - pCex = Abc_CexAlloc( Aig_ManRegNum(pAig), Saig_ManPiNum(pAig), nFrames ); - pCex->iPo = -1; - pCex->iFrame = -1; - Vec_IntForEachEntry( vPiVarMap, Entry, i ) - { - if ( Entry >= 0 ) - { - int iSatVar = pCnf->pVarNums[ Aig_ObjId(Aig_ManCi(pCnf->pMan, Entry)) ]; - if ( sat_solver_var_value( pSat, iSatVar ) ) - Abc_InfoSetBit( pCex->pData, Aig_ManRegNum(pAig) + i ); - } - } - // check what frame has failed - Aig_ManCleanMarkB(pAig); - Aig_ManConst1(pAig)->fMarkB = 1; - Saig_ManForEachLo( pAig, pObj, i ) - pObj->fMarkB = Abc_InfoHasBit(pCex->pData, iBit++); - for ( f = 0; f < nFrames; f++ ) - { - // compute new state - Saig_ManForEachPi( pAig, pObj, i ) - pObj->fMarkB = Abc_InfoHasBit(pCex->pData, iBit++); - Aig_ManForEachNode( pAig, pObj, i ) - pObj->fMarkB = (Aig_ObjFanin0(pObj)->fMarkB ^ Aig_ObjFaninC0(pObj)) & - (Aig_ObjFanin1(pObj)->fMarkB ^ Aig_ObjFaninC1(pObj)); - Aig_ManForEachCo( pAig, pObj, i ) - pObj->fMarkB = Aig_ObjFanin0(pObj)->fMarkB ^ Aig_ObjFaninC0(pObj); - Saig_ManForEachLiLo( pAig, pObjRi, pObjRo, i ) - pObjRo->fMarkB = pObjRi->fMarkB; - // check the outputs - Saig_ManForEachPo( pAig, pObj, i ) - { - if ( pObj->fMarkB ) - { - pCex->iPo = i; - pCex->iFrame = f; - pCex->nBits = pCex->nRegs + pCex->nPis * (f+1); - break; - } - } - if ( i < Saig_ManPoNum(pAig) ) - break; - } - Aig_ManCleanMarkB(pAig); - if ( f == nFrames ) - { - Abc_Print( -1, "Saig_ManPbaDeriveCex(): Internal error! Cannot find a failed primary outputs.\n" ); - Abc_CexFree( pCex ); - pCex = NULL; - } - if ( !Saig_ManVerifyCex( pAig, pCex ) ) - { - Abc_Print( -1, "Saig_ManPbaDeriveCex(): Internal error! Counter-example is invalid.\n" ); - Abc_CexFree( pCex ); - pCex = NULL; - } - return pCex; -} - -/**Function************************************************************* - - Synopsis [Derive unrolled timeframes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManPbaDerive( Aig_Man_t * pAig, int nInputs, int nStart, int nFrames, int nConfLimit, int TimeLimit, int fVerbose, int * piFrame ) -{ - Vec_Int_t * vFlops = NULL, * vMapVar2FF, * vAssumps, * vPiVarMap; - Aig_Man_t * pFrames; - sat_solver * pSat; - Cnf_Dat_t * pCnf; - Aig_Obj_t * pObj; - int nCoreLits, * pCoreLits; - int i, iVar, RetValue; - clock_t clk; -if ( fVerbose ) -{ -if ( TimeLimit ) - printf( "Abstracting from frame %d to frame %d with timeout %d sec.\n", nStart, nFrames, TimeLimit ); -else - printf( "Abstracting from frame %d to frame %d with no timeout.\n", nStart, nFrames ); -} - // create SAT solver -clk = clock(); - pFrames = Saig_ManUnrollForPba( pAig, nStart, nFrames, &vPiVarMap ); -if ( fVerbose ) -Aig_ManPrintStats( pFrames ); -// pCnf = Cnf_DeriveSimple( pFrames, 0 ); -// pCnf = Cnf_Derive( pFrames, 0 ); - pCnf = Cnf_DeriveFast( pFrames, 0 ); - pSat = (sat_solver *)Cnf_DataWriteIntoSolver( pCnf, 1, 0 ); - if ( pSat == NULL ) - { - Aig_ManStop( pFrames ); - Cnf_DataFree( pCnf ); - return NULL; - } -if ( fVerbose ) -Abc_PrintTime( 1, "Preparing", clock() - clk ); - - // map activation variables into flop numbers - vAssumps = Vec_IntAlloc( Aig_ManRegNum(pAig) ); - vMapVar2FF = Vec_IntStartFull( pCnf->nVars ); - Aig_ManForEachCi( pFrames, pObj, i ) - { - if ( i >= Aig_ManRegNum(pAig) ) - break; - iVar = pCnf->pVarNums[Aig_ObjId(pObj)]; - Vec_IntPush( vAssumps, toLitCond(iVar, 1) ); - Vec_IntWriteEntry( vMapVar2FF, iVar, i ); - } - - // set runtime limit - if ( TimeLimit ) - sat_solver_set_runtime_limit( pSat, TimeLimit ? TimeLimit * CLOCKS_PER_SEC + clock(): 0 ); - - // run SAT solver -clk = clock(); - RetValue = sat_solver_solve( pSat, Vec_IntArray(vAssumps), Vec_IntArray(vAssumps) + Vec_IntSize(vAssumps), - (ABC_INT64_T)nConfLimit, (ABC_INT64_T)0, (ABC_INT64_T)0, (ABC_INT64_T)0 ); -if ( fVerbose ) -Abc_PrintTime( 1, "Solving", clock() - clk ); - if ( RetValue != l_False ) - { - if ( RetValue == l_True ) - { - Vec_Int_t * vAbsFfsToAdd; - ABC_FREE( pAig->pSeqModel ); - pAig->pSeqModel = Saig_ManPbaDeriveCex( pAig, pSat, pCnf, nFrames, vPiVarMap ); - printf( "The problem is SAT in frame %d. Performing CEX-based refinement.\n", pAig->pSeqModel->iFrame ); - *piFrame = pAig->pSeqModel->iFrame; - // CEX is detected - refine the flops - vAbsFfsToAdd = Saig_ManCbaFilterInputs( pAig, nInputs, pAig->pSeqModel, fVerbose ); - if ( Vec_IntSize(vAbsFfsToAdd) == 0 ) - { - Vec_IntFree( vAbsFfsToAdd ); - goto finish; - } - if ( fVerbose ) - { - printf( "Adding %d registers to the abstraction (total = %d). ", Vec_IntSize(vAbsFfsToAdd), Aig_ManRegNum(pAig)+Vec_IntSize(vAbsFfsToAdd) ); - Abc_PrintTime( 1, "Time", clock() - clk ); - } - vFlops = vAbsFfsToAdd; - } - else - { - printf( "Saig_ManPerformPba(): SAT solver timed out. Current abstraction is not changed.\n" ); - } - goto finish; - } - assert( RetValue == l_False ); // UNSAT - *piFrame = nFrames; - - // get relevant SAT literals - nCoreLits = sat_solver_final( pSat, &pCoreLits ); - assert( nCoreLits > 0 ); - if ( fVerbose ) - printf( "AnalizeFinal after %d frames selected %d assumptions (out of %d). Conflicts = %d.\n", - nFrames, nCoreLits, Vec_IntSize(vAssumps), (int)pSat->stats.conflicts ); - - // collect flops - vFlops = Vec_IntAlloc( nCoreLits ); - for ( i = 0; i < nCoreLits; i++ ) - { - iVar = Vec_IntEntry( vMapVar2FF, lit_var(pCoreLits[i]) ); - assert( iVar >= 0 && iVar < Aig_ManRegNum(pAig) ); - Vec_IntPush( vFlops, iVar ); - } - Vec_IntSort( vFlops, 0 ); - - // cleanup -finish: - Vec_IntFree( vPiVarMap ); - Vec_IntFree( vAssumps ); - Vec_IntFree( vMapVar2FF ); - sat_solver_delete( pSat ); - Cnf_DataFree( pCnf ); - Aig_ManStop( pFrames ); - return vFlops; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/saig/saigAbsStart.c b/src/aig/saig/saigAbsStart.c deleted file mode 100644 index 90efef26..00000000 --- a/src/aig/saig/saigAbsStart.c +++ /dev/null @@ -1,310 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigAbsStart.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [Counter-example-based abstraction.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigAbsStart.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.h" -#include "proof/ssw/ssw.h" -#include "proof/fra/fra.h" -#include "proof/bbr/bbr.h" -#include "proof/pdr/pdr.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Find the first PI corresponding to the flop.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManCexFirstFlopPi( Aig_Man_t * p, Aig_Man_t * pAbs ) -{ - Aig_Obj_t * pObj; - int i; - assert( pAbs->vCiNumsOrig != NULL ); - Aig_ManForEachCi( p, pObj, i ) - { - if ( Vec_IntEntry(pAbs->vCiNumsOrig, i) >= Saig_ManPiNum(p) ) - return i; - } - return -1; -} - -/**Function************************************************************* - - Synopsis [Refines abstraction using one step.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Aig_Man_t * Saig_ManCexRefine( Aig_Man_t * p, Aig_Man_t * pAbs, Vec_Int_t * vFlops, int nFrames, int nConfMaxOne, int fUseBdds, int fUseDprove, int fVerbose, int * pnUseStart, int * piRetValue, int * pnFrames ) -{ - extern int Saig_BmcPerform( Aig_Man_t * pAig, int nStart, int nFramesMax, int nNodesMax, int nTimeOut, int nConfMaxOne, int nConfMaxAll, int fVerbose, int fVerbOverwrite, int * piFrames, int fSilent ); - Vec_Int_t * vFlopsNew; - int i, Entry, RetValue; - *piRetValue = -1; - if ( fUseDprove && Aig_ManRegNum(pAbs) > 0 ) - { -/* - Fra_Sec_t SecPar, * pSecPar = &SecPar; - Fra_SecSetDefaultParams( pSecPar ); - pSecPar->fVerbose = fVerbose; - RetValue = Fra_FraigSec( pAbs, pSecPar, NULL ); -*/ - Abc_Cex_t * pCex = NULL; - Aig_Man_t * pAbsOrpos = Saig_ManDupOrpos( pAbs ); - Pdr_Par_t Pars, * pPars = &Pars; - Pdr_ManSetDefaultParams( pPars ); - pPars->nTimeOut = 10; - pPars->fVerbose = fVerbose; - if ( pPars->fVerbose ) - printf( "Running property directed reachability...\n" ); - RetValue = Pdr_ManSolve( pAbsOrpos, pPars, &pCex ); - if ( pCex ) - pCex->iPo = Saig_ManFindFailedPoCex( pAbs, pCex ); - Aig_ManStop( pAbsOrpos ); - pAbs->pSeqModel = pCex; - if ( RetValue ) - *piRetValue = 1; - - } - else if ( fUseBdds && (Aig_ManRegNum(pAbs) > 0 && Aig_ManRegNum(pAbs) <= 80) ) - { - Saig_ParBbr_t Pars, * pPars = &Pars; - Bbr_ManSetDefaultParams( pPars ); - pPars->TimeLimit = 0; - pPars->nBddMax = 1000000; - pPars->nIterMax = nFrames; - pPars->fPartition = 1; - pPars->fReorder = 1; - pPars->fReorderImage = 1; - pPars->fVerbose = fVerbose; - pPars->fSilent = 0; - RetValue = Aig_ManVerifyUsingBdds( pAbs, pPars ); - if ( RetValue ) - *piRetValue = 1; - } - else - { - Saig_BmcPerform( pAbs, pnUseStart? *pnUseStart: 0, nFrames, 2000, 0, nConfMaxOne, 0, fVerbose, 0, pnFrames, 0 ); - } - if ( pAbs->pSeqModel == NULL ) - return NULL; - if ( pnUseStart ) - *pnUseStart = pAbs->pSeqModel->iFrame; -// vFlopsNew = Saig_ManExtendCounterExampleTest( pAbs, Saig_ManCexFirstFlopPi(p, pAbs), pAbs->pSeqModel, 1, fVerbose ); - vFlopsNew = Saig_ManExtendCounterExampleTest3( pAbs, Saig_ManCexFirstFlopPi(p, pAbs), pAbs->pSeqModel, fVerbose ); - if ( vFlopsNew == NULL ) - return NULL; - if ( Vec_IntSize(vFlopsNew) == 0 ) - { - printf( "Discovered a true counter-example!\n" ); - p->pSeqModel = Saig_ManCexRemap( p, pAbs, pAbs->pSeqModel ); - Vec_IntFree( vFlopsNew ); - *piRetValue = 0; - return NULL; - } - // vFlopsNew contains PI numbers that should be kept in pAbs - if ( fVerbose ) - printf( "Adding %d registers to the abstraction (total = %d).\n\n", Vec_IntSize(vFlopsNew), Aig_ManRegNum(pAbs)+Vec_IntSize(vFlopsNew) ); - // add to the abstraction - Vec_IntForEachEntry( vFlopsNew, Entry, i ) - { - Entry = Vec_IntEntry(pAbs->vCiNumsOrig, Entry); - assert( Entry >= Saig_ManPiNum(p) ); - assert( Entry < Aig_ManCiNum(p) ); - Vec_IntPush( vFlops, Entry-Saig_ManPiNum(p) ); - } - Vec_IntFree( vFlopsNew ); - - Vec_IntSort( vFlops, 0 ); - Vec_IntForEachEntryStart( vFlops, Entry, i, 1 ) - assert( Vec_IntEntry(vFlops, i-1) != Entry ); - - return Saig_ManDupAbstraction( p, vFlops ); -} - -/**Function************************************************************* - - Synopsis [Refines abstraction using one step.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManCexRefineStep( Aig_Man_t * p, Vec_Int_t * vFlops, Vec_Int_t * vFlopClasses, Abc_Cex_t * pCex, int nFfToAddMax, int fTryFour, int fSensePath, int fVerbose ) -{ - Aig_Man_t * pAbs; - Vec_Int_t * vFlopsNew; - int i, Entry; - clock_t clk = clock(); - pAbs = Saig_ManDupAbstraction( p, vFlops ); - if ( fSensePath ) - vFlopsNew = Saig_ManExtendCounterExampleTest2( pAbs, Saig_ManCexFirstFlopPi(p, pAbs), pCex, fVerbose ); - else -// vFlopsNew = Saig_ManExtendCounterExampleTest( pAbs, Saig_ManCexFirstFlopPi(p, pAbs), pCex, fTryFour, fVerbose ); - vFlopsNew = Saig_ManExtendCounterExampleTest3( pAbs, Saig_ManCexFirstFlopPi(p, pAbs), pCex, fVerbose ); - if ( vFlopsNew == NULL ) - { - Aig_ManStop( pAbs ); - return 0; - } - if ( Vec_IntSize(vFlopsNew) == 0 ) - { - printf( "Refinement did not happen. Discovered a true counter-example.\n" ); - printf( "Remapping counter-example from %d to %d primary inputs.\n", Aig_ManCiNum(pAbs), Aig_ManCiNum(p) ); - p->pSeqModel = Saig_ManCexRemap( p, pAbs, pCex ); - Vec_IntFree( vFlopsNew ); - Aig_ManStop( pAbs ); - return 0; - } - if ( fVerbose ) - { - printf( "Adding %d registers to the abstraction (total = %d). ", Vec_IntSize(vFlopsNew), Aig_ManRegNum(p)+Vec_IntSize(vFlopsNew) ); - Abc_PrintTime( 1, "Time", clock() - clk ); - } - // vFlopsNew contains PI numbers that should be kept in pAbs - // select the most useful flops among those to be added - if ( nFfToAddMax > 0 && Vec_IntSize(vFlopsNew) > nFfToAddMax ) - { - Vec_Int_t * vFlopsNewBest; - // shift the indices - Vec_IntForEachEntry( vFlopsNew, Entry, i ) - Vec_IntAddToEntry( vFlopsNew, i, -Saig_ManPiNum(p) ); - // create new flops - vFlopsNewBest = Saig_ManCbaFilterFlops( p, pCex, vFlopClasses, vFlopsNew, nFfToAddMax ); - assert( Vec_IntSize(vFlopsNewBest) == nFfToAddMax ); - printf( "Filtering flops based on cost (%d -> %d).\n", Vec_IntSize(vFlopsNew), Vec_IntSize(vFlopsNewBest) ); - // update - Vec_IntFree( vFlopsNew ); - vFlopsNew = vFlopsNewBest; - // shift the indices - Vec_IntForEachEntry( vFlopsNew, Entry, i ) - Vec_IntAddToEntry( vFlopsNew, i, Saig_ManPiNum(p) ); - } - // add to the abstraction - Vec_IntForEachEntry( vFlopsNew, Entry, i ) - { - Entry = Vec_IntEntry(pAbs->vCiNumsOrig, Entry); - assert( Entry >= Saig_ManPiNum(p) ); - assert( Entry < Aig_ManCiNum(p) ); - Vec_IntPush( vFlops, Entry-Saig_ManPiNum(p) ); - } - Vec_IntFree( vFlopsNew ); - Aig_ManStop( pAbs ); - return 1; -} - -/**Function************************************************************* - - Synopsis [Computes the flops to remain after abstraction.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManCexAbstractionFlops( Aig_Man_t * p, Gia_ParAbs_t * pPars ) -{ - int nUseStart = 0; - Aig_Man_t * pAbs, * pTemp; - Vec_Int_t * vFlops; - int Iter;//, clk = clock(), clk2 = clock();//, iFlop; - assert( Aig_ManRegNum(p) > 0 ); - if ( pPars->fVerbose ) - printf( "Performing counter-example-based refinement.\n" ); - Aig_ManSetCioIds( p ); - vFlops = Vec_IntStartNatural( 1 ); -/* - iFlop = Saig_ManFindFirstFlop( p ); - assert( iFlop >= 0 ); - vFlops = Vec_IntAlloc( 1 ); - Vec_IntPush( vFlops, iFlop ); -*/ - // create the resulting AIG - pAbs = Saig_ManDupAbstraction( p, vFlops ); - if ( !pPars->fVerbose ) - { - printf( "Init : " ); - Aig_ManPrintStats( pAbs ); - } - printf( "Refining abstraction...\n" ); - for ( Iter = 0; ; Iter++ ) - { - pTemp = Saig_ManCexRefine( p, pAbs, vFlops, pPars->nFramesBmc, pPars->nConfMaxBmc, pPars->fUseBdds, pPars->fUseDprove, pPars->fVerbose, pPars->fUseStart?&nUseStart:NULL, &pPars->Status, &pPars->nFramesDone ); - if ( pTemp == NULL ) - { - ABC_FREE( p->pSeqModel ); - p->pSeqModel = pAbs->pSeqModel; - pAbs->pSeqModel = NULL; - Aig_ManStop( pAbs ); - break; - } - Aig_ManStop( pAbs ); - pAbs = pTemp; - printf( "ITER %4d : ", Iter ); - if ( !pPars->fVerbose ) - Aig_ManPrintStats( pAbs ); - // output the intermediate result of abstraction - Ioa_WriteAiger( pAbs, "gabs.aig", 0, 0 ); -// printf( "Intermediate abstracted model was written into file \"%s\".\n", "gabs.aig" ); - // check if the ratio is reached - if ( 100.0*(Aig_ManRegNum(p)-Aig_ManRegNum(pAbs))/Aig_ManRegNum(p) < 1.0*pPars->nRatio ) - { - printf( "Refinements is stopped because flop reduction is less than %d%%\n", pPars->nRatio ); - Aig_ManStop( pAbs ); - pAbs = NULL; - Vec_IntFree( vFlops ); - vFlops = NULL; - break; - } - } - return vFlops; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/saig/saigAbsVfa.c b/src/aig/saig/saigAbsVfa.c deleted file mode 100644 index 2c3ebbff..00000000 --- a/src/aig/saig/saigAbsVfa.c +++ /dev/null @@ -1,329 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigAbsVfa.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [Intergrated abstraction procedure.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigAbsVfa.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.h" -#include "sat/cnf/cnf.h" -#include "sat/bsat/satSolver.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -typedef struct Abs_VfaMan_t_ Abs_VfaMan_t; -struct Abs_VfaMan_t_ -{ - Aig_Man_t * pAig; - int nConfLimit; - int fVerbose; - // unrolling info - int iFrame; - int nFrames; - Vec_Int_t * vObj2Vec; // maps obj ID into its vec ID - Vec_Int_t * vVec2Var; // maps vec ID into its sat Var (nFrames per vec ID) - Vec_Int_t * vVar2Inf; // maps sat Var into its frame and obj ID - Vec_Int_t * vFra2Var; // maps frame number into the first variable - // SAT solver - sat_solver * pSat; - Cnf_Dat_t * pCnf; - Vec_Int_t * vAssumps; - Vec_Int_t * vCore; -}; - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Adds CNF clauses for the MUX.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abs_VfaManSatMux( sat_solver * pSat, int VarF, int VarI, int VarT, int VarE ) -{ - int RetValue, pLits[3]; - - // f = ITE(i, t, e) - - // i' + t' + f - // i' + t + f' - // i + e' + f - // i + e + f' - - // create four clauses - pLits[0] = toLitCond(VarI, 1); - pLits[1] = toLitCond(VarT, 1); - pLits[2] = toLitCond(VarF, 0); - RetValue = sat_solver_addclause( pSat, pLits, pLits + 3 ); - assert( RetValue ); - - pLits[0] = toLitCond(VarI, 1); - pLits[1] = toLitCond(VarT, 0); - pLits[2] = toLitCond(VarF, 1); - RetValue = sat_solver_addclause( pSat, pLits, pLits + 3 ); - assert( RetValue ); - - pLits[0] = toLitCond(VarI, 0); - pLits[1] = toLitCond(VarE, 1); - pLits[2] = toLitCond(VarF, 0); - RetValue = sat_solver_addclause( pSat, pLits, pLits + 3 ); - assert( RetValue ); - - pLits[0] = toLitCond(VarI, 0); - pLits[1] = toLitCond(VarE, 0); - pLits[2] = toLitCond(VarF, 1); - RetValue = sat_solver_addclause( pSat, pLits, pLits + 3 ); - assert( RetValue ); - - // two additional clauses - // t' & e' -> f' - // t & e -> f - - // t + e + f' - // t' + e' + f - assert( VarT != VarE ); - - pLits[0] = toLitCond(VarT, 0); - pLits[1] = toLitCond(VarE, 0); - pLits[2] = toLitCond(VarF, 1); - RetValue = sat_solver_addclause( pSat, pLits, pLits + 3 ); - assert( RetValue ); - - pLits[0] = toLitCond(VarT, 1); - pLits[1] = toLitCond(VarE, 1); - pLits[2] = toLitCond(VarF, 0); - RetValue = sat_solver_addclause( pSat, pLits, pLits + 3 ); - assert( RetValue ); -} - - - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abs_VfaManAddVar( Abs_VfaMan_t * p, Aig_Obj_t * pObj, int f, int * pfNew ) -{ - int i, SatId, VecId = Vec_IntEntry( p->vObj2Vec, Aig_ObjId(pObj) ); - *pfNew = 0; - if ( VecId == -1 ) - return -1; - if ( VecId == 0 ) - { - VecId = Vec_IntSize( p->vVec2Var ) / p->nFrames; - for ( i = 0; i < p->nFrames; i++ ) - Vec_IntPush( p->vVec2Var, 0 ); - Vec_IntWriteEntry( p->vObj2Vec, Aig_ObjId(pObj), VecId ); - } - SatId = Vec_IntEntry( p->vVec2Var, p->nFrames * VecId + f ); - if ( SatId ) - return SatId; - SatId = Vec_IntSize( p->vVar2Inf ) / 2; - // save SatId - Vec_IntWriteEntry( p->vVec2Var, p->nFrames * VecId + f, SatId ); - Vec_IntPush( p->vVar2Inf, Aig_ObjId(pObj) ); - Vec_IntPush( p->vVar2Inf, f ); - if ( Saig_ObjIsLo( p->pAig, pObj ) ) // reserve IDs for aux vars - { - Vec_IntPush( p->vVar2Inf, -1 ); - Vec_IntPush( p->vVar2Inf, f ); - Vec_IntPush( p->vVar2Inf, -2 ); - Vec_IntPush( p->vVar2Inf, f ); - } - *pfNew = 1; - return SatId; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abs_VfaManCreateFrame_rec( Abs_VfaMan_t * p, Aig_Obj_t * pObj, int f ) -{ - int SatVar, fNew; - if ( Aig_ObjIsConst1(pObj) ) - return -1; - SatVar = Abs_VfaManAddVar( p, pObj, f, &fNew ); - if ( (SatVar > 0 && !fNew) || Saig_ObjIsPi(p->pAig, pObj) || (Aig_ObjIsCi(pObj) && f==0) ) - return SatVar; - if ( Aig_ObjIsCo(pObj) ) - return Abs_VfaManCreateFrame_rec( p, Aig_ObjFanin0(pObj), f ); - if ( Aig_ObjIsCi(pObj) ) - return Abs_VfaManCreateFrame_rec( p, Saig_ObjLoToLi(p->pAig, pObj), f-1 ); - assert( Aig_ObjIsAnd(pObj) ); - Abs_VfaManCreateFrame_rec( p, Aig_ObjFanin0(pObj), f ); - Abs_VfaManCreateFrame_rec( p, Aig_ObjFanin1(pObj), f ); - return SatVar; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abs_VfaManCreateFrame( Abs_VfaMan_t * p, int f ) -{ - Aig_Obj_t * pObj; - int i; - clock_t clk = clock(); - - Saig_ManForEachPo( p->pAig, pObj, i ) - Abs_VfaManCreateFrame_rec( p, pObj, f ); - - Vec_IntPush( p->vFra2Var, Vec_IntSize( p->vVar2Inf ) / 2 ); - - printf( "Frame = %3d : ", f ); - printf( "Vecs = %8d ", Vec_IntSize( p->vVec2Var ) / p->nFrames ); - printf( "Vars = %8d ", Vec_IntSize( p->vVar2Inf ) / 2 ); - Abc_PrintTime( 1, "Time", clock() - clk ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abs_VfaMan_t * Abs_VfaManStart( Aig_Man_t * pAig ) -{ - Abs_VfaMan_t * p; - int i; - - p = ABC_CALLOC( Abs_VfaMan_t, 1 ); - p->pAig = pAig; - p->vObj2Vec = Vec_IntStart( Aig_ManObjNumMax(pAig) ); - p->vVec2Var = Vec_IntAlloc( 1 << 20 ); - p->vVar2Inf = Vec_IntAlloc( 1 << 20 ); - p->vFra2Var = Vec_IntStart( 1 ); - - // skip the first variable - Vec_IntPush( p->vVar2Inf, -3 ); - Vec_IntPush( p->vVar2Inf, -3 ); - for ( i = 0; i < p->nFrames; i++ ) - Vec_IntPush( p->vVec2Var, -1 ); - - // transfer values from CNF - p->pCnf = Cnf_DeriveOther( pAig, 0 ); - for ( i = 0; i < Aig_ManObjNumMax(pAig); i++ ) - if ( p->pCnf->pObj2Clause[i] == -1 ) - Vec_IntWriteEntry( p->vObj2Vec, i, -1 ); - - p->vAssumps = Vec_IntAlloc( 100 ); - p->vCore = Vec_IntAlloc( 100 ); - return p; -} - - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abs_VfaManStop( Abs_VfaMan_t * p ) -{ - Vec_IntFreeP( &p->vObj2Vec ); - Vec_IntFreeP( &p->vVec2Var ); - Vec_IntFreeP( &p->vVar2Inf ); - Vec_IntFreeP( &p->vFra2Var ); - Vec_IntFreeP( &p->vAssumps ); - Vec_IntFreeP( &p->vCore ); - if ( p->pCnf ) - Cnf_DataFree( p->pCnf ); - if ( p->pSat ) - sat_solver_delete( p->pSat ); - ABC_FREE( p ); -} - -/**Function************************************************************* - - Synopsis [Perform variable frame abstraction.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abs_VfaManTest( Aig_Man_t * pAig, int nFrames, int nConfLimit, int fVerbose ) -{ - Abs_VfaMan_t * p; - int i; - - p = Abs_VfaManStart( pAig ); - p->nFrames = nFrames; - p->nConfLimit = nConfLimit; - p->fVerbose = fVerbose; - - - // create unrolling for the given number of frames - for ( i = 0; i < p->nFrames; i++ ) - Abs_VfaManCreateFrame( p, i ); - - - Abs_VfaManStop( p ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/saig/saigSimExt.c b/src/aig/saig/saigSimExt.c deleted file mode 100644 index 1a5ec7e5..00000000 --- a/src/aig/saig/saigSimExt.c +++ /dev/null @@ -1,556 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigSimExt.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [Extending simulation trace to contain ternary values.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigSimExt.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.h" -#include "proof/ssw/ssw.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static inline int Saig_ManSimInfoNot( int Value ) -{ - if ( Value == SAIG_ZER ) - return SAIG_ONE; - if ( Value == SAIG_ONE ) - return SAIG_ZER; - return SAIG_UND; -} - -static inline int Saig_ManSimInfoAnd( int Value0, int Value1 ) -{ - if ( Value0 == SAIG_ZER || Value1 == SAIG_ZER ) - return SAIG_ZER; - if ( Value0 == SAIG_ONE && Value1 == SAIG_ONE ) - return SAIG_ONE; - return SAIG_UND; -} - -static inline int Saig_ManSimInfoGet( Vec_Ptr_t * vSimInfo, Aig_Obj_t * pObj, int iFrame ) -{ - unsigned * pInfo = (unsigned *)Vec_PtrEntry( vSimInfo, Aig_ObjId(pObj) ); - return 3 & (pInfo[iFrame >> 4] >> ((iFrame & 15) << 1)); -} - -static inline void Saig_ManSimInfoSet( Vec_Ptr_t * vSimInfo, Aig_Obj_t * pObj, int iFrame, int Value ) -{ - unsigned * pInfo = (unsigned *)Vec_PtrEntry( vSimInfo, Aig_ObjId(pObj) ); - assert( Value >= SAIG_ZER && Value <= SAIG_UND ); - Value ^= Saig_ManSimInfoGet( vSimInfo, pObj, iFrame ); - pInfo[iFrame >> 4] ^= (Value << ((iFrame & 15) << 1)); -} - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Performs ternary simulation for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManExtendOneEval( Vec_Ptr_t * vSimInfo, Aig_Obj_t * pObj, int iFrame ) -{ - int Value0, Value1, Value; - Value0 = Saig_ManSimInfoGet( vSimInfo, Aig_ObjFanin0(pObj), iFrame ); - if ( Aig_ObjFaninC0(pObj) ) - Value0 = Saig_ManSimInfoNot( Value0 ); - if ( Aig_ObjIsCo(pObj) ) - { - Saig_ManSimInfoSet( vSimInfo, pObj, iFrame, Value0 ); - return Value0; - } - assert( Aig_ObjIsNode(pObj) ); - Value1 = Saig_ManSimInfoGet( vSimInfo, Aig_ObjFanin1(pObj), iFrame ); - if ( Aig_ObjFaninC1(pObj) ) - Value1 = Saig_ManSimInfoNot( Value1 ); - Value = Saig_ManSimInfoAnd( Value0, Value1 ); - Saig_ManSimInfoSet( vSimInfo, pObj, iFrame, Value ); - return Value; -} - -/**Function************************************************************* - - Synopsis [Performs ternary simulation for one design.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManSimDataInit( Aig_Man_t * p, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, Vec_Int_t * vRes ) -{ - Aig_Obj_t * pObj, * pObjLi, * pObjLo; - int i, f, Entry, iBit = 0; - Saig_ManForEachLo( p, pObj, i ) - Saig_ManSimInfoSet( vSimInfo, pObj, 0, Abc_InfoHasBit(pCex->pData, iBit++)?SAIG_ONE:SAIG_ZER ); - for ( f = 0; f <= pCex->iFrame; f++ ) - { - Saig_ManSimInfoSet( vSimInfo, Aig_ManConst1(p), f, SAIG_ONE ); - Saig_ManForEachPi( p, pObj, i ) - Saig_ManSimInfoSet( vSimInfo, pObj, f, Abc_InfoHasBit(pCex->pData, iBit++)?SAIG_ONE:SAIG_ZER ); - if ( vRes ) - Vec_IntForEachEntry( vRes, Entry, i ) - Saig_ManSimInfoSet( vSimInfo, Aig_ManCi(p, Entry), f, SAIG_UND ); - Aig_ManForEachNode( p, pObj, i ) - Saig_ManExtendOneEval( vSimInfo, pObj, f ); - Aig_ManForEachCo( p, pObj, i ) - Saig_ManExtendOneEval( vSimInfo, pObj, f ); - if ( f == pCex->iFrame ) - break; - Saig_ManForEachLiLo( p, pObjLi, pObjLo, i ) - Saig_ManSimInfoSet( vSimInfo, pObjLo, f+1, Saig_ManSimInfoGet(vSimInfo, pObjLi, f) ); - } - // make sure the output of the property failed - pObj = Aig_ManCo( p, pCex->iPo ); - return Saig_ManSimInfoGet( vSimInfo, pObj, pCex->iFrame ); -} - -/**Function************************************************************* - - Synopsis [Tries to assign ternary value to one of the primary inputs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManExtendOne( Aig_Man_t * p, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, - int iPi, int iFrame, Vec_Int_t * vUndo, Vec_Int_t * vVis, Vec_Int_t * vVis2 ) -{ - Aig_Obj_t * pFanout, * pObj = Aig_ManCi(p, iPi); - int i, k, f, iFanout = -1, Value, Value2, Entry; - // save original value - Value = Saig_ManSimInfoGet( vSimInfo, pObj, iFrame ); - assert( Value == SAIG_ZER || Value == SAIG_ONE ); - Vec_IntPush( vUndo, Aig_ObjId(pObj) ); - Vec_IntPush( vUndo, iFrame ); - Vec_IntPush( vUndo, Value ); - // update original value - Saig_ManSimInfoSet( vSimInfo, pObj, iFrame, SAIG_UND ); - // traverse - Vec_IntClear( vVis ); - Vec_IntPush( vVis, Aig_ObjId(pObj) ); - for ( f = iFrame; f <= pCex->iFrame; f++ ) - { - Vec_IntClear( vVis2 ); - Vec_IntForEachEntry( vVis, Entry, i ) - { - pObj = Aig_ManObj( p, Entry ); - Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, k ) - { - assert( Aig_ObjId(pObj) < Aig_ObjId(pFanout) ); - Value = Saig_ManSimInfoGet( vSimInfo, pFanout, f ); - if ( Value == SAIG_UND ) - continue; - Value2 = Saig_ManExtendOneEval( vSimInfo, pFanout, f ); - if ( Value2 == Value ) - continue; - assert( Value2 == SAIG_UND ); -// assert( Vec_IntFind(vVis, Aig_ObjId(pFanout)) == -1 ); - if ( Aig_ObjIsNode(pFanout) ) - Vec_IntPushOrder( vVis, Aig_ObjId(pFanout) ); - else if ( Saig_ObjIsLi(p, pFanout) ) - Vec_IntPush( vVis2, Aig_ObjId(pFanout) ); - Vec_IntPush( vUndo, Aig_ObjId(pFanout) ); - Vec_IntPush( vUndo, f ); - Vec_IntPush( vUndo, Value ); - } - } - if ( Vec_IntSize(vVis2) == 0 ) - break; - if ( f == pCex->iFrame ) - break; - // transfer - Vec_IntClear( vVis ); - Vec_IntForEachEntry( vVis2, Entry, i ) - { - pObj = Aig_ManObj( p, Entry ); - assert( Saig_ObjIsLi(p, pObj) ); - pFanout = Saig_ObjLiToLo( p, pObj ); - Vec_IntPushOrder( vVis, Aig_ObjId(pFanout) ); - Value = Saig_ManSimInfoGet( vSimInfo, pObj, f ); - Saig_ManSimInfoSet( vSimInfo, pFanout, f+1, Value ); - } - } - // check the output - pObj = Aig_ManCo( p, pCex->iPo ); - Value = Saig_ManSimInfoGet( vSimInfo, pObj, pCex->iFrame ); - assert( Value == SAIG_ONE || Value == SAIG_UND ); - return (int)(Value == SAIG_ONE); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManExtendUndo( Aig_Man_t * p, Vec_Ptr_t * vSimInfo, Vec_Int_t * vUndo ) -{ - Aig_Obj_t * pObj; - int i, iFrame, Value; - for ( i = 0; i < Vec_IntSize(vUndo); i += 3 ) - { - pObj = Aig_ManObj( p, Vec_IntEntry(vUndo, i) ); - iFrame = Vec_IntEntry(vUndo, i+1); - Value = Vec_IntEntry(vUndo, i+2); - assert( Saig_ManSimInfoGet(vSimInfo, pObj, iFrame) == SAIG_UND ); - Saig_ManSimInfoSet( vSimInfo, pObj, iFrame, Value ); - } -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExample0( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Vec_Int_t * vRes, * vResInv, * vUndo, * vVis, * vVis2; - int i, f, Value; -// assert( Aig_ManRegNum(p) > 0 ); - assert( (unsigned *)Vec_PtrEntry(vSimInfo,1) - (unsigned *)Vec_PtrEntry(vSimInfo,0) >= Abc_BitWordNum(2*(pCex->iFrame+1)) ); - // start simulation data - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, NULL ); - assert( Value == SAIG_ONE ); - // select the result - vRes = Vec_IntAlloc( 1000 ); - vResInv = Vec_IntAlloc( 1000 ); - vVis = Vec_IntAlloc( 1000 ); - vVis2 = Vec_IntAlloc( 1000 ); - vUndo = Vec_IntAlloc( 1000 ); - for ( i = iFirstFlopPi; i < Saig_ManPiNum(p); i++ ) - { - Vec_IntClear( vUndo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - if ( !Saig_ManExtendOne( p, pCex, vSimInfo, i, f, vUndo, vVis, vVis2 ) ) - { - Saig_ManExtendUndo( p, vSimInfo, vUndo ); - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - Vec_IntFree( vVis ); - Vec_IntFree( vVis2 ); - Vec_IntFree( vUndo ); - // resimulate to make sure it is valid - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, vResInv ); - assert( Value == SAIG_ONE ); - Vec_IntFree( vResInv ); - return vRes; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExample1( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Vec_Int_t * vRes, * vResInv, * vUndo, * vVis, * vVis2; - int i, f, Value; -// assert( Aig_ManRegNum(p) > 0 ); - assert( (unsigned *)Vec_PtrEntry(vSimInfo,1) - (unsigned *)Vec_PtrEntry(vSimInfo,0) >= Abc_BitWordNum(2*(pCex->iFrame+1)) ); - // start simulation data - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, NULL ); - assert( Value == SAIG_ONE ); - // select the result - vRes = Vec_IntAlloc( 1000 ); - vResInv = Vec_IntAlloc( 1000 ); - vVis = Vec_IntAlloc( 1000 ); - vVis2 = Vec_IntAlloc( 1000 ); - vUndo = Vec_IntAlloc( 1000 ); - for ( i = Saig_ManPiNum(p) - 1; i >= iFirstFlopPi; i-- ) - { - Vec_IntClear( vUndo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - if ( !Saig_ManExtendOne( p, pCex, vSimInfo, i, f, vUndo, vVis, vVis2 ) ) - { - Saig_ManExtendUndo( p, vSimInfo, vUndo ); - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - Vec_IntFree( vVis ); - Vec_IntFree( vVis2 ); - Vec_IntFree( vUndo ); - // resimulate to make sure it is valid - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, vResInv ); - assert( Value == SAIG_ONE ); - Vec_IntFree( vResInv ); - return vRes; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExample2( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Vec_Int_t * vRes, * vResInv, * vUndo, * vVis, * vVis2; - int i, f, Value; -// assert( Aig_ManRegNum(p) > 0 ); - assert( (unsigned *)Vec_PtrEntry(vSimInfo,1) - (unsigned *)Vec_PtrEntry(vSimInfo,0) >= Abc_BitWordNum(2*(pCex->iFrame+1)) ); - // start simulation data - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, NULL ); - assert( Value == SAIG_ONE ); - // select the result - vRes = Vec_IntAlloc( 1000 ); - vResInv = Vec_IntAlloc( 1000 ); - vVis = Vec_IntAlloc( 1000 ); - vVis2 = Vec_IntAlloc( 1000 ); - vUndo = Vec_IntAlloc( 1000 ); - for ( i = iFirstFlopPi; i < Saig_ManPiNum(p); i++ ) - { - if ( i % 2 == 0 ) - continue; - Vec_IntClear( vUndo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - if ( !Saig_ManExtendOne( p, pCex, vSimInfo, i, f, vUndo, vVis, vVis2 ) ) - { - Saig_ManExtendUndo( p, vSimInfo, vUndo ); - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - for ( i = iFirstFlopPi; i < Saig_ManPiNum(p); i++ ) - { - if ( i % 2 == 1 ) - continue; - Vec_IntClear( vUndo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - if ( !Saig_ManExtendOne( p, pCex, vSimInfo, i, f, vUndo, vVis, vVis2 ) ) - { - Saig_ManExtendUndo( p, vSimInfo, vUndo ); - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - Vec_IntFree( vVis ); - Vec_IntFree( vVis2 ); - Vec_IntFree( vUndo ); - // resimulate to make sure it is valid - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, vResInv ); - assert( Value == SAIG_ONE ); - Vec_IntFree( vResInv ); - return vRes; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExample3( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Vec_Int_t * vRes, * vResInv, * vUndo, * vVis, * vVis2; - int i, f, Value; -// assert( Aig_ManRegNum(p) > 0 ); - assert( (unsigned *)Vec_PtrEntry(vSimInfo,1) - (unsigned *)Vec_PtrEntry(vSimInfo,0) >= Abc_BitWordNum(2*(pCex->iFrame+1)) ); - // start simulation data - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, NULL ); - assert( Value == SAIG_ONE ); - // select the result - vRes = Vec_IntAlloc( 1000 ); - vResInv = Vec_IntAlloc( 1000 ); - vVis = Vec_IntAlloc( 1000 ); - vVis2 = Vec_IntAlloc( 1000 ); - vUndo = Vec_IntAlloc( 1000 ); - for ( i = Saig_ManPiNum(p) - 1; i >= iFirstFlopPi; i-- ) - { - if ( i % 2 == 0 ) - continue; - Vec_IntClear( vUndo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - if ( !Saig_ManExtendOne( p, pCex, vSimInfo, i, f, vUndo, vVis, vVis2 ) ) - { - Saig_ManExtendUndo( p, vSimInfo, vUndo ); - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - for ( i = Saig_ManPiNum(p) - 1; i >= iFirstFlopPi; i-- ) - { - if ( i % 2 == 1 ) - continue; - Vec_IntClear( vUndo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - if ( !Saig_ManExtendOne( p, pCex, vSimInfo, i, f, vUndo, vVis, vVis2 ) ) - { - Saig_ManExtendUndo( p, vSimInfo, vUndo ); - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - Vec_IntFree( vVis ); - Vec_IntFree( vVis2 ); - Vec_IntFree( vUndo ); - // resimulate to make sure it is valid - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, vResInv ); - assert( Value == SAIG_ONE ); - Vec_IntFree( vResInv ); - return vRes; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExample( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Vec_Int_t * vRes0 = Saig_ManExtendCounterExample0( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - Vec_Int_t * vRes1 = Saig_ManExtendCounterExample1( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - Vec_Int_t * vRes2 = Saig_ManExtendCounterExample2( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - Vec_Int_t * vRes3 = Saig_ManExtendCounterExample3( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - Vec_Int_t * vRes = vRes0; -// if ( fVerbose ) - printf( "Removable flops: Order0 =%3d. Order1 =%3d. Order2 =%3d. Order3 =%3d.\n", - Vec_IntSize(vRes0), Vec_IntSize(vRes1), Vec_IntSize(vRes2), Vec_IntSize(vRes3) ); - if ( Vec_IntSize(vRes1) < Vec_IntSize(vRes) ) - vRes = vRes1; - if ( Vec_IntSize(vRes2) < Vec_IntSize(vRes) ) - vRes = vRes2; - if ( Vec_IntSize(vRes3) < Vec_IntSize(vRes) ) - vRes = vRes3; - vRes = Vec_IntDup( vRes ); - Vec_IntFree( vRes0 ); - Vec_IntFree( vRes1 ); - Vec_IntFree( vRes2 ); - Vec_IntFree( vRes3 ); - return vRes; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExampleTest( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, int fTryFour, int fVerbose ) -{ - Vec_Int_t * vRes; - Vec_Ptr_t * vSimInfo; - clock_t clk; - if ( Saig_ManPiNum(p) != pCex->nPis ) - { - printf( "Saig_ManExtendCounterExampleTest(): The PI count of AIG (%d) does not match that of cex (%d).\n", - Aig_ManCiNum(p), pCex->nPis ); - return NULL; - } - Aig_ManFanoutStart( p ); - vSimInfo = Vec_PtrAllocSimInfo( Aig_ManObjNumMax(p), Abc_BitWordNum(2*(pCex->iFrame+1)) ); - Vec_PtrCleanSimInfo( vSimInfo, 0, Abc_BitWordNum(2*(pCex->iFrame+1)) ); - -clk = clock(); - if ( fTryFour ) - vRes = Saig_ManExtendCounterExample( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - else - vRes = Saig_ManExtendCounterExample0( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - if ( fVerbose ) - { - printf( "Total new PIs = %3d. Non-removable PIs = %3d. ", Saig_ManPiNum(p)-iFirstFlopPi, Vec_IntSize(vRes) ); -ABC_PRT( "Time", clock() - clk ); - } - Vec_PtrFree( vSimInfo ); - Aig_ManFanoutStop( p ); - return vRes; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/saig/saigSimExt2.c b/src/aig/saig/saigSimExt2.c deleted file mode 100644 index ca46c0b3..00000000 --- a/src/aig/saig/saigSimExt2.c +++ /dev/null @@ -1,481 +0,0 @@ -/**CFile**************************************************************** - - FileName [saigSimExt2.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Sequential AIG package.] - - Synopsis [Extending simulation trace to contain ternary values.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: saigSimExt2.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "saig.h" -#include "proof/ssw/ssw.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -#define SAIG_ZER_NEW 0 // 0 not visited -#define SAIG_ONE_NEW 1 // 1 not visited -#define SAIG_ZER_OLD 2 // 0 visited -#define SAIG_ONE_OLD 3 // 1 visited - -static inline int Saig_ManSimInfo2IsOld( int Value ) -{ - return Value == SAIG_ZER_OLD || Value == SAIG_ONE_OLD; -} - -static inline int Saig_ManSimInfo2SetOld( int Value ) -{ - if ( Value == SAIG_ZER_NEW ) - return SAIG_ZER_OLD; - if ( Value == SAIG_ONE_NEW ) - return SAIG_ONE_OLD; - assert( 0 ); - return 0; -} - -static inline int Saig_ManSimInfo2Not( int Value ) -{ - if ( Value == SAIG_ZER_NEW ) - return SAIG_ONE_NEW; - if ( Value == SAIG_ONE_NEW ) - return SAIG_ZER_NEW; - if ( Value == SAIG_ZER_OLD ) - return SAIG_ONE_OLD; - if ( Value == SAIG_ONE_OLD ) - return SAIG_ZER_OLD; - assert( 0 ); - return 0; -} - -static inline int Saig_ManSimInfo2And( int Value0, int Value1 ) -{ - if ( Value0 == SAIG_ZER_NEW || Value1 == SAIG_ZER_NEW ) - return SAIG_ZER_NEW; - if ( Value0 == SAIG_ONE_NEW && Value1 == SAIG_ONE_NEW ) - return SAIG_ONE_NEW; - assert( 0 ); - return 0; -} - -static inline int Saig_ManSimInfo2Get( Vec_Ptr_t * vSimInfo, Aig_Obj_t * pObj, int iFrame ) -{ - unsigned * pInfo = (unsigned *)Vec_PtrEntry( vSimInfo, Aig_ObjId(pObj) ); - return 3 & (pInfo[iFrame >> 4] >> ((iFrame & 15) << 1)); -} - -static inline void Saig_ManSimInfo2Set( Vec_Ptr_t * vSimInfo, Aig_Obj_t * pObj, int iFrame, int Value ) -{ - unsigned * pInfo = (unsigned *)Vec_PtrEntry( vSimInfo, Aig_ObjId(pObj) ); - Value ^= Saig_ManSimInfo2Get( vSimInfo, pObj, iFrame ); - pInfo[iFrame >> 4] ^= (Value << ((iFrame & 15) << 1)); -} - -// performs ternary simulation -extern int Saig_ManSimDataInit( Aig_Man_t * p, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, Vec_Int_t * vRes ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Performs ternary simulation for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManExtendOneEval2( Vec_Ptr_t * vSimInfo, Aig_Obj_t * pObj, int iFrame ) -{ - int Value0, Value1, Value; - Value0 = Saig_ManSimInfo2Get( vSimInfo, Aig_ObjFanin0(pObj), iFrame ); - if ( Aig_ObjFaninC0(pObj) ) - Value0 = Saig_ManSimInfo2Not( Value0 ); - if ( Aig_ObjIsCo(pObj) ) - { - Saig_ManSimInfo2Set( vSimInfo, pObj, iFrame, Value0 ); - return Value0; - } - assert( Aig_ObjIsNode(pObj) ); - Value1 = Saig_ManSimInfo2Get( vSimInfo, Aig_ObjFanin1(pObj), iFrame ); - if ( Aig_ObjFaninC1(pObj) ) - Value1 = Saig_ManSimInfo2Not( Value1 ); - Value = Saig_ManSimInfo2And( Value0, Value1 ); - Saig_ManSimInfo2Set( vSimInfo, pObj, iFrame, Value ); - return Value; -} - -/**Function************************************************************* - - Synopsis [Performs sensitization analysis for one design.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Saig_ManSimDataInit2( Aig_Man_t * p, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo ) -{ - Aig_Obj_t * pObj, * pObjLi, * pObjLo; - int i, f, iBit = 0; - Saig_ManForEachLo( p, pObj, i ) - Saig_ManSimInfo2Set( vSimInfo, pObj, 0, Abc_InfoHasBit(pCex->pData, iBit++)?SAIG_ONE_NEW:SAIG_ZER_NEW ); - for ( f = 0; f <= pCex->iFrame; f++ ) - { - Saig_ManSimInfo2Set( vSimInfo, Aig_ManConst1(p), f, SAIG_ONE_NEW ); - Saig_ManForEachPi( p, pObj, i ) - Saig_ManSimInfo2Set( vSimInfo, pObj, f, Abc_InfoHasBit(pCex->pData, iBit++)?SAIG_ONE_NEW:SAIG_ZER_NEW ); - Aig_ManForEachNode( p, pObj, i ) - Saig_ManExtendOneEval2( vSimInfo, pObj, f ); - Aig_ManForEachCo( p, pObj, i ) - Saig_ManExtendOneEval2( vSimInfo, pObj, f ); - if ( f == pCex->iFrame ) - break; - Saig_ManForEachLiLo( p, pObjLi, pObjLo, i ) - Saig_ManSimInfo2Set( vSimInfo, pObjLo, f+1, Saig_ManSimInfo2Get(vSimInfo, pObjLi, f) ); - } - // make sure the output of the property failed - pObj = Aig_ManCo( p, pCex->iPo ); - return Saig_ManSimInfo2Get( vSimInfo, pObj, pCex->iFrame ); -} - -/**Function************************************************************* - - Synopsis [Drive implications of the given node towards primary outputs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManSetAndDriveImplications_rec( Aig_Man_t * p, Aig_Obj_t * pObj, int f, int fMax, Vec_Ptr_t * vSimInfo ) -{ - Aig_Obj_t * pFanout; - int k, iFanout = -1, Value0, Value1; - int Value = Saig_ManSimInfo2Get( vSimInfo, pObj, f ); - assert( !Saig_ManSimInfo2IsOld( Value ) ); - Saig_ManSimInfo2Set( vSimInfo, pObj, f, Saig_ManSimInfo2SetOld(Value) ); - if ( (Aig_ObjIsCo(pObj) && f == fMax) || Saig_ObjIsPo(p, pObj) ) - return; - if ( Saig_ObjIsLi( p, pObj ) ) - { - assert( f < fMax ); - pFanout = Saig_ObjLiToLo(p, pObj); - Value = Saig_ManSimInfo2Get( vSimInfo, pFanout, f+1 ); - if ( !Saig_ManSimInfo2IsOld( Value ) ) - Saig_ManSetAndDriveImplications_rec( p, pFanout, f+1, fMax, vSimInfo ); - return; - } - assert( Aig_ObjIsCi(pObj) || Aig_ObjIsNode(pObj) || Aig_ObjIsConst1(pObj) ); - Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, k ) - { - Value = Saig_ManSimInfo2Get( vSimInfo, pFanout, f ); - if ( Saig_ManSimInfo2IsOld( Value ) ) - continue; - if ( Aig_ObjIsCo(pFanout) ) - { - Saig_ManSetAndDriveImplications_rec( p, pFanout, f, fMax, vSimInfo ); - continue; - } - assert( Aig_ObjIsNode(pFanout) ); - Value0 = Saig_ManSimInfo2Get( vSimInfo, Aig_ObjFanin0(pFanout), f ); - Value1 = Saig_ManSimInfo2Get( vSimInfo, Aig_ObjFanin1(pFanout), f ); - if ( Aig_ObjFaninC0(pFanout) ) - Value0 = Saig_ManSimInfo2Not( Value0 ); - if ( Aig_ObjFaninC1(pFanout) ) - Value1 = Saig_ManSimInfo2Not( Value1 ); - if ( Value0 == SAIG_ZER_OLD || Value1 == SAIG_ZER_OLD || - (Value0 == SAIG_ONE_OLD && Value1 == SAIG_ONE_OLD) ) - Saig_ManSetAndDriveImplications_rec( p, pFanout, f, fMax, vSimInfo ); - } -} - -/**Function************************************************************* - - Synopsis [Performs recursive sensetization analysis.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Saig_ManExplorePaths_rec( Aig_Man_t * p, Aig_Obj_t * pObj, int f, int fMax, Vec_Ptr_t * vSimInfo ) -{ - int Value = Saig_ManSimInfo2Get( vSimInfo, pObj, f ); - if ( Saig_ManSimInfo2IsOld( Value ) ) - return; - Saig_ManSetAndDriveImplications_rec( p, pObj, f, fMax, vSimInfo ); - assert( !Aig_ObjIsConst1(pObj) ); - if ( Saig_ObjIsLo(p, pObj) && f == 0 ) - return; - if ( Saig_ObjIsPi(p, pObj) ) - { - // propagate implications of this assignment - int i, iPiNum = Aig_ObjCioId(pObj); - for ( i = fMax; i >= 0; i-- ) - if ( i != f ) - Saig_ManSetAndDriveImplications_rec( p, Aig_ManCi(p, iPiNum), i, fMax, vSimInfo ); - return; - } - if ( Saig_ObjIsLo( p, pObj ) ) - { - assert( f > 0 ); - Saig_ManExplorePaths_rec( p, Saig_ObjLoToLi(p, pObj), f-1, fMax, vSimInfo ); - return; - } - if ( Aig_ObjIsCo(pObj) ) - { - Saig_ManExplorePaths_rec( p, Aig_ObjFanin0(pObj), f, fMax, vSimInfo ); - return; - } - assert( Aig_ObjIsNode(pObj) ); - if ( Value == SAIG_ZER_OLD ) - { -// if ( (Aig_ObjId(pObj) & 1) == 0 ) - Saig_ManExplorePaths_rec( p, Aig_ObjFanin0(pObj), f, fMax, vSimInfo ); -// else -// Saig_ManExplorePaths_rec( p, Aig_ObjFanin1(pObj), f, fMax, vSimInfo ); - } - else - { - Saig_ManExplorePaths_rec( p, Aig_ObjFanin0(pObj), f, fMax, vSimInfo ); - Saig_ManExplorePaths_rec( p, Aig_ObjFanin1(pObj), f, fMax, vSimInfo ); - } -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManProcessCex( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Aig_Obj_t * pObj; - Vec_Int_t * vRes, * vResInv; - int i, f, Value; -// assert( Aig_ManRegNum(p) > 0 ); - assert( (unsigned *)Vec_PtrEntry(vSimInfo,1) - (unsigned *)Vec_PtrEntry(vSimInfo,0) >= Abc_BitWordNum(2*(pCex->iFrame+1)) ); - // start simulation data - Value = Saig_ManSimDataInit2( p, pCex, vSimInfo ); - assert( Value == SAIG_ONE_NEW ); - // derive implications of constants and primary inputs - Saig_ManForEachLo( p, pObj, i ) - Saig_ManSetAndDriveImplications_rec( p, pObj, 0, pCex->iFrame, vSimInfo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - { - Saig_ManSetAndDriveImplications_rec( p, Aig_ManConst1(p), f, pCex->iFrame, vSimInfo ); - for ( i = 0; i < iFirstFlopPi; i++ ) - Saig_ManSetAndDriveImplications_rec( p, Aig_ManCi(p, i), f, pCex->iFrame, vSimInfo ); - } - // recursively compute justification - Saig_ManExplorePaths_rec( p, Aig_ManCo(p, pCex->iPo), pCex->iFrame, pCex->iFrame, vSimInfo ); - // select the result - vRes = Vec_IntAlloc( 1000 ); - vResInv = Vec_IntAlloc( 1000 ); - for ( i = iFirstFlopPi; i < Saig_ManPiNum(p); i++ ) - { - for ( f = pCex->iFrame; f >= 0; f-- ) - { - Value = Saig_ManSimInfo2Get( vSimInfo, Aig_ManCi(p, i), f ); - if ( Saig_ManSimInfo2IsOld( Value ) ) - break; - } - if ( f >= 0 ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - // resimulate to make sure it is valid - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, vResInv ); - assert( Value == SAIG_ONE ); - Vec_IntFree( vResInv ); - return vRes; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Saig_ManExtendCounterExampleTest2( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, int fVerbose ) -{ - Vec_Int_t * vRes; - Vec_Ptr_t * vSimInfo; - clock_t clk; - if ( Saig_ManPiNum(p) != pCex->nPis ) - { - printf( "Saig_ManExtendCounterExampleTest2(): The PI count of AIG (%d) does not match that of cex (%d).\n", - Aig_ManCiNum(p), pCex->nPis ); - return NULL; - } - Aig_ManFanoutStart( p ); - vSimInfo = Vec_PtrAllocSimInfo( Aig_ManObjNumMax(p), Abc_BitWordNum(2*(pCex->iFrame+1)) ); - Vec_PtrCleanSimInfo( vSimInfo, 0, Abc_BitWordNum(2*(pCex->iFrame+1)) ); - -clk = clock(); - vRes = Saig_ManProcessCex( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - if ( fVerbose ) - { - printf( "Total new PIs = %3d. Non-removable PIs = %3d. ", Saig_ManPiNum(p)-iFirstFlopPi, Vec_IntSize(vRes) ); -ABC_PRT( "Time", clock() - clk ); - } - Vec_PtrFree( vSimInfo ); - Aig_ManFanoutStop( p ); - return vRes; -} - - - - - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Cex_t * Saig_ManDeriveCex( Aig_Man_t * p, int iFirstFlopPi, Abc_Cex_t * pCex, Vec_Ptr_t * vSimInfo, int fVerbose ) -{ - Abc_Cex_t * pCare; - Aig_Obj_t * pObj; - Vec_Int_t * vRes, * vResInv; - int i, f, Value; -// assert( Aig_ManRegNum(p) > 0 ); - assert( (unsigned *)Vec_PtrEntry(vSimInfo,1) - (unsigned *)Vec_PtrEntry(vSimInfo,0) >= Abc_BitWordNum(2*(pCex->iFrame+1)) ); - // start simulation data - Value = Saig_ManSimDataInit2( p, pCex, vSimInfo ); - assert( Value == SAIG_ONE_NEW ); - // derive implications of constants and primary inputs - Saig_ManForEachLo( p, pObj, i ) - Saig_ManSetAndDriveImplications_rec( p, pObj, 0, pCex->iFrame, vSimInfo ); - for ( f = pCex->iFrame; f >= 0; f-- ) - { - Saig_ManSetAndDriveImplications_rec( p, Aig_ManConst1(p), f, pCex->iFrame, vSimInfo ); - for ( i = 0; i < iFirstFlopPi; i++ ) - Saig_ManSetAndDriveImplications_rec( p, Aig_ManCi(p, i), f, pCex->iFrame, vSimInfo ); - } - // recursively compute justification - Saig_ManExplorePaths_rec( p, Aig_ManCo(p, pCex->iPo), pCex->iFrame, pCex->iFrame, vSimInfo ); - - // create CEX - pCare = Abc_CexDup( pCex, pCex->nRegs ); - memset( pCare->pData, 0, sizeof(unsigned) * Abc_BitWordNum(pCare->nBits) ); - - // select the result - vRes = Vec_IntAlloc( 1000 ); - vResInv = Vec_IntAlloc( 1000 ); - for ( i = iFirstFlopPi; i < Saig_ManPiNum(p); i++ ) - { - int fFound = 0; - for ( f = pCex->iFrame; f >= 0; f-- ) - { - Value = Saig_ManSimInfo2Get( vSimInfo, Aig_ManCi(p, i), f ); - if ( Saig_ManSimInfo2IsOld( Value ) ) - { - fFound = 1; - Abc_InfoSetBit( pCare->pData, pCare->nRegs + pCare->nPis * f + i ); - } - } - if ( fFound ) - Vec_IntPush( vRes, i ); - else - Vec_IntPush( vResInv, i ); - } - // resimulate to make sure it is valid - Value = Saig_ManSimDataInit( p, pCex, vSimInfo, vResInv ); - assert( Value == SAIG_ONE ); - Vec_IntFree( vResInv ); - Vec_IntFree( vRes ); - - return pCare; -} - -/**Function************************************************************* - - Synopsis [Returns the array of PIs for flops that should not be absracted.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Cex_t * Saig_ManFindCexCareBitsSense( Aig_Man_t * p, Abc_Cex_t * pCex, int iFirstFlopPi, int fVerbose ) -{ - Abc_Cex_t * pCare; - Vec_Ptr_t * vSimInfo; - clock_t clk; - if ( Saig_ManPiNum(p) != pCex->nPis ) - { - printf( "Saig_ManExtendCounterExampleTest2(): The PI count of AIG (%d) does not match that of cex (%d).\n", - Aig_ManCiNum(p), pCex->nPis ); - return NULL; - } - Aig_ManFanoutStart( p ); - vSimInfo = Vec_PtrAllocSimInfo( Aig_ManObjNumMax(p), Abc_BitWordNum(2*(pCex->iFrame+1)) ); - Vec_PtrCleanSimInfo( vSimInfo, 0, Abc_BitWordNum(2*(pCex->iFrame+1)) ); - -clk = clock(); - pCare = Saig_ManDeriveCex( p, iFirstFlopPi, pCex, vSimInfo, fVerbose ); - if ( fVerbose ) - { -// printf( "Total new PIs = %3d. Non-removable PIs = %3d. ", Saig_ManPiNum(p)-iFirstFlopPi, Vec_IntSize(vRes) ); -Abc_CexPrintStats( pCex ); -Abc_CexPrintStats( pCare ); -ABC_PRT( "Time", clock() - clk ); - } - - Vec_PtrFree( vSimInfo ); - Aig_ManFanoutStop( p ); - return pCare; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - |