From c921058019c22ca917fb63f1139a46cb9f766ae2 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 4 Jul 2012 14:52:16 -0700 Subject: Added static fanout to GIA package. --- src/aig/gia/gia.h | 14 ++++++ src/aig/gia/giaFanout.c | 128 ++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/giaMan.c | 1 + 3 files changed, 143 insertions(+) (limited to 'src/aig') diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 606a4540..245d7d5d 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -126,6 +126,8 @@ struct Gia_Man_t_ int nTerStates; // the total number of ternary states int * pFanData; // the database to store fanout information int nFansAlloc; // the size of fanout representation + Vec_Int_t * vFanoutNums; // static fanout + Vec_Int_t * vFanout; // static fanout int * pMapping; // mapping for each node Vec_Int_t * vLutConfigs; // LUT configurations Abc_Cex_t * pCexComb; // combinational counter-example @@ -624,6 +626,16 @@ static inline void Gia_ClassUndoPair( Gia_Man_t * p, int i ) { a for ( assert(Gia_ObjIsHead(p, i)), iObj = Gia_ObjNext(p, i); iObj; iObj = Gia_ObjNext(p, iObj) ) +static inline int Gia_ObjFoffset( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Vec_IntEntry( p->vFanout, Gia_ObjId(p, pObj) ); } +static inline int Gia_ObjFanoutNum( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Vec_IntEntry( p->vFanoutNums, Gia_ObjId(p, pObj) ); } +static inline int Gia_ObjFanoutId( Gia_Man_t * p, Gia_Obj_t * pObj, int i ){ return Vec_IntEntry( p->vFanout, Gia_ObjFoffset(p, pObj) + i ); } +static inline Gia_Obj_t * Gia_ObjFanout0( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Gia_ManObj( p, Gia_ObjFanoutId(p, pObj, 0) ); } +static inline Gia_Obj_t * Gia_ObjFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i ) { return Gia_ManObj( p, Gia_ObjFanoutId(p, pObj, i) ); } +static inline void Gia_ObjSetFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i, Gia_Obj_t * pFan ) { Vec_IntWriteEntry( p->vFanout, Gia_ObjFoffset(p, pObj) + i, Gia_ObjId(p, pFan) ); } + +#define Gia_ObjForEachFanoutStatic( p, pObj, pFanout, i ) \ + for ( i = 0; (i < Gia_ObjFanoutNum(p, pObj)) && (((pFanout) = Gia_ObjFanout(p, pObj, i)), 1); i++ ) + static inline int Gia_ObjIsLut( Gia_Man_t * p, int Id ) { return p->pMapping[Id] != 0; } static inline int Gia_ObjLutSize( Gia_Man_t * p, int Id ) { return p->pMapping[p->pMapping[Id]]; } static inline int * Gia_ObjLutFanins( Gia_Man_t * p, int Id ) { return p->pMapping + p->pMapping[Id] + 1; } @@ -787,6 +799,8 @@ extern void Gia_ObjAddFanout( Gia_Man_t * p, Gia_Obj_t * pObj, Gi extern void Gia_ObjRemoveFanout( Gia_Man_t * p, Gia_Obj_t * pObj, Gia_Obj_t * pFanout ); extern void Gia_ManFanoutStart( Gia_Man_t * p ); extern void Gia_ManFanoutStop( Gia_Man_t * p ); +extern void Gia_ManStaticFanoutStart( Gia_Man_t * p ); +extern void Gia_ManStaticFanoutStop( Gia_Man_t * p ); /*=== giaForce.c =========================================================*/ extern void For_ManExperiment( Gia_Man_t * pGia, int nIters, int fClustered, int fVerbose ); /*=== giaFrames.c =========================================================*/ diff --git a/src/aig/gia/giaFanout.c b/src/aig/gia/giaFanout.c index 412594ad..62053fec 100644 --- a/src/aig/gia/giaFanout.c +++ b/src/aig/gia/giaFanout.c @@ -41,6 +41,7 @@ static inline int * Gia_FanoutNext( int * pData, int iFan ) { return pData + 5 // these two procedures are only here for the use inside the iterator static inline int Gia_ObjFanout0Int( Gia_Man_t * p, int ObjId ) { assert(ObjId < p->nFansAlloc); return p->pFanData[5*ObjId]; } static inline int Gia_ObjFanoutNext( Gia_Man_t * p, int iFan ) { assert(iFan/2 < p->nFansAlloc); return p->pFanData[5*(iFan >> 1) + 3 + (iFan & 1)]; } + // iterator over the fanouts #define Gia_ObjForEachFanout( p, pObj, pFanout, iFan, i ) \ for ( assert(p->pFanData), i = 0; (i < (int)(pObj)->nRefs) && \ @@ -193,6 +194,133 @@ void Gia_ObjRemoveFanout( Gia_Man_t * p, Gia_Obj_t * pObj, Gia_Obj_t * pFanout ) *pNextC = 0; } + + + +/**Function************************************************************* + + Synopsis [Compute the map of all edges.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManStartFanoutMap( Gia_Man_t * p, Vec_Int_t * vFanoutNums ) +{ + Vec_Int_t * vEdgeMap; + Gia_Obj_t * pObj; + int i, iOffset; + iOffset = Gia_ManObjNum(p); + vEdgeMap = Vec_IntStart( iOffset + 2 * Gia_ManAndNum(p) + Gia_ManCoNum(p) ); + Gia_ManForEachObj( p, pObj, i ) + { + Vec_IntWriteEntry( vEdgeMap, i, iOffset ); + iOffset += Vec_IntEntry( vFanoutNums, Gia_ObjId(p, pObj) ); + } + assert( iOffset <= Vec_IntSize(vEdgeMap) ); + return vEdgeMap; +} + +/**Function************************************************************* + + Synopsis [Allocates static fanout.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManStaticFanoutStart( Gia_Man_t * p ) +{ + Vec_Int_t * vCounts; + int * pRefsOld; + Gia_Obj_t * pObj, * pFanin; + int i, iFanout; + assert( p->vFanoutNums == NULL ); + assert( p->vFanout == NULL ); + // recompute reference counters + pRefsOld = p->pRefs; p->pRefs = NULL; + Gia_ManCreateRefs(p); + p->vFanoutNums = Vec_IntAllocArray( p->pRefs, Gia_ManObjNum(p) ); + p->pRefs = pRefsOld; + // start the fanout maps + p->vFanout = Gia_ManStartFanoutMap( p, p->vFanoutNums ); + // incrementally add fanouts + vCounts = Vec_IntStart( Gia_ManObjNum(p) ); + Gia_ManForEachObj( p, pObj, i ) + { + if ( Gia_ObjIsAnd(pObj) || Gia_ObjIsCo(pObj) ) + { + pFanin = Gia_ObjFanin0(pObj); + iFanout = Vec_IntEntry( vCounts, Gia_ObjId(p, pFanin) ); + Gia_ObjSetFanout( p, pFanin, iFanout, pObj ); + Vec_IntAddToEntry( vCounts, Gia_ObjId(p, pFanin), 1 ); + } + if ( Gia_ObjIsAnd(pObj) ) + { + + pFanin = Gia_ObjFanin1(pObj); + iFanout = Vec_IntEntry( vCounts, Gia_ObjId(p, pFanin) ); + Gia_ObjSetFanout( p, pFanin, iFanout, pObj ); + Vec_IntAddToEntry( vCounts, Gia_ObjId(p, pFanin), 1 ); + } + } + // double-check the current number of fanouts added + Gia_ManForEachObj( p, pObj, i ) + assert( Vec_IntEntry(vCounts, i) == Gia_ObjFanoutNum(p, pObj) ); + Vec_IntFree( vCounts ); +} + +/**Function************************************************************* + + Synopsis [Deallocates static fanout.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManStaticFanoutStop( Gia_Man_t * p ) +{ + Vec_IntFreeP( &p->vFanoutNums ); + Vec_IntFreeP( &p->vFanout ); +} + + +/**Function************************************************************* + + Synopsis [Tests static fanout.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManStaticFanoutTest( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj, * pFanout; + int i, k; + Gia_ManStaticFanoutStart( p ); + Gia_ManForEachObj( p, pObj, i ) + { + Gia_ObjPrint( p, pObj ); + printf( " Fanouts : " ); + Gia_ObjForEachFanoutStatic( p, pObj, pFanout, k ) + printf( "%5d ", Gia_ObjId(p, pFanout) ); + printf( "\n" ); + } + Gia_ManStaticFanoutStop( p ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index 979bbe38..c116f5e7 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -70,6 +70,7 @@ Gia_Man_t * Gia_ManStart( int nObjsMax ) ***********************************************************************/ void Gia_ManStop( Gia_Man_t * p ) { + Gia_ManStaticFanoutStop( p ); Tim_ManStopP( (Tim_Man_t **)&p->pManTime ); assert( p->pManTime == NULL ); Vec_PtrFreeFree( p->vNamesIn ); -- cgit v1.2.3