| /**CFile**************************************************************** |
| |
| FileName [giaMuxes.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Scalable AIG package.] |
| |
| Synopsis [Multiplexer profiling algorithm.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: giaMuxes.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "gia.h" |
| #include "misc/util/utilNam.h" |
| #include "misc/vec/vecWec.h" |
| #include "misc/vec/vecHsh.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Counts XORs and MUXes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_ManCountMuxXor( Gia_Man_t * p, int * pnMuxes, int * pnXors ) |
| { |
| Gia_Obj_t * pObj, * pFan0, * pFan1; int i; |
| *pnMuxes = *pnXors = 0; |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| if ( !Gia_ObjIsMuxType(pObj) ) |
| continue; |
| if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) |
| (*pnXors)++; |
| else |
| (*pnMuxes)++; |
| } |
| } |
| void Gia_ManPrintMuxStats( Gia_Man_t * p ) |
| { |
| int nAnds, nMuxes, nXors, nTotal; |
| if ( p->pMuxes ) |
| { |
| nAnds = Gia_ManAndNotBufNum(p)-Gia_ManXorNum(p)-Gia_ManMuxNum(p); |
| nXors = Gia_ManXorNum(p); |
| nMuxes = Gia_ManMuxNum(p); |
| nTotal = nAnds + 3*nXors + 3*nMuxes; |
| } |
| else |
| { |
| Gia_ManCountMuxXor( p, &nMuxes, &nXors ); |
| nAnds = Gia_ManAndNotBufNum(p) - 3*nMuxes - 3*nXors; |
| nTotal = Gia_ManAndNotBufNum(p); |
| } |
| Abc_Print( 1, "stats: " ); |
| Abc_Print( 1, "xor =%8d %6.2f %% ", nXors, 300.0*nXors/nTotal ); |
| Abc_Print( 1, "mux =%8d %6.2f %% ", nMuxes, 300.0*nMuxes/nTotal ); |
| Abc_Print( 1, "and =%8d %6.2f %% ", nAnds, 100.0*nAnds/nTotal ); |
| Abc_Print( 1, "obj =%8d ", Gia_ManAndNotBufNum(p) ); |
| fflush( stdout ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives GIA with MUXes.] |
| |
| Description [Create MUX if the sum of fanin references does not exceed limit.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Gia_Man_t * Gia_ManDupMuxes( Gia_Man_t * p, int Limit ) |
| { |
| Gia_Man_t * pNew, * pTemp; |
| Gia_Obj_t * pObj, * pFan0, * pFan1, * pFanC, * pSiblNew, * pObjNew; |
| int i; |
| assert( p->pMuxes == NULL ); |
| assert( Limit >= 0 ); // allows to create AIG with XORs without MUXes |
| ABC_FREE( p->pRefs ); |
| Gia_ManCreateRefs( p ); |
| // start the new manager |
| pNew = Gia_ManStart( Gia_ManObjNum(p) ); |
| pNew->pName = Abc_UtilStrsav( p->pName ); |
| pNew->pSpec = Abc_UtilStrsav( p->pSpec ); |
| pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc ); |
| if ( Gia_ManHasChoices(p) ) |
| pNew->pSibls = ABC_CALLOC( int, pNew->nObjsAlloc ); |
| Gia_ManConst0(p)->Value = 0; |
| Gia_ManHashStart( pNew ); |
| Gia_ManForEachObj1( p, pObj, i ) |
| { |
| if ( Gia_ObjIsCi(pObj) ) |
| pObj->Value = Gia_ManAppendCi( pNew ); |
| else if ( Gia_ObjIsCo(pObj) ) |
| pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); |
| else if ( Gia_ObjIsBuf(pObj) ) |
| pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) ); |
| else if ( !Gia_ObjIsMuxType(pObj) || Gia_ObjSibl(p, Gia_ObjFaninId0(pObj, i)) || Gia_ObjSibl(p, Gia_ObjFaninId1(pObj, i)) ) |
| pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); |
| else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) |
| pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)) ); |
| else if ( Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) + Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) > Limit ) |
| pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); |
| else |
| { |
| pFanC = Gia_ObjRecognizeMux( pObj, &pFan1, &pFan0 ); |
| pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFanC)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)) ); |
| } |
| if ( !Gia_ObjSibl(p, i) ) |
| continue; |
| pObjNew = Gia_ManObj( pNew, Abc_Lit2Var(pObj->Value) ); |
| pSiblNew = Gia_ManObj( pNew, Abc_Lit2Var(Gia_ObjSiblObj(p, i)->Value) ); |
| if ( Gia_ObjIsAnd(pObjNew) && Gia_ObjIsAnd(pSiblNew) && Gia_ObjId(pNew, pObjNew) > Gia_ObjId(pNew, pSiblNew) ) |
| pNew->pSibls[Gia_ObjId(pNew, pObjNew)] = Gia_ObjId(pNew, pSiblNew); |
| } |
| Gia_ManHashStop( pNew ); |
| Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); |
| // perform cleanup |
| pNew = Gia_ManCleanup( pTemp = pNew ); |
| Gia_ManStop( pTemp ); |
| return pNew; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives GIA without MUXes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Gia_Man_t * Gia_ManDupNoMuxes( Gia_Man_t * p ) |
| { |
| Gia_Man_t * pNew, * pTemp; |
| Gia_Obj_t * pObj; |
| int i; |
| assert( p->pMuxes != NULL ); |
| // start the new manager |
| pNew = Gia_ManStart( 5000 ); |
| pNew->pName = Abc_UtilStrsav( p->pName ); |
| pNew->pSpec = Abc_UtilStrsav( p->pSpec ); |
| Gia_ManConst0(p)->Value = 0; |
| Gia_ManHashStart( pNew ); |
| Gia_ManForEachObj1( p, pObj, i ) |
| { |
| if ( Gia_ObjIsCi(pObj) ) |
| pObj->Value = Gia_ManAppendCi( pNew ); |
| else if ( Gia_ObjIsCo(pObj) ) |
| pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); |
| else if ( Gia_ObjIsBuf(pObj) ) |
| pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) ); |
| else if ( Gia_ObjIsMuxId(p, i) ) |
| pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) ); |
| else if ( Gia_ObjIsXor(pObj) ) |
| pObj->Value = Gia_ManHashXor( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); |
| else |
| pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); |
| } |
| Gia_ManHashStop( pNew ); |
| Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); |
| // perform cleanup |
| pNew = Gia_ManCleanup( pTemp = pNew ); |
| Gia_ManStop( pTemp ); |
| return pNew; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Test these procedures.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Gia_Man_t * Gia_ManDupMuxesTest( Gia_Man_t * p ) |
| { |
| Gia_Man_t * pNew, * pNew2; |
| pNew = Gia_ManDupMuxes( p, 2 ); |
| pNew2 = Gia_ManDupNoMuxes( pNew ); |
| Gia_ManPrintStats( p, NULL ); |
| Gia_ManPrintStats( pNew, NULL ); |
| Gia_ManPrintStats( pNew2, NULL ); |
| Gia_ManStop( pNew ); |
| // Gia_ManStop( pNew2 ); |
| return pNew2; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the size of MUX structure.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Gia_MuxRef_rec( Gia_Man_t * p, int iObj ) |
| { |
| Gia_Obj_t * pObj; |
| if ( !Gia_ObjIsMuxId(p, iObj) ) |
| return 0; |
| pObj = Gia_ManObj( p, iObj ); |
| if ( Gia_ObjRefInc(p, pObj) ) |
| return 0; |
| return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) + |
| Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) + |
| Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1; |
| } |
| int Gia_MuxRef( Gia_Man_t * p, int iObj ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, iObj ); |
| assert( Gia_ObjIsMuxId(p, iObj) ); |
| return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) + |
| Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) + |
| Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1; |
| } |
| int Gia_MuxDeref_rec( Gia_Man_t * p, int iObj ) |
| { |
| Gia_Obj_t * pObj; |
| if ( !Gia_ObjIsMuxId(p, iObj) ) |
| return 0; |
| pObj = Gia_ManObj( p, iObj ); |
| if ( Gia_ObjRefDec(p, pObj) ) |
| return 0; |
| return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) + |
| Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) + |
| Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1; |
| } |
| int Gia_MuxDeref( Gia_Man_t * p, int iObj ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, iObj ); |
| assert( Gia_ObjIsMuxId(p, iObj) ); |
| return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) + |
| Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) + |
| Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1; |
| } |
| int Gia_MuxMffcSize( Gia_Man_t * p, int iObj ) |
| { |
| int Count1, Count2; |
| if ( !Gia_ObjIsMuxId(p, iObj) ) |
| return 0; |
| Count1 = Gia_MuxDeref( p, iObj ); |
| Count2 = Gia_MuxRef( p, iObj ); |
| assert( Count1 == Count2 ); |
| return Count1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_MuxStructPrint_rec( Gia_Man_t * p, int iObj, int fFirst ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, iObj ); |
| int iCtrl; |
| if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) ) |
| { |
| // printf( "%d", iObj ); |
| printf( "<%02d>", Gia_ObjLevelId(p, iObj) ); |
| return; |
| } |
| iCtrl = Gia_ObjFaninId2p(p, pObj); |
| printf( " [(" ); |
| if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 ) |
| Gia_MuxStructPrint_rec( p, iCtrl, 0 ); |
| else |
| { |
| printf( "%d", iCtrl ); |
| printf( "<%d>", Gia_ObjLevelId(p, iCtrl) ); |
| } |
| printf( ")" ); |
| if ( Gia_ObjFaninC2(p, pObj) ) |
| { |
| Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 ); |
| printf( "|" ); |
| Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 ); |
| printf( "]" ); |
| } |
| else |
| { |
| Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 ); |
| printf( "|" ); |
| Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 ); |
| printf( "]" ); |
| } |
| } |
| void Gia_MuxStructPrint( Gia_Man_t * p, int iObj ) |
| { |
| int Count1, Count2; |
| assert( Gia_ObjIsMuxId(p, iObj) ); |
| Count1 = Gia_MuxDeref( p, iObj ); |
| Gia_MuxStructPrint_rec( p, iObj, 1 ); |
| Count2 = Gia_MuxRef( p, iObj ); |
| assert( Count1 == Count2 ); |
| printf( "\n" ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_MuxStructDump_rec( Gia_Man_t * p, int iObj, int fFirst, Vec_Str_t * vStr, int nDigitsId ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, iObj ); |
| int iCtrl; |
| if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) ) |
| return; |
| iCtrl = Gia_ObjFaninId2p(p, pObj); |
| Vec_StrPush( vStr, '[' ); |
| Vec_StrPush( vStr, '(' ); |
| if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 ) |
| Gia_MuxStructDump_rec( p, iCtrl, 0, vStr, nDigitsId ); |
| else |
| Vec_StrPrintNumStar( vStr, iCtrl, nDigitsId ); |
| Vec_StrPush( vStr, ')' ); |
| if ( Gia_ObjFaninC2(p, pObj) ) |
| { |
| Gia_MuxStructDump_rec( p, Gia_ObjFaninId0p(p, pObj), 0, vStr, nDigitsId ); |
| Vec_StrPush( vStr, '|' ); |
| Gia_MuxStructDump_rec( p, Gia_ObjFaninId1p(p, pObj), 0, vStr, nDigitsId ); |
| Vec_StrPush( vStr, ']' ); |
| } |
| else |
| { |
| Gia_MuxStructDump_rec( p, Gia_ObjFaninId1p(p, pObj), 0, vStr, nDigitsId ); |
| Vec_StrPush( vStr, '|' ); |
| Gia_MuxStructDump_rec( p, Gia_ObjFaninId0p(p, pObj), 0, vStr, nDigitsId ); |
| Vec_StrPush( vStr, ']' ); |
| } |
| } |
| int Gia_MuxStructDump( Gia_Man_t * p, int iObj, Vec_Str_t * vStr, int nDigitsNum, int nDigitsId ) |
| { |
| int Count1, Count2; |
| assert( Gia_ObjIsMuxId(p, iObj) ); |
| Count1 = Gia_MuxDeref( p, iObj ); |
| Vec_StrClear( vStr ); |
| Vec_StrPrintNumStar( vStr, Count1, nDigitsNum ); |
| Gia_MuxStructDump_rec( p, iObj, 1, vStr, nDigitsId ); |
| Vec_StrPush( vStr, '\0' ); |
| Count2 = Gia_MuxRef( p, iObj ); |
| assert( Count1 == Count2 ); |
| return Count1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Gia_ManMuxCompare( char ** pp1, char ** pp2 ) |
| { |
| int Diff = strcmp( *pp1, *pp2 ); |
| if ( Diff < 0 ) |
| return 1; |
| if ( Diff > 0) |
| return -1; |
| return 0; |
| } |
| int Gia_ManMuxCountOne( char * p ) |
| { |
| int Count = 0; |
| for ( ; *p; p++ ) |
| Count += (*p == '['); |
| return Count; |
| } |
| |
| typedef struct Mux_Man_t_ Mux_Man_t; |
| struct Mux_Man_t_ |
| { |
| Gia_Man_t * pGia; // manager |
| Abc_Nam_t * pNames; // hashing name into ID |
| Vec_Wec_t * vTops; // top nodes for each struct |
| }; |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Mux_Man_t * Mux_ManAlloc( Gia_Man_t * pGia ) |
| { |
| Mux_Man_t * p; |
| p = ABC_CALLOC( Mux_Man_t, 1 ); |
| p->pGia = pGia; |
| p->pNames = Abc_NamStart( 10000, 50 ); |
| p->vTops = Vec_WecAlloc( 1000 ); |
| Vec_WecPushLevel( p->vTops ); |
| return p; |
| } |
| void Mux_ManFree( Mux_Man_t * p ) |
| { |
| Abc_NamStop( p->pNames ); |
| Vec_WecFree( p->vTops ); |
| ABC_FREE( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Gia_ManMuxProfile( Mux_Man_t * p, int fWidth ) |
| { |
| int i, Entry, Counter, Total; |
| Vec_Int_t * vVec, * vCounts; |
| vCounts = Vec_IntStart( 1000 ); |
| if ( fWidth ) |
| { |
| Vec_WecForEachLevelStart( p->vTops, vVec, i, 1 ) |
| Vec_IntAddToEntry( vCounts, Abc_MinInt(Vec_IntSize(vVec), 999), 1 ); |
| } |
| else |
| { |
| for ( i = 1; i < Vec_WecSize(p->vTops); i++ ) |
| Vec_IntAddToEntry( vCounts, Abc_MinInt(atoi(Abc_NamStr(p->pNames, i)), 999), 1 ); |
| } |
| Total = Vec_IntCountPositive(vCounts); |
| if ( Total == 0 ) |
| return 0; |
| printf( "The distribution of MUX tree %s:\n", fWidth ? "widths" : "sizes" ); |
| Counter = 0; |
| Vec_IntForEachEntry( vCounts, Entry, i ) |
| { |
| if ( !Entry ) continue; |
| if ( ++Counter == 12 ) |
| printf( "\n" ), Counter = 0; |
| printf( " %d=%d", i, Entry ); |
| } |
| printf( "\nSummary: " ); |
| printf( "Max = %d ", Vec_IntFindMax(vCounts) ); |
| printf( "Ave = %.2f", 1.0*Vec_IntSum(vCounts)/Total ); |
| printf( "\n" ); |
| Vec_IntFree( vCounts ); |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_ManMuxProfiling( Gia_Man_t * p ) |
| { |
| Mux_Man_t * pMan; |
| Gia_Man_t * pNew; |
| Gia_Obj_t * pObj; |
| Vec_Str_t * vStr; |
| Vec_Int_t * vFans, * vVec; |
| int i, Counter, fFound, iStructId, nDigitsId; |
| abctime clk = Abc_Clock(); |
| |
| pNew = Gia_ManDupMuxes( p, 2 ); |
| nDigitsId = Abc_Base10Log( Gia_ManObjNum(pNew) ); |
| |
| pMan = Mux_ManAlloc( pNew ); |
| |
| Gia_ManLevelNum( pNew ); |
| Gia_ManCreateRefs( pNew ); |
| Gia_ManForEachCo( pNew, pObj, i ) |
| Gia_ObjRefFanin0Inc( pNew, pObj ); |
| |
| vStr = Vec_StrAlloc( 1000 ); |
| vFans = Gia_ManFirstFanouts( pNew ); |
| Gia_ManForEachMux( pNew, pObj, i ) |
| { |
| // skip MUXes in the middle of the tree (which have only one MUX fanout) |
| if ( Gia_ObjRefNumId(pNew, i) == 1 && Gia_ObjIsMuxId(pNew, Vec_IntEntry(vFans, i)) ) |
| continue; |
| // this node is the root of the MUX structure - create hash key |
| Counter = Gia_MuxStructDump( pNew, i, vStr, 3, nDigitsId ); |
| if ( Counter == 1 ) |
| continue; |
| iStructId = Abc_NamStrFindOrAdd( pMan->pNames, Vec_StrArray(vStr), &fFound ); |
| if ( !fFound ) |
| Vec_WecPushLevel( pMan->vTops ); |
| assert( Abc_NamObjNumMax(pMan->pNames) == Vec_WecSize(pMan->vTops) ); |
| Vec_IntPush( Vec_WecEntry(pMan->vTops, iStructId), i ); |
| } |
| Vec_StrFree( vStr ); |
| Vec_IntFree( vFans ); |
| |
| printf( "MUX structure profile for AIG \"%s\":\n", p->pName ); |
| printf( "Total MUXes = %d. Total trees = %d. Unique trees = %d. Memory = %.2f MB ", |
| Gia_ManMuxNum(pNew), Vec_WecSizeSize(pMan->vTops), Vec_WecSize(pMan->vTops)-1, |
| 1.0*Abc_NamMemUsed(pMan->pNames)/(1<<20) ); |
| Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); |
| |
| if ( Gia_ManMuxProfile(pMan, 0) ) |
| { |
| Gia_ManMuxProfile( pMan, 1 ); |
| |
| // short the first ones |
| printf( "The first %d structures: \n", 10 ); |
| Vec_WecForEachLevelStartStop( pMan->vTops, vVec, i, 1, Abc_MinInt(Vec_WecSize(pMan->vTops), 10) ) |
| { |
| char * pTemp = Abc_NamStr(pMan->pNames, i); |
| printf( "%5d : ", i ); |
| printf( "Occur = %4d ", Vec_IntSize(vVec) ); |
| printf( "Size = %4d ", atoi(pTemp) ); |
| printf( "%s\n", pTemp ); |
| } |
| |
| // print trees for the first one |
| Counter = 0; |
| Vec_WecForEachLevelStart( pMan->vTops, vVec, i, 1 ) |
| { |
| char * pTemp = Abc_NamStr(pMan->pNames, i); |
| if ( Vec_IntSize(vVec) > 5 && atoi(pTemp) > 5 ) |
| { |
| int k, Entry; |
| printf( "For example, structure %d has %d MUXes and bit-width %d:\n", i, atoi(pTemp), Vec_IntSize(vVec) ); |
| Vec_IntForEachEntry( vVec, Entry, k ) |
| Gia_MuxStructPrint( pNew, Entry ); |
| if ( ++Counter == 5 ) |
| break; |
| } |
| } |
| } |
| |
| Mux_ManFree( pMan ); |
| Gia_ManStop( pNew ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compute one-level TFI/TFO structural signatures.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| |
| // these are object/fanin/fanout attributes |
| // http://stackoverflow.com/questions/9907160/how-to-convert-enum-names-to-string-in-c |
| #define GIA_FOREACH_ITEM(ITEM) \ |
| ITEM(C0) \ |
| ITEM(PO) \ |
| ITEM(PI) \ |
| ITEM(FF) \ |
| ITEM(XOR) \ |
| ITEM(MUX) \ |
| ITEM(AND) \ |
| ITEM(iC0) \ |
| ITEM(iC1) \ |
| ITEM(iPI) \ |
| ITEM(iFF) \ |
| ITEM(iXOR) \ |
| ITEM(iMUX) \ |
| ITEM(iAND) \ |
| ITEM(iANDn) \ |
| ITEM(iANDp) \ |
| ITEM(oPO) \ |
| ITEM(oFF) \ |
| ITEM(oXOR) \ |
| ITEM(oMUXc) \ |
| ITEM(oMUXd) \ |
| ITEM(oAND) \ |
| ITEM(oANDn) \ |
| ITEM(oANDp) \ |
| ITEM(GIA_END) |
| |
| #define GENERATE_ENUM(ENUM) ENUM, |
| typedef enum { GIA_FOREACH_ITEM(GENERATE_ENUM) } Gia_ObjType_t; |
| |
| #define GENERATE_STRING(STRING) #STRING, |
| static const char * GIA_TYPE_STRINGS[] = { GIA_FOREACH_ITEM(GENERATE_STRING) }; |
| |
| void Gia_ManProfileStructuresTest( Gia_Man_t * p ) |
| { |
| int i; |
| for ( i = 0; i < GIA_END; i++ ) |
| printf( "%d = %s\n", i, GIA_TYPE_STRINGS[i] ); |
| } |
| |
| |
| |
| // find object code |
| int Gia_ManEncodeObj( Gia_Man_t * p, int i ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, i ); |
| assert( !Gia_ObjIsRi(p, pObj) ); |
| if ( Gia_ObjIsConst0(pObj) ) |
| return C0; |
| if ( Gia_ObjIsPo(p, pObj) ) |
| return PO; |
| if ( Gia_ObjIsPi(p, pObj) ) |
| return PI; |
| if ( Gia_ObjIsCi(pObj) ) |
| return FF; |
| if ( Gia_ObjIsXor(pObj) ) |
| return XOR; |
| if ( Gia_ObjIsMux(p, pObj) ) |
| return MUX; |
| assert( Gia_ObjIsAnd(pObj) ); |
| return AND; |
| } |
| // find fanin code |
| int Gia_ManEncodeFanin( Gia_Man_t * p, int iLit ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, Abc_Lit2Var(iLit) ); |
| if ( Gia_ObjIsConst0(pObj) ) |
| return iC0; |
| if ( Gia_ObjIsPi(p, pObj) ) |
| return iPI; |
| if ( Gia_ObjIsCi(pObj) ) |
| return iFF; |
| if ( Gia_ObjIsXor(pObj) ) |
| return iXOR; |
| if ( Gia_ObjIsMux(p, pObj) ) |
| return iMUX; |
| assert( Gia_ObjIsAnd(pObj) ); |
| return iAND; |
| // if ( Abc_LitIsCompl(iLit) ) |
| // return iANDn; |
| // else |
| // return iANDp; |
| } |
| // find fanout code |
| Gia_ObjType_t Gia_ManEncodeFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i ) |
| { |
| // int iLit; |
| if ( Gia_ObjIsPo(p, pObj) ) |
| return oPO; |
| if ( Gia_ObjIsCo(pObj) ) |
| return oFF; |
| if ( Gia_ObjIsXor(pObj) ) |
| return oXOR; |
| if ( Gia_ObjIsMux(p, pObj) ) |
| return i == 2 ? oMUXc : oMUXd; |
| assert( Gia_ObjIsAnd(pObj) ); |
| return oAND; |
| // iLit = i ? Gia_ObjFaninLit1p(p, pObj) : Gia_ObjFaninLit0p(p, pObj); |
| // if ( Abc_LitIsCompl(iLit) ) |
| // return oANDn; |
| // else |
| // return oANDp; |
| } |
| |
| void Gia_ManProfileCollect( Gia_Man_t * p, int i, Vec_Int_t * vCode, Vec_Int_t * vCodeOffsets, Vec_Int_t * vArray ) |
| { |
| int k; |
| Vec_IntClear( vArray ); |
| for ( k = Vec_IntEntry(vCodeOffsets, i); k < Vec_IntEntry(vCodeOffsets, i+1); k++ ) |
| Vec_IntPush( vArray, Vec_IntEntry(vCode, k) ); |
| } |
| |
| void Gia_ManProfilePrintOne( Gia_Man_t * p, int i, Vec_Int_t * vArray ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj( p, i ); |
| int k, nFanins, nFanouts; |
| if ( Gia_ObjIsRi(p, pObj) ) |
| return; |
| nFanins = Gia_ObjIsRo(p, pObj) ? 1 : Gia_ObjFaninNum(p, pObj); |
| nFanouts = Gia_ObjFanoutNum(p, pObj); |
| |
| printf( "%6d : ", i ); |
| for ( k = 0; k < nFanins; k++ ) |
| printf( " %5s", GIA_TYPE_STRINGS[Vec_IntEntry(vArray, k + 1)] ); |
| for ( ; k < 3; k++ ) |
| printf( " %5s", "" ); |
| printf( " ->" ); |
| printf( " %5s", GIA_TYPE_STRINGS[Vec_IntEntry(vArray, 0)] ); |
| printf( " ->" ); |
| if ( nFanouts > 0 ) |
| { |
| int Count = 1, Prev = Vec_IntEntry(vArray, 1 + nFanins); |
| for ( k = 1; k < nFanouts; k++ ) |
| { |
| if ( Prev != Vec_IntEntry(vArray, k + 1 + nFanins) ) |
| { |
| printf( " %d x %s", Count, GIA_TYPE_STRINGS[Prev] ); |
| Prev = Vec_IntEntry(vArray, k + 1 + nFanins); |
| Count = 0; |
| } |
| Count++; |
| } |
| printf( " %d x %s", Count, GIA_TYPE_STRINGS[Prev] ); |
| } |
| printf( "\n" ); |
| } |
| |
| Vec_Int_t * Gia_ManProfileHash( Gia_Man_t * p, Vec_Int_t * vCode, Vec_Int_t * vCodeOffsets ) |
| { |
| Hsh_VecMan_t * pHash; |
| Vec_Int_t * vRes, * vArray; |
| Gia_Obj_t * pObj; |
| int i; |
| vRes = Vec_IntAlloc( Gia_ManObjNum(p) ); |
| pHash = Hsh_VecManStart( Gia_ManObjNum(p) ); |
| // add empty entry |
| vArray = Vec_IntAlloc( 100 ); |
| Hsh_VecManAdd( pHash, vArray ); |
| // iterate through the entries |
| Gia_ManForEachObj( p, pObj, i ) |
| { |
| Gia_ManProfileCollect( p, i, vCode, vCodeOffsets, vArray ); |
| Vec_IntPush( vRes, Hsh_VecManAdd( pHash, vArray ) ); |
| } |
| Hsh_VecManStop( pHash ); |
| Vec_IntFree( vArray ); |
| assert( Vec_IntSize(vRes) == Gia_ManObjNum(p) ); |
| return vRes; |
| } |
| |
| |
| void Gia_ManProfileStructuresInt( Gia_Man_t * p, int nLimit, int fVerbose ) |
| { |
| Vec_Int_t * vRes, * vCount, * vFirst; |
| Vec_Int_t * vCode, * vCodeOffsets, * vArray; |
| Gia_Obj_t * pObj, * pFanout; |
| int i, k, nFanins, nFanouts, * pPerm, nClasses; |
| assert( p->pMuxes ); |
| Gia_ManStaticFanoutStart( p ); |
| // create fanout codes |
| vArray = Vec_IntAlloc( 100 ); |
| vCode = Vec_IntAlloc( 5 * Gia_ManObjNum(p) ); |
| vCodeOffsets = Vec_IntAlloc( Gia_ManObjNum(p) ); |
| Gia_ManForEachObj( p, pObj, i ) |
| { |
| Vec_IntPush( vCodeOffsets, Vec_IntSize(vCode) ); |
| if ( Gia_ObjIsRi(p, pObj) ) |
| continue; |
| nFanins = Gia_ObjFaninNum(p, pObj); |
| nFanouts = Gia_ObjFanoutNum(p, pObj); |
| Vec_IntPush( vCode, Gia_ManEncodeObj(p, i) ); |
| if ( nFanins == 3 ) |
| { |
| int iLit = Gia_ObjFaninLit2p(p, pObj); |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Abc_LitRegular(iLit)) ); |
| if ( Abc_LitIsCompl(iLit) ) |
| { |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)) ); |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit1p(p, pObj)) ); |
| } |
| else |
| { |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit1p(p, pObj)) ); |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)) ); |
| } |
| } |
| else if ( nFanins == 2 ) |
| { |
| int Code0 = Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)); |
| int Code1 = Gia_ManEncodeFanin(p, Gia_ObjFaninLit1p(p, pObj)); |
| Vec_IntPush( vCode, Code0 < Code1 ? Code0 : Code1 ); |
| Vec_IntPush( vCode, Code0 < Code1 ? Code1 : Code0 ); |
| } |
| else if ( nFanins == 1 ) |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)) ); |
| else if ( Gia_ObjIsRo(p, pObj) ) |
| Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, Gia_ObjRoToRi(p, pObj))) ); |
| |
| // add fanouts |
| Vec_IntClear( vArray ); |
| Gia_ObjForEachFanoutStatic( p, pObj, pFanout, k ) |
| { |
| int Index = Gia_ObjWhatFanin( p, pFanout, pObj ); |
| Gia_ObjType_t Type = Gia_ManEncodeFanout( p, pFanout, Index ); |
| Vec_IntPush( vArray, Type ); |
| } |
| Vec_IntSort( vArray, 0 ); |
| Vec_IntAppend( vCode, vArray ); |
| } |
| assert( Vec_IntSize(vCodeOffsets) == Gia_ManObjNum(p) ); |
| Vec_IntPush( vCodeOffsets, Vec_IntSize(vCode) ); |
| // print the results |
| if ( fVerbose ) |
| { |
| printf( "Showing TFI/node/TFO structures for all nodes:\n" ); |
| Gia_ManForEachObj( p, pObj, i ) |
| { |
| Gia_ManProfileCollect( p, i, vCode, vCodeOffsets, vArray ); |
| Gia_ManProfilePrintOne( p, i, vArray ); |
| } |
| } |
| |
| // collect statistics |
| vRes = Gia_ManProfileHash( p, vCode, vCodeOffsets ); |
| //Vec_IntPrint( vRes ); |
| |
| // count how many times each class appears |
| nClasses = Vec_IntFindMax(vRes) + 1; |
| vCount = Vec_IntStart( nClasses ); |
| vFirst = Vec_IntStart( nClasses ); |
| Gia_ManForEachObj( p, pObj, i ) |
| { |
| int Entry = Vec_IntEntry( vRes, i ); |
| if ( Gia_ObjIsRi(p, pObj) ) |
| continue; |
| if ( Vec_IntEntry(vCount, Entry) == 0 ) |
| Vec_IntWriteEntry( vFirst, Entry, i ); |
| Vec_IntAddToEntry( vCount, Entry, -1 ); |
| } |
| // sort the counts |
| pPerm = Abc_MergeSortCost( Vec_IntArray(vCount), Vec_IntSize(vCount) ); |
| printf( "Showing TFI/node/TFO structures that appear more than %d times.\n", nLimit ); |
| for ( i = 0; i < nClasses-1; i++ ) |
| { |
| if ( nLimit > -Vec_IntEntry(vCount, pPerm[i]) ) |
| break; |
| printf( "%6d : ", i ); |
| printf( "%6d : ", pPerm[i] ); |
| printf( "Weight =%6d ", -Vec_IntEntry(vCount, pPerm[i]) ); |
| printf( "First obj =" ); |
| // print the object |
| Gia_ManProfileCollect( p, Vec_IntEntry(vFirst, pPerm[i]), vCode, vCodeOffsets, vArray ); |
| Gia_ManProfilePrintOne( p, Vec_IntEntry(vFirst, pPerm[i]), vArray ); |
| } |
| |
| // cleanup |
| ABC_FREE( pPerm ); |
| Vec_IntFree( vRes ); |
| Vec_IntFree( vCount ); |
| Vec_IntFree( vFirst ); |
| |
| Vec_IntFree( vArray ); |
| Vec_IntFree( vCode ); |
| Vec_IntFree( vCodeOffsets ); |
| Gia_ManStaticFanoutStop( p ); |
| } |
| void Gia_ManProfileStructures( Gia_Man_t * p, int nLimit, int fVerbose ) |
| { |
| if ( p->pMuxes ) |
| Gia_ManProfileStructuresInt( p, nLimit, fVerbose ); |
| else |
| { |
| Gia_Man_t * pNew = Gia_ManDupMuxes( p, 2 ); |
| Gia_ManProfileStructuresInt( pNew, nLimit, fVerbose ); |
| Gia_ManStop( pNew ); |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
