diff options
Diffstat (limited to 'src/proof/acec/acecCl.c')
| -rw-r--r-- | src/proof/acec/acecCl.c | 390 |
1 files changed, 390 insertions, 0 deletions
diff --git a/src/proof/acec/acecCl.c b/src/proof/acec/acecCl.c index 32be3b30..6185677b 100644 --- a/src/proof/acec/acecCl.c +++ b/src/proof/acec/acecCl.c @@ -45,6 +45,396 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ +void Acec_ManDerive_rec( Gia_Man_t * pNew, Gia_Man_t * p, int Node, Vec_Int_t * vMirrors ) +{ + Gia_Obj_t * pObj; + int Obj = Node; + if ( Vec_IntEntry(vMirrors, Node) >= 0 ) + Obj = Abc_Lit2Var( Vec_IntEntry(vMirrors, Node) ); + pObj = Gia_ManObj( p, Obj ); + if ( !~pObj->Value ) + { + assert( Gia_ObjIsAnd(pObj) ); + Acec_ManDerive_rec( pNew, p, Gia_ObjFaninId0(pObj, Obj), vMirrors ); + Acec_ManDerive_rec( pNew, p, Gia_ObjFaninId1(pObj, Obj), vMirrors ); + if ( Gia_ObjIsXor(pObj) ) + pObj->Value = Gia_ManAppendXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + else + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + } + // set the original node as well + if ( Obj != Node ) + Gia_ManObj(p, Node)->Value = Abc_LitNotCond( pObj->Value, Abc_LitIsCompl(Vec_IntEntry(vMirrors, Node)) ); +} +Gia_Man_t * Acec_ManDerive( Gia_Man_t * p, Vec_Int_t * vMirrors ) +{ + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i; + assert( p->pMuxes == NULL ); + Gia_ManFillValue( p ); + pNew = Gia_ManStart( Gia_ManObjNum(p) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + Gia_ManConst0(p)->Value = 0; + Gia_ManHashAlloc( pNew ); + Gia_ManForEachCi( p, pObj, i ) + pObj->Value = Gia_ManAppendCi(pNew); + Gia_ManForEachCo( p, pObj, i ) + Acec_ManDerive_rec( pNew, p, Gia_ObjFaninId0p(p, pObj), vMirrors ); + Gia_ManForEachCo( p, pObj, i ) + pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + Gia_ManHashStop( pNew ); + Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Acec_CollectXorTops( Gia_Man_t * p ) +{ + Vec_Int_t * vRootXorSet = Vec_IntAlloc( Gia_ManCoNum(p) ); + Gia_Obj_t * pObj, * pFan0, * pFan1, * pFan00, * pFan01, * pFan10, * pFan11; + int i, fXor0, fXor1, fFirstXor = 0; + Gia_ManForEachCoDriver( p, pObj, i ) + { + if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) + { + if ( fFirstXor ) + { + printf( "XORs do not form a continuous sequence\n" ); + Vec_IntFreeP( &vRootXorSet ); + break; + } + continue; + } + fFirstXor = 1; + fXor0 = Gia_ObjRecognizeExor(Gia_Regular(pFan0), &pFan00, &pFan01); + fXor1 = Gia_ObjRecognizeExor(Gia_Regular(pFan1), &pFan10, &pFan11); + if ( fXor0 == fXor1 ) + { + printf( "Both inputs of top level XOR have XOR/non-XOR\n" ); + Vec_IntFreeP( &vRootXorSet ); + break; + } + Vec_IntPush( vRootXorSet, Gia_ObjId(p, pObj) ); + Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan0)) : Gia_ObjId(p, Gia_Regular(pFan1)) ); + Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan10)) : Gia_ObjId(p, Gia_Regular(pFan00)) ); + Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan11)) : Gia_ObjId(p, Gia_Regular(pFan01)) ); + } + for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ ) + { + printf( "%2d : ", i ); + printf( "%4d <- ", Vec_IntEntry(vRootXorSet, 4*i) ); + printf( "%4d ", Vec_IntEntry(vRootXorSet, 4*i+1) ); + printf( "%4d ", Vec_IntEntry(vRootXorSet, 4*i+2) ); + printf( "%4d ", Vec_IntEntry(vRootXorSet, 4*i+3) ); + printf( "\n" ); + } + return vRootXorSet; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Acec_DetectLitPolarity( Gia_Man_t * p, int Node, int Leaf ) +{ + Gia_Obj_t * pNode; + int Lit0, Lit1; + if ( Node < Leaf ) + return -1; + if ( Node == Leaf ) + return Abc_Var2Lit(Node, 0); + pNode = Gia_ManObj( p, Node ); + Lit0 = Acec_DetectLitPolarity( p, Gia_ObjFaninId0(pNode, Node), Leaf ); + Lit1 = Acec_DetectLitPolarity( p, Gia_ObjFaninId1(pNode, Node), Leaf ); + Lit0 = Lit0 == -1 ? Lit0 : Abc_LitNotCond( Lit0, Gia_ObjFaninC0(pNode) ); + Lit1 = Lit1 == -1 ? Lit1 : Abc_LitNotCond( Lit1, Gia_ObjFaninC1(pNode) ); + if ( Lit0 == -1 && Lit1 == -1 ) + return -1; + assert( Lit0 != -1 || Lit1 != -1 ); + if ( Lit0 != -1 && Lit1 != -1 ) + { + assert( Lit0 == Lit1 ); + printf( "Problem for leaf %d\n", Leaf ); + return Lit0; + } + return Lit0 != -1 ? Lit0 : Lit1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Acec_DetectComputeSuppOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp, Vec_Int_t * vNods ) +{ + if ( Gia_ObjIsTravIdCurrent(p, pObj) ) + return; + Gia_ObjSetTravIdCurrent(p, pObj); + if ( pObj->fMark0 ) + { + Vec_IntPush( vSupp, Gia_ObjId(p, pObj) ); + return; + } + assert( Gia_ObjIsAnd(pObj) ); + Acec_DetectComputeSuppOne_rec( p, Gia_ObjFanin0(pObj), vSupp, vNods ); + Acec_DetectComputeSuppOne_rec( p, Gia_ObjFanin1(pObj), vSupp, vNods ); + Vec_IntPush( vNods, Gia_ObjId(p, pObj) ); +} +void Acec_DetectComputeSupports( Gia_Man_t * p, Vec_Int_t * vRootXorSet ) +{ + Vec_Int_t * vNods = Vec_IntAlloc( 100 ); + Vec_Int_t * vPols = Vec_IntAlloc( 100 ); + Vec_Int_t * vSupp = Vec_IntAlloc( 100 ); int i, k, Node, Pol; + for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ ) + { + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 1; + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+2) )->fMark0 = 1; + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+3) )->fMark0 = 1; + } + for ( i = 1; 4*i < Vec_IntSize(vRootXorSet); i++ ) + { + Vec_IntClear( vSupp ); + Gia_ManIncrementTravId( p ); + + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 0; + Acec_DetectComputeSuppOne_rec( p, Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) ), vSupp, vNods ); + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 1; + + Vec_IntSort( vSupp, 0 ); + + printf( "Out %4d : %4d \n", i, Vec_IntEntry(vRootXorSet, 4*i+1) ); + Vec_IntPrint( vSupp ); + + printf( "Cone:\n" ); + Vec_IntForEachEntry( vNods, Node, k ) + Gia_ObjPrint( p, Gia_ManObj(p, Node) ); + + + Vec_IntClear( vPols ); + Vec_IntForEachEntry( vSupp, Node, k ) + Vec_IntPush( vPols, Acec_DetectLitPolarity(p, Vec_IntEntry(vRootXorSet, 4*i+1), Node) ); + + Vec_IntForEachEntryTwo( vSupp, vPols, Node, Pol, k ) + printf( "%d(%d) ", Node, Abc_LitIsCompl(Pol) ); + + printf( "\n" ); + + Vec_IntPrint( vSupp ); + } + for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ ) + { + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 0; + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+2) )->fMark0 = 0; + Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+3) )->fMark0 = 0; + } + Vec_IntFree( vSupp ); + Vec_IntFree( vPols ); + Vec_IntFree( vNods ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Acec_DetectXorBuildNew( Gia_Man_t * p, Vec_Int_t * vRootXorSet ) +{ + Gia_Man_t * pNew; + int i, k, iOr1, iAnd1, iAnd2, pLits[3]; // carry, in1, in2 + Vec_Int_t * vMirrors = Vec_IntStart( Gia_ManObjNum(p) ); + for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ ) + { + pLits[0] = Acec_DetectLitPolarity( p, Vec_IntEntry(vRootXorSet, 4*i), Vec_IntEntry(vRootXorSet, 4*i+1) ); + // get polarity of two new ones + for ( k = 1; k < 3; k++ ) + pLits[k] = Acec_DetectLitPolarity( p, Vec_IntEntry(vRootXorSet, 4*i), Vec_IntEntry(vRootXorSet, 4*i+k+1) ); + // create the gate + iOr1 = Gia_ManAppendOr( p, pLits[1], pLits[2] ); + iAnd1 = Gia_ManAppendAnd( p, pLits[0], iOr1 ); + iAnd2 = Gia_ManAppendAnd( p, pLits[1], pLits[2] ); + pLits[0] = Gia_ManAppendOr( p, iAnd1, iAnd2 ); + Vec_IntWriteEntry( vMirrors, Vec_IntEntry(vRootXorSet, 4*i+1), pLits[0] ); + } + // remap the AIG using map + pNew = Acec_ManDerive( p, vMirrors ); + Vec_IntFree( vMirrors ); + return pNew; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Acec_DetectAdditional( Gia_Man_t * p, int fVerbose ) +{ + abctime clk = Abc_Clock(); + Gia_Man_t * pNew; + Vec_Int_t * vRootXorSet; +// Vec_Int_t * vXors, * vAdds = Ree_ManComputeCuts( p, &vXors, 0 ); + + //Ree_ManPrintAdders( vAdds, 1 ); +// printf( "Detected %d full-adders and %d half-adders. Found %d XOR-cuts. ", Ree_ManCountFadds(vAdds), Vec_IntSize(vAdds)/6-Ree_ManCountFadds(vAdds), Vec_IntSize(vXors)/4 ); +// Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + + clk = Abc_Clock(); + vRootXorSet = Acec_CollectXorTops( p ); + if ( vRootXorSet ) + { + Acec_DetectComputeSupports( p, vRootXorSet ); + + pNew = Acec_DetectXorBuildNew( p, vRootXorSet ); + Vec_IntFree( vRootXorSet ); + } + else + pNew = Gia_ManDup( p ); + + printf( "Detected %d top XORs. ", Vec_IntSize(vRootXorSet)/4 ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + +// Vec_IntFree( vXors ); +// Vec_IntFree( vAdds ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Acec_RewriteTop( Gia_Man_t * p, Acec_Box_t * pBox ) +{ + Vec_Int_t * vRes = Vec_IntAlloc( Gia_ManCoNum(p) + 1 ); + Vec_Int_t * vLevel; + int i, k, iStart, iLit, Driver, Count = 0; + // determine how much to shift + Driver = Gia_ObjFaninId0p( p, Gia_ManCo(p, 0) ); + Vec_WecForEachLevel( pBox->vRootLits, vLevel, iStart ) + if ( Abc_Lit2Var(Vec_IntEntry(vLevel,0)) == Driver ) + break; + assert( iStart < Gia_ManCoNum(p) ); + //Vec_WecPrintLits( pBox->vRootLits ); + Vec_WecForEachLevelStart( pBox->vRootLits, vLevel, i, iStart ) + { + int In[3] = {0}, Out[2]; + assert( Vec_IntSize(vLevel) > 0 ); + assert( Vec_IntSize(vLevel) <= 3 ); + if ( Vec_IntSize(vLevel) == 1 ) + { + Vec_IntPush( vRes, Vec_IntEntry(vLevel, 0) ); + continue; + } + Vec_IntForEachEntry( vLevel, iLit, k ) + In[k] = iLit; + Acec_InsertFadd( p, In, Out ); + Vec_IntPush( vRes, Out[0] ); + if ( i+1 < Vec_WecSize(pBox->vRootLits) ) + Vec_IntPush( Vec_WecEntry(pBox->vRootLits, i+1), Out[1] ); + else + Vec_IntPush( Vec_WecPushLevel(pBox->vRootLits), Out[1] ); + Count++; + } + assert( Vec_IntSize(vRes) >= Gia_ManCoNum(p) ); + Vec_IntShrink( vRes, Gia_ManCoNum(p) ); + printf( "Added %d adders for replace CLAs. ", Count ); + return vRes; +} +Gia_Man_t * Acec_RewriteReplace( Gia_Man_t * p, Vec_Int_t * vRes ) +{ + Gia_Man_t * pNew, * pTemp; + Gia_Obj_t * pObj; int i; + assert( Gia_ManCoNum(p) == Vec_IntSize(vRes) ); + // create new manager + pNew = Gia_ManStart( Gia_ManObjNum(p) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + Gia_ManFillValue( p ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachCi( p, pObj, i ) + pObj->Value = Gia_ManAppendCi(pNew); + Gia_ManForEachAnd( p, pObj, i ) + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( p, pObj, i ) + { + int iLit = Vec_IntEntry( vRes, i ); + Gia_Obj_t * pRepr = Gia_ManObj( p, Abc_Lit2Var(iLit) ); + pObj->Value = Gia_ManAppendCo( pNew, pRepr->Value ); + } + // set correct phase + Gia_ManSetPhase( p ); + Gia_ManSetPhase( pNew ); + Gia_ManForEachCo( pNew, pObj, i ) + if ( Gia_ObjPhase(pObj) != Gia_ObjPhase(Gia_ManCo(p, i)) ) + Gia_ObjFlipFaninC0( pObj ); + // remove dangling nodes + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} +Gia_Man_t * Acec_ManDecla( Gia_Man_t * pGia, int fBooth, int fVerbose ) +{ + abctime clk = Abc_Clock(); + Gia_Man_t * pNew = NULL; + Vec_Bit_t * vIgnore = fBooth ? Acec_BoothFindPPG(pGia) : NULL; + Acec_Box_t * pBox = Acec_DeriveBox( pGia, vIgnore, 0, 0, fVerbose ); + Vec_Int_t * vResult; + Vec_BitFreeP( &vIgnore ); + if ( pBox == NULL ) // cannot match + { + printf( "Cannot find arithmetic boxes.\n" ); + return Gia_ManDup( pGia ); + } + vResult = Acec_RewriteTop( pGia, pBox ); + Acec_BoxFreeP( &pBox ); + pNew = Acec_RewriteReplace( pGia, vResult ); + Vec_IntFree( vResult ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + return pNew; +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// |