From 22d9b1d38b27a6a4c4f4b3b8f489704eed943351 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 16 Jul 2020 20:33:03 -0700 Subject: Experiment with structural similarity. --- src/aig/gia/gia.h | 3 ++ src/aig/gia/giaDfs.c | 28 ++++++++++++++++ src/aig/gia/giaIso3.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/giaUtil.c | 22 ++++++++++++ 4 files changed, 145 insertions(+) (limited to 'src/aig') diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 2458b152..7f6bbea6 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -570,6 +570,7 @@ static inline int Gia_ObjPhaseRealLit( Gia_Man_t * p, int iLit ) { static inline int Gia_ObjLevelId( Gia_Man_t * p, int Id ) { return Vec_IntGetEntry(p->vLevels, Id); } static inline int Gia_ObjLevel( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Gia_ObjLevelId( p, Gia_ObjId(p,pObj) ); } +static inline void Gia_ObjUpdateLevelId( Gia_Man_t * p, int Id, int l ) { Vec_IntSetEntry(p->vLevels, Id, Abc_MaxInt(Vec_IntEntry(p->vLevels, Id), l)); } static inline void Gia_ObjSetLevelId( Gia_Man_t * p, int Id, int l ) { Vec_IntSetEntry(p->vLevels, Id, l); } static inline void Gia_ObjSetLevel( Gia_Man_t * p, Gia_Obj_t * pObj, int l ) { Gia_ObjSetLevelId( p, Gia_ObjId(p,pObj), l ); } static inline void Gia_ObjSetCoLevel( Gia_Man_t * p, Gia_Obj_t * pObj ) { assert( Gia_ObjIsCo(pObj) ); Gia_ObjSetLevel( p, pObj, Gia_ObjLevel(p,Gia_ObjFanin0(pObj)) ); } @@ -1264,6 +1265,7 @@ extern Vec_Int_t * Gia_ManCollectNodesCis( Gia_Man_t * p, int * pNodes, extern int Gia_ManSuppSize( Gia_Man_t * p, int * pNodes, int nNodes ); extern int Gia_ManConeSize( Gia_Man_t * p, int * pNodes, int nNodes ); extern Vec_Vec_t * Gia_ManLevelize( Gia_Man_t * p ); +extern Vec_Wec_t * Gia_ManLevelizeR( Gia_Man_t * p ); extern Vec_Int_t * Gia_ManOrderReverse( Gia_Man_t * p ); extern void Gia_ManCollectTfi( Gia_Man_t * p, Vec_Int_t * vRoots, Vec_Int_t * vNodes ); extern void Gia_ManCollectTfo( Gia_Man_t * p, Vec_Int_t * vRoots, Vec_Int_t * vNodes ); @@ -1670,6 +1672,7 @@ extern void Gia_ManSetPhase1( Gia_Man_t * p ); extern void Gia_ManCleanPhase( Gia_Man_t * p ); extern int Gia_ManCheckCoPhase( Gia_Man_t * p ); extern int Gia_ManLevelNum( Gia_Man_t * p ); +extern int Gia_ManLevelRNum( Gia_Man_t * p ); extern Vec_Int_t * Gia_ManGetCiLevels( Gia_Man_t * p ); extern int Gia_ManSetLevels( Gia_Man_t * p, Vec_Int_t * vCiLevels ); extern Vec_Int_t * Gia_ManReverseLevel( Gia_Man_t * p ); diff --git a/src/aig/gia/giaDfs.c b/src/aig/gia/giaDfs.c index 5cfe3b44..7ed59b9a 100644 --- a/src/aig/gia/giaDfs.c +++ b/src/aig/gia/giaDfs.c @@ -416,6 +416,34 @@ Vec_Vec_t * Gia_ManLevelize( Gia_Man_t * p ) return vLevels; } +/**Function************************************************************* + + Synopsis [Levelizes the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Wec_t * Gia_ManLevelizeR( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + Vec_Wec_t * vLevels; + int nLevels, Level, i; + nLevels = Gia_ManLevelRNum( p ); + vLevels = Vec_WecStart( nLevels + 1 ); + Gia_ManForEachObj( p, pObj, i ) + { + if ( i == 0 || (!Gia_ObjIsCo(pObj) && !Gia_ObjLevel(p, pObj)) ) + continue; + Level = Gia_ObjLevel( p, pObj ); + assert( Level <= nLevels ); + Vec_WecPush( vLevels, Level, i ); + } + return vLevels; +} /**Function************************************************************* Synopsis [Computes reverse topological order.] diff --git a/src/aig/gia/giaIso3.c b/src/aig/gia/giaIso3.c index a88a0569..a151033a 100644 --- a/src/aig/gia/giaIso3.c +++ b/src/aig/gia/giaIso3.c @@ -158,6 +158,98 @@ void Gia_Iso3Test( Gia_Man_t * p ) Vec_IntFreeP( &vSign ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Wec_t * Gia_Iso4Gia( Gia_Man_t * p ) +{ + Vec_Wec_t * vLevs = Gia_ManLevelizeR( p ); + Vec_Int_t * vLevel; int l; + Abc_Random( 1 ); + Vec_WecForEachLevel( vLevs, vLevel, l ) + { + Gia_Obj_t * pObj; int i; + int RandC[2] = { Abc_Random(0), Abc_Random(0) }; + if ( l == 0 ) + { + Gia_ManForEachObjVec( vLevel, p, pObj, i ) + { + Gia_Obj_t * pfanin = Gia_ObjFanin0(pObj); + assert( Gia_ObjIsCo(pObj) ); + pObj->Value = Abc_Random(0); + Gia_ObjFanin0(pObj)->Value += pObj->Value + RandC[Gia_ObjFaninC0(pObj)]; + } + } + else + { + Gia_ManForEachObjVec( vLevel, p, pObj, i ) if ( Gia_ObjIsAnd(pObj) ) + { + Gia_ObjFanin0(pObj)->Value += pObj->Value + RandC[Gia_ObjFaninC0(pObj)]; + Gia_ObjFanin1(pObj)->Value += pObj->Value + RandC[Gia_ObjFaninC1(pObj)]; + } + } + } + return vLevs; +} +void Gia_Iso4Test( Gia_Man_t * p ) +{ + Vec_Wec_t * vLevs = Gia_Iso4Gia( p ); + Vec_Int_t * vLevel; int l; + Vec_WecForEachLevel( vLevs, vLevel, l ) + { + Gia_Obj_t * pObj; int i; + printf( "Level %d\n", l ); + Gia_ManForEachObjVec( vLevel, p, pObj, i ) + printf( "Obj = %5d. Value = %08x.\n", Gia_ObjId(p, pObj), pObj->Value ); + } + Vec_WecFree( vLevs ); +} +Vec_Int_t * Gia_IsoCollectData( Gia_Man_t * p, Vec_Int_t * vObjs ) +{ + Gia_Obj_t * pObj; int i; + Vec_Int_t * vData = Vec_IntAlloc( Vec_IntSize(vObjs) ); + Gia_ManForEachObjVec( vObjs, p, pObj, i ) + Vec_IntPush( vData, pObj->Value ); + return vData; +} +void Gia_IsoCompareVecs( Gia_Man_t * pGia0, Vec_Wec_t * vLevs0, Gia_Man_t * pGia1, Vec_Wec_t * vLevs1 ) +{ + int i, Common, nLevels = Abc_MinInt( Vec_WecSize(vLevs0), Vec_WecSize(vLevs1) ); + Gia_ManPrintStats( pGia0, NULL ); + Gia_ManPrintStats( pGia1, NULL ); + printf( "Printing %d shared levels:\n", nLevels ); + for ( i = 0; i < nLevels; i++ ) + { + Vec_Int_t * vLev0 = Vec_WecEntry(vLevs0, i); + Vec_Int_t * vLev1 = Vec_WecEntry(vLevs1, i); + Vec_Int_t * vData0 = Gia_IsoCollectData( pGia0, vLev0 ); + Vec_Int_t * vData1 = Gia_IsoCollectData( pGia1, vLev1 ); + Vec_IntSort( vData0, 0 ); + Vec_IntSort( vData1, 0 ); + Common = Vec_IntTwoCountCommon( vData0, vData1 ); + printf( "Level = %3d. One = %6d. Two = %6d. Common = %6d.\n", + i, Vec_IntSize(vData0)-Common, Vec_IntSize(vData1)-Common, Common ); + Vec_IntFree( vData0 ); + Vec_IntFree( vData1 ); + } +} +void Gia_Iso4TestTwo( Gia_Man_t * pGia0, Gia_Man_t * pGia1 ) +{ + Vec_Wec_t * vLevs0 = Gia_Iso4Gia( pGia0 ); + Vec_Wec_t * vLevs1 = Gia_Iso4Gia( pGia1 ); + Gia_IsoCompareVecs( pGia0, vLevs0, pGia1, vLevs1 ); + Vec_WecFree( vLevs0 ); + Vec_WecFree( vLevs1 ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c index 007faeca..2e1830c5 100644 --- a/src/aig/gia/giaUtil.c +++ b/src/aig/gia/giaUtil.c @@ -522,6 +522,28 @@ int Gia_ManLevelNum( Gia_Man_t * p ) } return p->nLevels; } +int Gia_ManLevelRNum( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + int i; + Gia_ManCleanLevels( p, Gia_ManObjNum(p) ); + p->nLevels = 0; + Gia_ManForEachObjReverse( p, pObj, i ) + { + if ( !p->fGiaSimple && Gia_ObjIsBuf(pObj) ) + Gia_ObjUpdateLevelId( p, Gia_ObjFaninId0(pObj, i), Gia_ObjLevel(p, pObj) ); + else if ( Gia_ObjIsAnd(pObj) ) + { + Gia_ObjUpdateLevelId( p, Gia_ObjFaninId0(pObj, i), 1+Gia_ObjLevel(p, pObj) ); + Gia_ObjUpdateLevelId( p, Gia_ObjFaninId1(pObj, i), 1+Gia_ObjLevel(p, pObj) ); + } + else if ( Gia_ObjIsCo(pObj) ) + Gia_ObjUpdateLevelId( p, Gia_ObjFaninId0(pObj, i), 1 ); + else + p->nLevels = Abc_MaxInt( p->nLevels, Gia_ObjLevel(p, pObj) ); + } + return p->nLevels; +} float Gia_ManLevelAve( Gia_Man_t * p ) { Gia_Obj_t * pObj; -- cgit v1.2.3