From 640100954ad8bdc1c77e981e8ba4ccb883bc8bef Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 5 Aug 2016 20:34:44 -0700 Subject: Updates to arithmetic verification. --- abclib.dsp | 4 +++ src/base/abci/abc.c | 2 +- src/base/wlc/wlc.h | 2 +- src/base/wlc/wlcBlast.c | 30 +++++++++------- src/base/wlc/wlcCom.c | 12 ++++--- src/base/wlc/wlcReadVer.c | 2 +- src/base/wlc/wlcSim.c | 2 +- src/proof/acec/acecPolyn.c | 89 ++++++++++++++++++++++++++++------------------ 8 files changed, 88 insertions(+), 55 deletions(-) diff --git a/abclib.dsp b/abclib.dsp index f2dbc1b3..7d1c1551 100644 --- a/abclib.dsp +++ b/abclib.dsp @@ -5355,6 +5355,10 @@ SOURCE=.\src\proof\acec\acecCore.c # End Source File # Begin Source File +SOURCE=.\src\proof\acec\acecCover.c +# End Source File +# Begin Source File + SOURCE=.\src\proof\acec\acecFadds.c # End Source File # Begin Source File diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 4dc50ed2..31f3a275 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -40126,7 +40126,7 @@ usage: int Abc_CommandAbc9Polyn( Abc_Frame_t * pAbc, int argc, char ** argv ) { Vec_Int_t * vOrder = NULL; - int c, fSimple = 0, fSigned = 0, fVerbose = 0, fVeryVerbose = 0; + int c, fSimple = 1, fSigned = 0, fVerbose = 0, fVeryVerbose = 0; Extra_UtilGetoptReset(); while ( ( c = Extra_UtilGetopt( argc, argv, "asvwh" ) ) != EOF ) { diff --git a/src/base/wlc/wlc.h b/src/base/wlc/wlc.h index 5791731e..bb5c4bfe 100644 --- a/src/base/wlc/wlc.h +++ b/src/base/wlc/wlc.h @@ -259,7 +259,7 @@ extern Vec_Int_t * Wlc_NtkFindUifableMultiplierPairs( Wlc_Ntk_t * p ); extern Wlc_Ntk_t * Wlc_NtkAbstractNodes( Wlc_Ntk_t * pNtk, Vec_Int_t * vNodes ); extern Wlc_Ntk_t * Wlc_NtkUifNodePairs( Wlc_Ntk_t * pNtk, Vec_Int_t * vPairs ); /*=== wlcBlast.c ========================================================*/ -extern Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nRange, int fGiaSimple, int fAddOutputs ); +extern Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nRange, int fGiaSimple, int fAddOutputs, int fBooth ); /*=== wlcCom.c ========================================================*/ extern void Wlc_SetNtk( Abc_Frame_t * pAbc, Wlc_Ntk_t * pNtk ); /*=== wlcNtk.c ========================================================*/ diff --git a/src/base/wlc/wlcBlast.c b/src/base/wlc/wlcBlast.c index 97b32144..c86c7cf0 100644 --- a/src/base/wlc/wlcBlast.c +++ b/src/base/wlc/wlcBlast.c @@ -635,7 +635,7 @@ void Wlc_IntInsert( Vec_Int_t * vProd, Vec_Int_t * vLevel, int Node, int Level ) Vec_IntInsert( vProd, i + 1, Node ); Vec_IntInsert( vLevel, i + 1, Level ); } -void Wlc_BlastReduceMatrix( Gia_Man_t * pNew, Vec_Wec_t * vProds, Vec_Wec_t * vLevels, Vec_Int_t * vRes, int nSizeMax ) +void Wlc_BlastReduceMatrix( Gia_Man_t * pNew, Vec_Wec_t * vProds, Vec_Wec_t * vLevels, Vec_Int_t * vRes ) { Vec_Int_t * vLevel, * vProd; int i, NodeS, NodeC, LevelS, LevelC, Node1, Node2, Node3, Level1, Level2, Level3; @@ -691,7 +691,9 @@ void Wlc_BlastReduceMatrix( Gia_Man_t * pNew, Vec_Wec_t * vProds, Vec_Wec_t * vL Vec_IntPush( vRes, Vec_IntEntry(vProd, 0) ); Vec_IntPush( vLevel, Vec_IntEntry(vProd, 1) ); } - Wlc_BlastAdder( pNew, Vec_IntArray(vRes), Vec_IntArray(vLevel), nSizeMax ); + Vec_IntPush( vRes, 0 ); + Vec_IntPush( vLevel, 0 ); + Wlc_BlastAdder( pNew, Vec_IntArray(vRes), Vec_IntArray(vLevel), Vec_IntSize(vRes) ); } void Wlc_BlastMultiplier3( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int nArgB, Vec_Int_t * vRes ) { @@ -705,7 +707,7 @@ void Wlc_BlastMultiplier3( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA Vec_WecPush( vLevels, i+k, 0 ); } - Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes, nArgA + nArgB ); + Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes ); Vec_WecFree( vProds ); Vec_WecFree( vLevels ); @@ -730,15 +732,15 @@ void Wlc_BlastSquare( Gia_Man_t * pNew, int * pNum, int nNum, Vec_Int_t * vTmp, } } - Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes, 2*nNum ); + Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes ); Vec_WecFree( vProds ); Vec_WecFree( vLevels ); } void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int nArgB, Vec_Int_t * vRes, int fSigned ) { - Vec_Wec_t * vProds = Vec_WecStart( nArgA + nArgB ); - Vec_Wec_t * vLevels = Vec_WecStart( nArgA + nArgB ); + Vec_Wec_t * vProds = Vec_WecStart( nArgA + nArgB + 3 ); + Vec_Wec_t * vLevels = Vec_WecStart( nArgA + nArgB + 3 ); int FillA = fSigned ? pArgA[nArgA-1] : 0; int FillB = fSigned ? pArgB[nArgB-1] : 0; int i, k, Sign; @@ -769,6 +771,8 @@ void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int pp = Gia_ManHashXor( pNew, Part, Neg ); + if ( pp == 0 ) + continue; Vec_WecPush( vProds, k+i, pp ); Vec_WecPush( vLevels, k+i, 0 ); } @@ -799,9 +803,9 @@ void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int Vec_WecPush( vProds, k, Neg ); Vec_WecPush( vLevels, k, 0 ); } -// Vec_WecPrint( vProds, 0 ); + //Vec_WecPrint( vProds, 0 ); - Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes, nArgA + nArgB ); + Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes ); Vec_WecFree( vProds ); Vec_WecFree( vLevels ); @@ -820,7 +824,7 @@ void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int SeeAlso [] ***********************************************************************/ -Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nOutputRange, int fGiaSimple, int fAddOutputs ) +Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nOutputRange, int fGiaSimple, int fAddOutputs, int fBooth ) { int fVerbose = 0; int fUseOldMultiplierBlasting = 0; @@ -1229,10 +1233,12 @@ Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, in int * pArg1 = Wlc_VecLoadFanins( vTemp1, pFans1, nRange1, nRangeMax, fSigned ); if ( Wlc_NtkCountConstBits(pArg0, nRangeMax) < Wlc_NtkCountConstBits(pArg1, nRangeMax) ) ABC_SWAP( int *, pArg0, pArg1 ); - Wlc_BlastMultiplier( pNew, pArg0, pArg1, nRangeMax, nRangeMax, vTemp2, vRes, fSigned ); - //Wlc_BlastBooth( pNew, pArg0, pArg1, nRange0, nRange1, vRes, fSigned ); + if ( fBooth ) + Wlc_BlastBooth( pNew, pArg0, pArg1, nRange0, nRange1, vRes, fSigned ); + else + Wlc_BlastMultiplier( pNew, pArg0, pArg1, nRangeMax, nRangeMax, vTemp2, vRes, fSigned ); //Wlc_BlastMultiplier3( pNew, pArg0, pArg1, nRange0, nRange1, vRes ); - if ( nRange > nRangeMax + nRangeMax ) + if ( nRange > Vec_IntSize(vRes) ) Vec_IntFillExtra( vRes, nRange, fSigned ? Vec_IntEntryLast(vRes) : 0 ); else Vec_IntShrink( vRes, nRange ); diff --git a/src/base/wlc/wlcCom.c b/src/base/wlc/wlcCom.c index 5237f11d..2c504127 100644 --- a/src/base/wlc/wlcCom.c +++ b/src/base/wlc/wlcCom.c @@ -338,9 +338,9 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv ) Wlc_Ntk_t * pNtk = Wlc_AbcGetNtk(pAbc); Vec_Int_t * vBoxIds = NULL; Gia_Man_t * pNew = NULL; - int c, iOutput = -1, nOutputRange = 2, fGiaSimple = 0, fAddOutputs = 0, fMulti = 0, fVerbose = 0; + int c, iOutput = -1, nOutputRange = 2, fGiaSimple = 0, fAddOutputs = 0, fMulti = 0, fBooth = 0, fVerbose = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "ORcomvh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "ORcombvh" ) ) != EOF ) { switch ( c ) { @@ -375,6 +375,9 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'm': fMulti ^= 1; break; + case 'b': + fBooth ^= 1; + break; case 'v': fVerbose ^= 1; break; @@ -401,7 +404,7 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv ) return 0; } // transform - pNew = Wlc_NtkBitBlast( pNtk, vBoxIds, iOutput, nOutputRange, fGiaSimple, fAddOutputs ); + pNew = Wlc_NtkBitBlast( pNtk, vBoxIds, iOutput, nOutputRange, fGiaSimple, fAddOutputs, fBooth ); Vec_IntFreeP( &vBoxIds ); if ( pNew == NULL ) { @@ -411,13 +414,14 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv ) Abc_FrameUpdateGia( pAbc, pNew ); return 0; usage: - Abc_Print( -2, "usage: %%blast [-OR num] [-comvh]\n" ); + Abc_Print( -2, "usage: %%blast [-OR num] [-combvh]\n" ); Abc_Print( -2, "\t performs bit-blasting of the word-level design\n" ); Abc_Print( -2, "\t-O num : zero-based index of the first word-level PO to bit-blast [default = %d]\n", iOutput ); Abc_Print( -2, "\t-R num : the total number of word-level POs to bit-blast [default = %d]\n", nOutputRange ); Abc_Print( -2, "\t-c : toggle using AIG w/o const propagation and strashing [default = %s]\n", fGiaSimple? "yes": "no" ); Abc_Print( -2, "\t-o : toggle using additional POs on the word-level boundaries [default = %s]\n", fAddOutputs? "yes": "no" ); Abc_Print( -2, "\t-m : toggle creating boxes for all multipliers in the design [default = %s]\n", fMulti? "yes": "no" ); + Abc_Print( -2, "\t-b : toggle generating radix-4 Booth multipliers [default = %s]\n", fBooth? "yes": "no" ); Abc_Print( -2, "\t-v : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); return 1; diff --git a/src/base/wlc/wlcReadVer.c b/src/base/wlc/wlcReadVer.c index 3ff5cc6f..08dc8e98 100644 --- a/src/base/wlc/wlcReadVer.c +++ b/src/base/wlc/wlcReadVer.c @@ -1291,7 +1291,7 @@ void Io_ReadWordTest( char * pFileName ) return; Wlc_WriteVer( pNtk, "test.v", 0, 0 ); - pNew = Wlc_NtkBitBlast( pNtk, NULL, -1, 0, 0, 0 ); + pNew = Wlc_NtkBitBlast( pNtk, NULL, -1, 0, 0, 0, 0 ); Gia_AigerWrite( pNew, "test.aig", 0, 0 ); Gia_ManStop( pNew ); diff --git a/src/base/wlc/wlcSim.c b/src/base/wlc/wlcSim.c index 5fd83ca7..20ac8c61 100644 --- a/src/base/wlc/wlcSim.c +++ b/src/base/wlc/wlcSim.c @@ -129,7 +129,7 @@ Vec_Ptr_t * Wlc_NtkSimulate( Wlc_Ntk_t * p, Vec_Int_t * vNodes, int nWords, int { Gia_Obj_t * pObj; Vec_Ptr_t * vOne, * vRes; - Gia_Man_t * pGia = Wlc_NtkBitBlast( p, NULL, -1, 0, 0, 0 ); + Gia_Man_t * pGia = Wlc_NtkBitBlast( p, NULL, -1, 0, 0, 0, 0 ); Wlc_Obj_t * pWlcObj; int f, i, k, w, nBits, Counter = 0; // allocate simulation info for one timeframe diff --git a/src/proof/acec/acecPolyn.c b/src/proof/acec/acecPolyn.c index be601405..042e0c59 100644 --- a/src/proof/acec/acecPolyn.c +++ b/src/proof/acec/acecPolyn.c @@ -62,26 +62,6 @@ struct Pln_Man_t_ /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Pln_ManSimpleOrder( Gia_Man_t * p ) -{ - Vec_Int_t * vOrder; int Id; - vOrder = Vec_IntStart( Gia_ManObjNum(p) ); - Gia_ManForEachAndId( p, Id ) - Vec_IntWriteEntry( vOrder, Id, Id ); - return vOrder; -} - /**Function************************************************************* Synopsis [Computation manager.] @@ -108,7 +88,7 @@ Pln_Man_t * Pln_ManAlloc( Gia_Man_t * pGia, Vec_Int_t * vOrder ) p->vTempM[1] = Vec_IntAlloc( 100 ); p->vTempM[2] = Vec_IntAlloc( 100 ); p->vTempM[3] = Vec_IntAlloc( 100 ); - p->vOrder = vOrder ? vOrder : Vec_IntStartNatural( Gia_ManObjNum(pGia) ); + p->vOrder = vOrder ? Vec_IntDup(vOrder) : Vec_IntStartNatural( Gia_ManObjNum(pGia) ); assert( Vec_IntSize(p->vOrder) == Gia_ManObjNum(pGia) ); Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) ); // add 0-constant and 1-monomial @@ -131,36 +111,52 @@ void Pln_ManStop( Pln_Man_t * p ) Vec_IntFree( p->vTempM[1] ); Vec_IntFree( p->vTempM[2] ); Vec_IntFree( p->vTempM[3] ); - //Vec_IntFree( p->vOrder ); + Vec_IntFree( p->vOrder ); ABC_FREE( p ); } +int Pln_ManCompare3( int * pData0, int * pData1 ) +{ + if ( pData0[0] < pData1[0] ) return -1; + if ( pData0[0] > pData1[0] ) return 1; + if ( pData0[1] < pData1[1] ) return -1; + if ( pData0[1] > pData1[1] ) return 1; + return 0; +} void Pln_ManPrintFinal( Pln_Man_t * p, int fVerbose, int fVeryVerbose ) { Vec_Int_t * vArray; - int k, Entry, iMono, iConst, Count = 0; + int i, k, Entry, iMono, iConst; + // collect triples + Vec_Int_t * vPairs = Vec_IntAlloc( 100 ); Vec_IntForEachEntry( p->vCoefs, iConst, iMono ) { if ( iConst == 0 ) continue; - - Count++; - - if ( !fVerbose ) - continue; - - if ( Count > 25 ) + vArray = Hsh_VecReadEntry( p->pHashC, iConst ); + Vec_IntPush( vPairs, Vec_IntEntry(vArray, 0) ); + vArray = Hsh_VecReadEntry( p->pHashM, iMono ); + Vec_IntPush( vPairs, Vec_IntSize(vArray) ? Vec_IntEntry(vArray, 0) : 0 ); + Vec_IntPushTwo( vPairs, iConst, iMono ); + } + // sort triples + qsort( Vec_IntArray(vPairs), Vec_IntSize(vPairs)/4, 16, (int (*)(const void *, const void *))Pln_ManCompare3 ); + // print + if ( fVerbose ) + Vec_IntForEachEntryDouble( vPairs, iConst, iMono, i ) + { + if ( i % 4 == 0 ) continue; - + printf( "%-6d : ", i/4 ); vArray = Hsh_VecReadEntry( p->pHashC, iConst ); Vec_IntForEachEntry( vArray, Entry, k ) printf( "%s%d", Entry < 0 ? "-" : "+", (1 << (Abc_AbsInt(Entry)-1)) ); - vArray = Hsh_VecReadEntry( p->pHashM, iMono ); Vec_IntForEachEntry( vArray, Entry, k ) printf( " * %d", Entry ); printf( "\n" ); } - printf( "HashC = %d. HashM = %d. Total = %d. Used = %d.\n", Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, Count ); + printf( "HashC = %d. HashM = %d. Total = %d. Used = %d. ", Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, Vec_IntSize(vPairs)/4 ); + Vec_IntFree( vPairs ); } /**Function************************************************************* @@ -400,7 +396,7 @@ void Gia_PolynBuild( Gia_Man_t * pGia, Vec_Int_t * vOrder, int fSigned, int fVer else Vec_BitSetEntry( vPres, LevCur, 1 ); - if ( fVerbose ) + if ( fVeryVerbose ) printf( "Line%5d Iter%10d : Obj =%6d. Order =%6d. HashC =%6d. HashM =%10d. Total =%10d. Used =%10d.\n", Line++, Iter, LevCur, Vec_IntEntry(p->vOrder, LevCur), Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, p->nUsed ); } @@ -409,14 +405,37 @@ void Gia_PolynBuild( Gia_Man_t * pGia, Vec_Int_t * vOrder, int fSigned, int fVer Gia_PolynBuildOne( p, iMono ); //clk2 += Abc_Clock() - temp; } - Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); //Abc_PrintTime( 1, "Time2", clk2 ); Pln_ManPrintFinal( p, fVerbose, fVeryVerbose ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); Pln_ManStop( p ); Vec_BitFree( vPres ); } + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_PolynBuild2( Gia_Man_t * pGia, int fSigned, int fVerbose, int fVeryVerbose ) +{ + Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 ); // hash table for constants + Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 ); // hash table for monomials + Vec_Wec_t * vLit2Mono = Vec_WecStart( Gia_ManObjNum(pGia) * 2 ); + + Hsh_VecManStop( pHashC ); + Hsh_VecManStop( pHashM ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3