| /**CFile**************************************************************** |
| |
| FileName [acecCl.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [CEC for arithmetic circuits.] |
| |
| Synopsis [Core procedures.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: acecCl.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "acecInt.h" |
| #include "misc/vec/vecWec.h" |
| #include "misc/extra/extra.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| 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 /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
