diff options
Diffstat (limited to 'src/opt/sbd/sbdCut2.c')
-rw-r--r-- | src/opt/sbd/sbdCut2.c | 431 |
1 files changed, 431 insertions, 0 deletions
diff --git a/src/opt/sbd/sbdCut2.c b/src/opt/sbd/sbdCut2.c new file mode 100644 index 00000000..b4a8be74 --- /dev/null +++ b/src/opt/sbd/sbdCut2.c @@ -0,0 +1,431 @@ +/**CFile**************************************************************** + + FileName [sbdCut2.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [SAT-based optimization using internal don't-cares.] + + Synopsis [Cut computation.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: sbdCut2.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "sbdInt.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define SBD_MAX_CUTSIZE 10 +#define SBD_MAX_CUTNUM 501 + +#define SBD_CUT_NO_LEAF 0xF + +typedef struct Sbd_Cut_t_ Sbd_Cut_t; +struct Sbd_Cut_t_ +{ + word Sign; // signature + int iFunc; // functionality + int Cost; // cut cost + int CostLev; // cut cost + unsigned nTreeLeaves : 9; // tree leaves + unsigned nSlowLeaves : 9; // slow leaves + unsigned nTopLeaves : 10; // top leaves + unsigned nLeaves : 4; // leaf count + int pLeaves[SBD_MAX_CUTSIZE]; // leaves +}; + +struct Sbd_Srv_t_ +{ + int nLutSize; + int nCutSize; + int nCutNum; + int fVerbose; + Gia_Man_t * pGia; // user's AIG manager (will be modified by adding nodes) + Vec_Int_t * vMirrors; // mirrors for each node + Vec_Int_t * vLutLevs; // delays for each node + Vec_Int_t * vLevs; // levels for each node + Vec_Int_t * vRefs; // refs for each node + Sbd_Cut_t pCuts[SBD_MAX_CUTNUM]; // temporary cuts + Sbd_Cut_t * ppCuts[SBD_MAX_CUTNUM]; // temporary cut pointers + abctime clkStart; // starting time + Vec_Int_t * vCut0; // current cut + Vec_Int_t * vCut; // current cut + Vec_Int_t * vCutTop; // current cut + Vec_Int_t * vCutBot; // current cut +}; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Sbd_Srv_t * Sbd_ManCutServerStart( Gia_Man_t * pGia, Vec_Int_t * vMirrors, + Vec_Int_t * vLutLevs, Vec_Int_t * vLevs, Vec_Int_t * vRefs, + int nLutSize, int nCutSize, int nCutNum, int fVerbose ) +{ + Sbd_Srv_t * p; + assert( nLutSize <= nCutSize ); + assert( nCutSize < SBD_CUT_NO_LEAF ); + assert( nCutSize > 1 && nCutSize <= SBD_MAX_CUTSIZE ); + assert( nCutNum > 1 && nCutNum < SBD_MAX_CUTNUM ); + p = ABC_CALLOC( Sbd_Srv_t, 1 ); + p->clkStart = Abc_Clock(); + p->nLutSize = nLutSize; + p->nCutSize = nCutSize; + p->nCutNum = nCutNum; + p->fVerbose = fVerbose; + p->pGia = pGia; + p->vMirrors = vMirrors; + p->vLutLevs = vLutLevs; + p->vLevs = vLevs; + p->vRefs = vRefs; + p->vCut0 = Vec_IntAlloc( 100 ); + p->vCut = Vec_IntAlloc( 100 ); + p->vCutTop = Vec_IntAlloc( 100 ); + p->vCutBot = Vec_IntAlloc( 100 ); + return p; +} +void Sbd_ManCutServerStop( Sbd_Srv_t * p ) +{ + Vec_IntFree( p->vCut0 ); + Vec_IntFree( p->vCut ); + Vec_IntFree( p->vCutTop ); + Vec_IntFree( p->vCutBot ); + ABC_FREE( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sbd_ManCutIsTopo_rec( Gia_Man_t * p, Vec_Int_t * vMirrors, int iObj ) +{ + Gia_Obj_t * pObj; + int Ret0, Ret1; + if ( Vec_IntEntry(vMirrors, iObj) >= 0 ) + iObj = Abc_Lit2Var(Vec_IntEntry(vMirrors, iObj)); + if ( !iObj || Gia_ObjIsTravIdCurrentId(p, iObj) ) + return 1; + Gia_ObjSetTravIdCurrentId(p, iObj); + pObj = Gia_ManObj( p, iObj ); + if ( Gia_ObjIsCi(pObj) ) + return 0; + assert( Gia_ObjIsAnd(pObj) ); + Ret0 = Sbd_ManCutIsTopo_rec( p, vMirrors, Gia_ObjFaninId0(pObj, iObj) ); + Ret1 = Sbd_ManCutIsTopo_rec( p, vMirrors, Gia_ObjFaninId1(pObj, iObj) ); + return Ret0 && Ret1; +} +int Sbd_ManCutIsTopo( Gia_Man_t * p, Vec_Int_t * vMirrors, Vec_Int_t * vCut, int iObj ) +{ + int i, Entry, RetValue; + Gia_ManIncrementTravId( p ); + Vec_IntForEachEntry( vCut, Entry, i ) + Gia_ObjSetTravIdCurrentId( p, Entry ); + RetValue = Sbd_ManCutIsTopo_rec( p, vMirrors, iObj ); + if ( RetValue == 0 ) + printf( "Cut of node %d is not tological\n", iObj ); + assert( RetValue ); + return RetValue; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Sbd_ManCutExpandOne( Gia_Man_t * p, Vec_Int_t * vMirrors, Vec_Int_t * vLutLevs, Vec_Int_t * vCut, int iThis, int iObj ) +{ + int Lit0m, Lit1m, Fan0, Fan1, iPlace0, iPlace1; + int LutLev = Vec_IntEntry( vLutLevs, iObj ); + Gia_Obj_t * pObj = Gia_ManObj(p, iObj); + if ( Gia_ObjIsCi(pObj) ) + return 0; + assert( Gia_ObjIsAnd(pObj) ); + Lit0m = Vec_IntEntry( vMirrors, Gia_ObjFaninId0(pObj, iObj) ); + Lit1m = Vec_IntEntry( vMirrors, Gia_ObjFaninId1(pObj, iObj) ); + Fan0 = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, iObj); + Fan1 = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, iObj); + iPlace0 = Vec_IntFind( vCut, Fan0 ); + iPlace1 = Vec_IntFind( vCut, Fan1 ); + if ( iPlace0 == -1 && iPlace1 == -1 ) + return 0; + if ( Vec_IntEntry(vLutLevs, Fan0) > LutLev || Vec_IntEntry(vLutLevs, Fan1) > LutLev ) + return 0; + Vec_IntDrop( vCut, iThis ); + if ( iPlace0 == -1 && Fan0 ) + Vec_IntPushOrder( vCut, Fan0 ); + if ( iPlace1 == -1 && Fan1 ) + Vec_IntPushOrder( vCut, Fan1 ); + return 1; +} +void Vec_IntIsOrdered( Vec_Int_t * vCut ) +{ + int i, Prev, Entry; + Prev = Vec_IntEntry( vCut, 0 ); + Vec_IntForEachEntryStart( vCut, Entry, i, 1 ) + { + assert( Prev < Entry ); + Prev = Entry; + } +} +void Sbd_ManCutExpand( Gia_Man_t * p, Vec_Int_t * vMirrors, Vec_Int_t * vLutLevs, Vec_Int_t * vCut ) +{ + int i, Entry; + do + { + Vec_IntForEachEntry( vCut, Entry, i ) + if ( Sbd_ManCutExpandOne( p, vMirrors, vLutLevs, vCut, i, Entry ) ) + break; + } + while ( i < Vec_IntSize(vCut) ); +} +void Sbd_ManCutReload( Vec_Int_t * vMirrors, Vec_Int_t * vLutLevs, int LevStop, Vec_Int_t * vCut, Vec_Int_t * vCutTop, Vec_Int_t * vCutBot ) +{ + int i, Entry; + Vec_IntClear( vCutTop ); + Vec_IntClear( vCutBot ); + Vec_IntForEachEntry( vCut, Entry, i ) + { + assert( Entry ); + assert( Vec_IntEntry(vMirrors, Entry) == -1 ); + assert( Vec_IntEntry(vLutLevs, Entry) <= LevStop ); + if ( Vec_IntEntry(vLutLevs, Entry) == LevStop ) + Vec_IntPush( vCutTop, Entry ); + else + Vec_IntPush( vCutBot, Entry ); + } + Vec_IntIsOrdered( vCut ); +} +int Sbd_ManCutCollect_rec( Gia_Man_t * p, Vec_Int_t * vMirrors, int iObj, int LevStop, Vec_Int_t * vLutLevs, Vec_Int_t * vCut ) +{ + Gia_Obj_t * pObj; + int Ret0, Ret1; + if ( Vec_IntEntry(vMirrors, iObj) >= 0 ) + iObj = Abc_Lit2Var(Vec_IntEntry(vMirrors, iObj)); + if ( !iObj || Gia_ObjIsTravIdCurrentId(p, iObj) ) + return 1; + Gia_ObjSetTravIdCurrentId(p, iObj); + pObj = Gia_ManObj( p, iObj ); + if ( Gia_ObjIsCi(pObj) || Vec_IntEntry(vLutLevs, iObj) <= LevStop ) + { + Vec_IntPush( vCut, iObj ); + return Vec_IntEntry(vLutLevs, iObj) <= LevStop; + } + assert( Gia_ObjIsAnd(pObj) ); + Ret0 = Sbd_ManCutCollect_rec( p, vMirrors, Gia_ObjFaninId0(pObj, iObj), LevStop, vLutLevs, vCut ); + Ret1 = Sbd_ManCutCollect_rec( p, vMirrors, Gia_ObjFaninId1(pObj, iObj), LevStop, vLutLevs, vCut ); + return Ret0 && Ret1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sbd_ManCutReduceTop( Gia_Man_t * p, Vec_Int_t * vMirrors, int iObj, Vec_Int_t * vLutLevs, Vec_Int_t * vCut, Vec_Int_t * vCutTop, int nCutSize ) +{ + int i, Entry, Lit0m, Lit1m, Fan0, Fan1; + int LevStop = Vec_IntEntry(vLutLevs, iObj) - 2; + Vec_IntIsOrdered( vCut ); + Vec_IntForEachEntryReverse( vCutTop, Entry, i ) + { + Gia_Obj_t * pObj = Gia_ManObj( p, Entry ); + if ( Gia_ObjIsCi(pObj) ) + continue; + assert( Gia_ObjIsAnd(pObj) ); + assert( Vec_IntEntry(vLutLevs, Entry) == LevStop ); + Lit0m = Vec_IntEntry( vMirrors, Gia_ObjFaninId0(pObj, Entry) ); + Lit1m = Vec_IntEntry( vMirrors, Gia_ObjFaninId1(pObj, Entry) ); + Fan0 = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, Entry); + Fan1 = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, Entry); + if ( Vec_IntEntry(vLutLevs, Fan0) > LevStop || Vec_IntEntry(vLutLevs, Fan1) > LevStop ) + continue; + assert( Vec_IntEntry(vLutLevs, Fan0) <= LevStop ); + assert( Vec_IntEntry(vLutLevs, Fan1) <= LevStop ); + if ( Vec_IntEntry(vLutLevs, Fan0) == LevStop && Vec_IntEntry(vLutLevs, Fan1) == LevStop ) + continue; + Vec_IntRemove( vCut, Entry ); + if ( Fan0 ) Vec_IntPushUniqueOrder( vCut, Fan0 ); + if ( Fan1 ) Vec_IntPushUniqueOrder( vCut, Fan1 ); + //Sbd_ManCutIsTopo( p, vMirrors, vCut, iObj ); + return 1; + } + return 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sbd_ManCutServerFirst( Sbd_Srv_t * p, int iObj, int * pLeaves ) +{ + int RetValue, LevStop = Vec_IntEntry(p->vLutLevs, iObj) - 2; + + Vec_IntClear( p->vCut ); + Gia_ManIncrementTravId( p->pGia ); + RetValue = Sbd_ManCutCollect_rec( p->pGia, p->vMirrors, iObj, LevStop, p->vLutLevs, p->vCut ); + if ( RetValue == 0 ) // cannot build delay-improving cut + return -1; + // check if the current cut is good + Vec_IntSort( p->vCut, 0 ); +/* + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "%d ", Vec_IntSize(p->vCut) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } +*/ + // try to expand the cut + Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut ); + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "1=(%d,%d) ", Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) ); + //printf( "%d ", Vec_IntSize(p->vCut) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } + + // try to reduce the topmost + Vec_IntClear( p->vCut0 ); + Vec_IntAppend( p->vCut0, p->vCut ); + if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) ) + { + Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut ); + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + assert( Vec_IntSize(p->vCut) <= p->nCutSize ); + if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "%d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } + // try again + if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) ) + { + Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut ); + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + assert( Vec_IntSize(p->vCut) <= p->nCutSize ); + if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "* %d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } + // try again + if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) ) + { + Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut ); + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + assert( Vec_IntSize(p->vCut) <= p->nCutSize ); + if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "** %d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } + // try again + if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) ) + { + Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut ); + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + assert( Vec_IntSize(p->vCut) <= p->nCutSize ); + if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "*** %d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } + } + } + } + } + + // recompute the cut + Vec_IntClear( p->vCut ); + Gia_ManIncrementTravId( p->pGia ); + RetValue = Sbd_ManCutCollect_rec( p->pGia, p->vMirrors, iObj, LevStop-1, p->vLutLevs, p->vCut ); + if ( RetValue == 0 ) // cannot build delay-improving cut + return -1; + // check if the current cut is good + Vec_IntSort( p->vCut, 0 ); +/* + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "%d ", Vec_IntSize(p->vCut) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } +*/ + // try to expand the cut + Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut ); + Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot ); + if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 ) + { + //printf( "2=(%d,%d) ", Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) ); + //printf( "%d ", Vec_IntSize(p->vCut) ); + memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) ); + return Vec_IntSize(p->vCut); + } + + return -1; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + |