/**CFile**************************************************************** FileName [giaCof.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Scalable AIG package.] Synopsis [Cofactor estimation procedures.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: giaCof.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include #include "gia.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// typedef struct Cof_Fan_t_ Cof_Fan_t; struct Cof_Fan_t_ { unsigned iFan : 31; // ID of the fanin/fanout unsigned fCompl : 1; // complemented attribute }; typedef struct Cof_Obj_t_ Cof_Obj_t; struct Cof_Obj_t_ { unsigned fTerm : 1; // terminal node (CI/CO) unsigned fPhase : 1; // value under 000 pattern unsigned fMark0 : 1; // first user-controlled mark unsigned fMark1 : 1; // second user-controlled mark unsigned nFanins : 4; // the number of fanins unsigned nFanouts : 24; // total number of fanouts unsigned nFanoutsM; // total number of MUX ctrl fanouts unsigned Value; // application specific data int Id; // ID of the node int iNext; // next one in the linked list int iLit; // literal of the node after rehashing Cof_Fan_t Fanios[0]; // the array of fanins/fanouts }; typedef struct Cof_Man_t_ Cof_Man_t; struct Cof_Man_t_ { Gia_Man_t * pGia; // the original AIG manager Vec_Int_t * vCis; // the vector of CIs (PIs + LOs) Vec_Int_t * vCos; // the vector of COs (POs + LIs) int nObjs; // the number of objects int nNodes; // the number of nodes int nTravIds; // traversal ID of the network int * pObjData; // the logic network defined for the AIG int nObjData; // the size of array to store the logic network int * pLevels; // the linked lists of levels int nLevels; // the max number of logic levels }; static inline unsigned Gia_ObjHandle( Gia_Obj_t * pObj ) { return pObj->Value; } static inline int Cof_ObjLevel( Cof_Man_t * p, Cof_Obj_t * pObj ) { return Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia,pObj->Id)); } static inline unsigned Cof_ObjHandle( Cof_Man_t * p, Cof_Obj_t * pObj ) { return (unsigned)(((int *)pObj) - p->pObjData); } static inline unsigned Cof_ObjHandleDiff( Cof_Obj_t * pObj, Cof_Obj_t * pFanin ) { return (unsigned)(((int *)pObj) - ((int *)pFanin)); } static inline int Cof_ObjIsTerm( Cof_Obj_t * pObj ) { return pObj->fTerm; } static inline int Cof_ObjIsCi( Cof_Obj_t * pObj ) { return pObj->fTerm && pObj->nFanins == 0; } static inline int Cof_ObjIsCo( Cof_Obj_t * pObj ) { return pObj->fTerm && pObj->nFanins == 1; } static inline int Cof_ObjIsNode( Cof_Obj_t * pObj ) { return!pObj->fTerm && pObj->nFanins > 0; } static inline int Cof_ObjIsConst0( Cof_Obj_t * pObj ) { return!pObj->fTerm && pObj->nFanins == 0; } static inline int Cof_ObjFaninNum( Cof_Obj_t * pObj ) { return pObj->nFanins; } static inline int Cof_ObjFanoutNum( Cof_Obj_t * pObj ) { return pObj->nFanouts; } static inline int Cof_ObjSize( Cof_Obj_t * pObj ) { return sizeof(Cof_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; } static inline Cof_Obj_t * Cof_ManObj( Cof_Man_t * p, unsigned iHandle ) { return (Cof_Obj_t *)(p->pObjData + iHandle); } static inline Cof_Obj_t * Cof_ObjFanin( Cof_Obj_t * pObj, int i ) { return (Cof_Obj_t *)(((int *)pObj) - pObj->Fanios[i].iFan); } static inline Cof_Obj_t * Cof_ObjFanout( Cof_Obj_t * pObj, int i ) { return (Cof_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i].iFan); } static inline int Cof_ManObjNum( Cof_Man_t * p ) { return p->nObjs; } static inline int Cof_ManNodeNum( Cof_Man_t * p ) { return p->nNodes; } static inline void Cof_ManResetTravId( Cof_Man_t * p ) { extern void Cof_ManCleanValue( Cof_Man_t * p ); Cof_ManCleanValue( p ); p->nTravIds = 1; } static inline void Cof_ManIncrementTravId( Cof_Man_t * p ) { p->nTravIds++; } static inline void Cof_ObjSetTravId( Cof_Obj_t * pObj, int TravId ) { pObj->Value = TravId; } static inline void Cof_ObjSetTravIdCurrent( Cof_Man_t * p, Cof_Obj_t * pObj ) { pObj->Value = p->nTravIds; } static inline void Cof_ObjSetTravIdPrevious( Cof_Man_t * p, Cof_Obj_t * pObj ) { pObj->Value = p->nTravIds - 1; } static inline int Cof_ObjIsTravIdCurrent( Cof_Man_t * p, Cof_Obj_t * pObj ) { return ((int)pObj->Value == p->nTravIds); } static inline int Cof_ObjIsTravIdPrevious( Cof_Man_t * p, Cof_Obj_t * pObj ) { return ((int)pObj->Value == p->nTravIds - 1); } #define Cof_ManForEachObj( p, pObj, i ) \ for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) ) #define Cof_ManForEachNode( p, pObj, i ) \ for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) ) if ( Cof_ObjIsTerm(pObj) ) {} else #define Cof_ObjForEachFanin( pObj, pNext, i ) \ for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Cof_ObjFanin(pObj,i)); i++ ) #define Cof_ObjForEachFanout( pObj, pNext, i ) \ for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Cof_ObjFanout(pObj,i)); i++ ) //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Creates logic network isomorphic to the given AIG.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cof_Man_t * Cof_ManCreateLogicSimple( Gia_Man_t * pGia ) { Cof_Man_t * p; Cof_Obj_t * pObjLog, * pFanLog; Gia_Obj_t * pObj; int * pMuxRefs; int i, iHandle = 0; p = ABC_CALLOC( Cof_Man_t, 1 ); p->pGia = pGia; p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) ); p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) ); p->nObjData = (sizeof(Cof_Obj_t) / 4) * Gia_ManObjNum(pGia) + 4 * Gia_ManAndNum(pGia) + 2 * Gia_ManCoNum(pGia); p->pObjData = ABC_CALLOC( int, p->nObjData ); ABC_FREE( pGia->pRefs ); Gia_ManCreateRefs( pGia ); Gia_ManForEachObj( pGia, pObj, i ) { pObj->Value = iHandle; pObjLog = Cof_ManObj( p, iHandle ); pObjLog->nFanins = 0; pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj ); pObjLog->Id = i; pObjLog->Value = 0; if ( Gia_ObjIsAnd(pObj) ) { pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin0(pObj)) ); pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan = pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog ); pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC0(pObj); pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin1(pObj)) ); pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan = pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog ); pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC1(pObj); p->nNodes++; } else if ( Gia_ObjIsCo(pObj) ) { pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin0(pObj)) ); pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan = pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog ); pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC0(pObj); pObjLog->fTerm = 1; Vec_IntPush( p->vCos, iHandle ); } else if ( Gia_ObjIsCi(pObj) ) { pObjLog->fTerm = 1; Vec_IntPush( p->vCis, iHandle ); } iHandle += Cof_ObjSize( pObjLog ); p->nObjs++; } assert( iHandle == p->nObjData ); pMuxRefs = Gia_ManCreateMuxRefs( pGia ); Gia_ManForEachObj( pGia, pObj, i ) { pObjLog = Cof_ManObj( p, Gia_ObjHandle(pObj) ); assert( pObjLog->nFanouts == pObjLog->Value ); pObjLog->nFanoutsM = pMuxRefs[i]; } ABC_FREE( pMuxRefs ); return p; } /**Function************************************************************* Synopsis [Creates logic network isomorphic to the given AIG.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cof_ManStop( Cof_Man_t * p ) { Vec_IntFree( p->vCis ); Vec_IntFree( p->vCos ); ABC_FREE( p->pObjData ); ABC_FREE( p->pLevels ); ABC_FREE( p ); } /**Function************************************************************* Synopsis [Collects support nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManTfoSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj ) { Cof_Obj_t * pNext; unsigned i, Counter = 0; if ( Cof_ObjIsTravIdCurrent(p, pObj) ) return 0; Cof_ObjSetTravIdCurrent(p, pObj); if ( Cof_ObjIsCo(pObj) ) return 0; assert( Cof_ObjIsCi(pObj) || Cof_ObjIsNode(pObj) ); Cof_ObjForEachFanout( pObj, pNext, i ) Counter += Cof_ManTfoSize_rec( p, pNext ); return 1 + Counter; } /**Function************************************************************* Synopsis [Collects support nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManTfoSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs ) { int i, Counter = 0; Cof_ManIncrementTravId( p ); for ( i = 0; i < nObjs; i++ ) Counter += Cof_ManTfoSize_rec( p, ppObjs[i] ) - 1; return Counter; } /**Function************************************************************* Synopsis [Collects support nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManTfiSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj ) { Cof_Obj_t * pNext; unsigned i, Counter = 0; if ( Cof_ObjIsTravIdCurrent(p, pObj) ) return 0; Cof_ObjSetTravIdCurrent(p, pObj); if ( Cof_ObjIsCi(pObj) ) return 0; assert( Cof_ObjIsNode(pObj) ); Cof_ObjForEachFanin( pObj, pNext, i ) Counter += Cof_ManTfiSize_rec( p, pNext ); return 1 + Counter; } /**Function************************************************************* Synopsis [Collects support nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManTfiSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs ) { int i, Counter = 0; Cof_ManIncrementTravId( p ); for ( i = 0; i < nObjs; i++ ) if ( Cof_ObjIsCo(ppObjs[i]) ) Counter += Cof_ManTfiSize_rec( p, Cof_ObjFanin(ppObjs[i],0) ); else Counter += Cof_ManTfiSize_rec( p, ppObjs[i] ); return Counter; } /**Function************************************************************* Synopsis [Collects support nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManSuppSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj ) { Cof_Obj_t * pNext; unsigned i, Counter = 0; if ( Cof_ObjIsTravIdCurrent(p, pObj) ) return 0; Cof_ObjSetTravIdCurrent(p, pObj); if ( Cof_ObjIsCi(pObj) ) return 1; assert( Cof_ObjIsNode(pObj) ); Cof_ObjForEachFanin( pObj, pNext, i ) Counter += Cof_ManSuppSize_rec( p, pNext ); return Counter; } /**Function************************************************************* Synopsis [Collects support nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManSuppSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs ) { int i, Counter = 0; Cof_ManIncrementTravId( p ); for ( i = 0; i < nObjs; i++ ) if ( Cof_ObjIsCo(ppObjs[i]) ) Counter += Cof_ManSuppSize_rec( p, Cof_ObjFanin(ppObjs[i],0) ); else Counter += Cof_ManSuppSize_rec( p, ppObjs[i] ); return Counter; } /**Function************************************************************* Synopsis [Cleans the value.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cof_ManCleanValue( Cof_Man_t * p ) { Cof_Obj_t * pObj; int i; Cof_ManForEachObj( p, pObj, i ) pObj->Value = 0; } /**Function************************************************************* Synopsis [Returns sorted array of node handles with largest fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cof_ManInsertEntry_rec( Vec_Ptr_t * vNodes, Cof_Obj_t * pNode, int nNodeMax ) { Cof_Obj_t * pLast; if ( Vec_PtrSize(vNodes) == 0 ) { Vec_PtrPush(vNodes, pNode); return; } pLast = (Cof_Obj_t *)Vec_PtrPop(vNodes); if ( Cof_ObjFanoutNum(pLast) < Cof_ObjFanoutNum(pNode) ) { Cof_ManInsertEntry_rec( vNodes, pNode, nNodeMax ); if ( Vec_PtrSize(vNodes) < nNodeMax ) Vec_PtrPush( vNodes, pLast ); } else { Vec_PtrPush( vNodes, pLast ); if ( Vec_PtrSize(vNodes) < nNodeMax ) Vec_PtrPush( vNodes, pNode ); } } /**Function************************************************************* Synopsis [Returns sorted array of node handles with largest fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Cof_ManCollectHighFanout( Cof_Man_t * p, int nNodes ) { Vec_Ptr_t * vNodes; Cof_Obj_t * pObj; int i; vNodes = Vec_PtrAlloc( nNodes ); Cof_ManForEachObj( p, pObj, i ) if ( Cof_ObjIsCi(pObj) || Cof_ObjIsNode(pObj) ) Cof_ManInsertEntry_rec( vNodes, pObj, nNodes ); return vNodes; } /**Function************************************************************* Synopsis [Returns sorted array of node handles with largest fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_ManCountRemoved( Cof_Man_t * p, Cof_Obj_t * pRoot, int fConst1 ) { Gia_Obj_t * pNextGia; Cof_Obj_t * pTemp, * pNext, * pFanin0, * pFanin1; int Counter = 0, LevelStart, LevelNext; int i, k, iHandle, iLit0, iLit1, iNextNew; // restart the trav ids Cof_ManIncrementTravId( p ); Cof_ObjSetTravIdCurrent( p, pRoot ); // add the node to the queue LevelStart = Cof_ObjLevel(p, pRoot); assert( p->pLevels[LevelStart] == 0 ); pRoot->iNext = 0; p->pLevels[LevelStart] = Cof_ObjHandle( p, pRoot ); // set the new literal pRoot->iLit = Abc_Var2Lit( 0, fConst1 ); // process nodes in the levelized order for ( i = LevelStart; i < p->nLevels; i++ ) { for ( iHandle = p->pLevels[i]; iHandle && (pTemp = Cof_ManObj(p, iHandle)); iHandle = pTemp->iNext ) { assert( pTemp->Id != Abc_Lit2Var(pTemp->iLit) ); Cof_ObjForEachFanout( pTemp, pNext, k ) { if ( Cof_ObjIsCo(pNext) ) continue; if ( Cof_ObjIsTravIdCurrent(p, pNext) ) continue; pFanin0 = Cof_ObjFanin( pNext, 0 ); pFanin1 = Cof_ObjFanin( pNext, 1 ); assert( pFanin0 == pTemp || pFanin1 == pTemp ); pNextGia = Gia_ManObj( p->pGia, pNext->Id ); if ( Cof_ObjIsTravIdCurrent(p, pFanin0) ) iLit0 = Abc_LitNotCond( pFanin0->iLit, Gia_ObjFaninC0(pNextGia) ); else iLit0 = Gia_ObjFaninLit0( pNextGia, pNext->Id ); if ( Cof_ObjIsTravIdCurrent(p, pFanin1) ) iLit1 = Abc_LitNotCond( pFanin1->iLit, Gia_ObjFaninC1(pNextGia) ); else iLit1 = Gia_ObjFaninLit1( pNextGia, pNext->Id ); iNextNew = Gia_ManHashAndTry( p->pGia, iLit0, iLit1 ); if ( iNextNew == -1 ) continue; Cof_ObjSetTravIdCurrent(p, pNext); // set the new literal pNext->iLit = iNextNew; // add it to be processed LevelNext = Cof_ObjLevel( p, pNext ); assert( LevelNext > i && LevelNext < p->nLevels ); pNext->iNext = p->pLevels[LevelNext]; p->pLevels[LevelNext] = Cof_ObjHandle( p, pNext ); Counter++; } } p->pLevels[i] = 0; } return Counter; } /**Function************************************************************* Synopsis [Returns sorted array of node handles with largest fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cof_ManPrintHighFanoutOne( Cof_Man_t * p, Cof_Obj_t * pObj ) { printf( "%7d : ", pObj->Id ); printf( "i/o/c =%2d %5d %5d ", Cof_ObjFaninNum(pObj), Cof_ObjFanoutNum(pObj), 2*pObj->nFanoutsM ); printf( "l =%4d ", Cof_ObjLevel(p, pObj) ); printf( "s =%5d ", Cof_ManSuppSize(p, &pObj, 1) ); printf( "TFI =%7d ", Cof_ManTfiSize(p, &pObj, 1) ); printf( "TFO =%7d ", Cof_ManTfoSize(p, &pObj, 1) ); printf( "C0 =%6d ", Cof_ManCountRemoved(p, pObj, 0) ); printf( "C1 =%6d", Cof_ManCountRemoved(p, pObj, 1) ); printf( "\n" ); } /**Function************************************************************* Synopsis [Returns sorted array of node handles with largest fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cof_ManPrintHighFanout( Cof_Man_t * p, int nNodes ) { Vec_Ptr_t * vNodes; Cof_Obj_t * pObj; int i; vNodes = Cof_ManCollectHighFanout( p, nNodes ); Vec_PtrForEachEntry( Cof_Obj_t *, vNodes, pObj, i ) Cof_ManPrintHighFanoutOne( p, pObj ); Vec_PtrFree( vNodes ); } /**Function************************************************************* Synopsis [Compute MFFC size of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cof_NodeDeref_rec( Cof_Obj_t * pNode ) { if ( pNode->nFanins == 0 ) return 0; if ( --pNode->nFanouts > 0 ) return 0; return 1 + Cof_NodeDeref_rec( Cof_ObjFanin(pNode, 0) ) + Cof_NodeDeref_rec( Cof_ObjFanin(pNode, 1) ); } int Cof_NodeRef_rec( Cof_Obj_t * pNode ) { if ( pNode->nFanins == 0 ) return 0; if ( pNode->nFanouts++ > 0 ) return 0; return 1 + Cof_NodeRef_rec( Cof_ObjFanin(pNode, 0) ) + Cof_NodeRef_rec( Cof_ObjFanin(pNode, 1) ); } static inline int Cof_ObjMffcSize( Cof_Obj_t * pNode ) { int Count1, Count2, nFanout; nFanout = pNode->nFanouts; pNode->nFanouts = 1; Count1 = Cof_NodeDeref_rec( pNode ); Count2 = Cof_NodeRef_rec( pNode ); pNode->nFanouts = nFanout; assert( Count1 == Count2 ); return Count1; } /**Function************************************************************* Synopsis [Prints the distribution of fanins/fanouts in the network.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cof_ManPrintFanio( Cof_Man_t * p ) { char Buffer[100]; Cof_Obj_t * pNode; Vec_Int_t * vFanins, * vFanouts, * vMffcs; int nFanins, nFanouts, nMffcs, nFaninsMax, nFanoutsMax, nMffcsMax, nFaninsAll, nFanoutsAll, nMffcsAll; int i, k, nSizeMax, nMffcNodes = 0; // determine the largest fanin and fanout nFaninsMax = nFanoutsMax = nMffcsMax = 0; nFaninsAll = nFanoutsAll = nMffcsAll = 0; Cof_ManForEachNode( p, pNode, i ) { if ( i == 0 ) continue; nFanins = Cof_ObjFaninNum(pNode); nFanouts = Cof_ObjFanoutNum(pNode); nMffcs = pNode->nFanouts > 1 ? Cof_ObjMffcSize(pNode) : 0; nFaninsAll += nFanins; nFanoutsAll += nFanouts; nMffcsAll += nMffcs; nFaninsMax = Abc_MaxInt( nFaninsMax, nFanins ); nFanoutsMax = Abc_MaxInt( nFanoutsMax, nFanouts ); nMffcsMax = Abc_MaxInt( nMffcsMax, nMffcs ); } // allocate storage for fanin/fanout numbers nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) ); nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nMffcsMax) + 1), nSizeMax ); vFanins = Vec_IntStart( nSizeMax ); vFanouts = Vec_IntStart( nSizeMax ); vMffcs = Vec_IntStart( nSizeMax ); // count the number of fanins and fanouts Cof_ManForEachNode( p, pNode, i ) { if ( i == 0 ) continue; nFanins = Cof_ObjFaninNum(pNode); nFanouts = Cof_ObjFanoutNum(pNode); nMffcs = pNode->nFanouts > 1 ? Cof_ObjMffcSize(pNode) : 0; if ( nFanins < 10 ) Vec_IntAddToEntry( vFanins, nFanins, 1 ); else if ( nFanins < 100 ) Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 ); else if ( nFanins < 1000 ) Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 ); else if ( nFanins < 10000 ) Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 ); else if ( nFanins < 100000 ) Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 ); else if ( nFanins < 1000000 ) Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 ); else if ( nFanins < 10000000 ) Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 ); if ( nFanouts < 10 ) Vec_IntAddToEntry( vFanouts, nFanouts, 1 ); else if ( nFanouts < 100 ) Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 ); else if ( nFanouts < 1000 ) Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 ); else if ( nFanouts < 10000 ) Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 ); else if ( nFanouts < 100000 ) Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 ); else if ( nFanouts < 1000000 ) Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 ); else if ( nFanouts < 10000000 ) Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 ); if ( nMffcs == 0 ) continue; nMffcNodes++; if ( nMffcs < 10 ) Vec_IntAddToEntry( vMffcs, nMffcs, 1 ); else if ( nMffcs < 100 ) Vec_IntAddToEntry( vMffcs, 10 + nMffcs/10, 1 ); else if ( nMffcs < 1000 ) Vec_IntAddToEntry( vMffcs, 20 + nMffcs/100, 1 ); else if ( nMffcs < 10000 ) Vec_IntAddToEntry( vMffcs, 30 + nMffcs/1000, 1 ); else if ( nMffcs < 100000 ) Vec_IntAddToEntry( vMffcs, 40 + nMffcs/10000, 1 ); else if ( nMffcs < 1000000 ) Vec_IntAddToEntry( vMffcs, 50 + nMffcs/100000, 1 ); else if ( nMffcs < 10000000 ) Vec_IntAddToEntry( vMffcs, 60 + nMffcs/1000000, 1 ); } printf( "The distribution of fanins, fanouts. and MFFCs in the network:\n" ); printf( " Number Nodes with fanin Nodes with fanout Nodes with MFFC\n" ); for ( k = 0; k < nSizeMax; k++ ) { if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 && vMffcs->pArray[k] == 0 ) continue; if ( k < 10 ) printf( "%15d : ", k ); else { sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 ); printf( "%15s : ", Buffer ); } if ( vFanins->pArray[k] == 0 ) printf( " " ); else printf( "%11d ", vFanins->pArray[k] ); printf( " " ); if ( vFanouts->pArray[k] == 0 ) printf( " " ); else printf( "%12d ", vFanouts->pArray[k] ); printf( " " ); if ( vMffcs->pArray[k] == 0 ) printf( " " ); else printf( " %12d ", vMffcs->pArray[k] ); printf( "\n" ); } Vec_IntFree( vFanins ); Vec_IntFree( vFanouts ); Vec_IntFree( vMffcs ); printf( "Fanins: Max = %d. Ave = %.2f. Fanouts: Max = %d. Ave = %.2f. MFFCs: Max = %d. Ave = %.2f.\n", nFaninsMax, 1.0*nFaninsAll /Cof_ManNodeNum(p), nFanoutsMax, 1.0*nFanoutsAll/Cof_ManNodeNum(p), nMffcsMax, 1.0*nMffcsAll /nMffcNodes ); } /**Function************************************************************* Synopsis [Returns sorted array of node handles with largest fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Gia_ManPrintFanio( Gia_Man_t * pGia, int nNodes ) { Cof_Man_t * p; abctime clk = Abc_Clock(); p = Cof_ManCreateLogicSimple( pGia ); p->nLevels = 1 + Gia_ManLevelNum( pGia ); p->pLevels = ABC_CALLOC( int, p->nLevels ); Cof_ManPrintFanio( p ); if ( nNodes > 0 ) { Cof_ManResetTravId( p ); Gia_ManHashStart( pGia ); Cof_ManPrintHighFanout( p, nNodes ); Gia_ManHashStop( pGia ); ABC_PRMn( "Memory for logic network", 4*p->nObjData ); ABC_PRT( "Time", Abc_Clock() - clk ); } Cof_ManStop( p ); } /**Function************************************************************* Synopsis [Duplicates AIG in the DFS order while putting CIs first.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Gia_Man_t * Gia_ManDupCofInt( Gia_Man_t * p, int iVar ) { Gia_Man_t * pNew; Gia_Obj_t * pObj, * pPivot; int i, iCofVar = -1; if ( !(iVar > 0 && iVar < Gia_ManObjNum(p)) ) { printf( "Gia_ManDupCof(): Variable %d is out of range (%d; %d).\n", iVar, 0, Gia_ManObjNum(p) ); return NULL; } // find the cofactoring variable pPivot = Gia_ManObj( p, iVar ); if ( !Gia_ObjIsCand(pPivot) ) { printf( "Gia_ManDupCof(): Variable %d should be a CI or an AND node.\n", iVar ); return NULL; } pNew = Gia_ManStart( Gia_ManObjNum(p) ); pNew->pName = Abc_UtilStrsav( p->pName ); pNew->pSpec = Abc_UtilStrsav( p->pSpec ); Gia_ManHashAlloc( pNew ); Gia_ManFillValue( p ); Gia_ManConst0(p)->Value = 0; // compute negative cofactor Gia_ManForEachCi( p, pObj, i ) { pObj->Value = Gia_ManAppendCi(pNew); if ( pObj == pPivot ) { iCofVar = pObj->Value; pObj->Value = Abc_Var2Lit( 0, 0 ); } } Gia_ManForEachAnd( p, pObj, i ) { pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); if ( pObj == pPivot ) { iCofVar = pObj->Value; pObj->Value = Abc_Var2Lit( 0, 0 ); } } Gia_ManForEachCo( p, pObj, i ) pObj->Value = Gia_ObjFanin0Copy(pObj); // compute the positive cofactor Gia_ManForEachCi( p, pObj, i ) { pObj->Value = Abc_Var2Lit( Gia_ObjId(pNew, Gia_ManCi(pNew, i)), 0 ); if ( pObj == pPivot ) pObj->Value = Abc_Var2Lit( 0, 1 ); } Gia_ManForEachAnd( p, pObj, i ) { pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); if ( pObj == pPivot ) pObj->Value = Abc_Var2Lit( 0, 1 ); } // create MUXes assert( iCofVar > 0 ); Gia_ManForEachCo( p, pObj, i ) { if ( pObj->Value == (unsigned)Gia_ObjFanin0Copy(pObj) ) pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); else pObj->Value = Gia_ManAppendCo( pNew, Gia_ManHashMux(pNew, iCofVar, Gia_ObjFanin0Copy(pObj), pObj->Value) ); } Gia_ManHashStop( pNew ); Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); return pNew; } /**Function************************************************************* Synopsis [Duplicates AIG in the DFS order while putting CIs first.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Gia_Man_t * Gia_ManDupCof( Gia_Man_t * p, int iVar ) { Gia_Man_t * pNew, * pTemp; pNew = Gia_ManDupCofInt( p, iVar ); pNew = Gia_ManCleanup( pTemp = pNew ); Gia_ManStop( pTemp ); return pNew; } /**Function************************************************************* Synopsis [Determines variables whose fanout count is higher than this.] Description [Variables are returned in a reverse topological order.] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Int_t * Gia_ManCofVars( Gia_Man_t * p, int nFanLim ) { Vec_Int_t * vVars; Gia_Obj_t * pObj; int i; ABC_FREE( p->pRefs ); Gia_ManCreateRefs( p ); vVars = Vec_IntAlloc( 100 ); Gia_ManForEachObj( p, pObj, i ) if ( Gia_ObjIsCand(pObj) && Gia_ObjRefNum(p, pObj) >= nFanLim ) Vec_IntPush( vVars, i ); ABC_FREE( p->pRefs ); return vVars; } /**Function************************************************************* Synopsis [Transfers attributes from the original one to the final one.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Int_t * Gia_ManTransfer( Gia_Man_t * pAig, Gia_Man_t * pCof, Gia_Man_t * pNew, Vec_Int_t * vSigs ) { Vec_Int_t * vSigsNew; Gia_Obj_t * pObj, * pObjF; int i; vSigsNew = Vec_IntAlloc( 100 ); Gia_ManForEachObjVec( vSigs, pAig, pObj, i ) { assert( Gia_ObjIsCand(pObj) ); pObjF = Gia_ManObj( pCof, Abc_Lit2Var(pObj->Value) ); if ( pObjF->Value && ~pObjF->Value ) Vec_IntPushUnique( vSigsNew, Abc_Lit2Var(pObjF->Value) ); } return vSigsNew; } /**Function************************************************************* Synopsis [Cofactors selected variables (should be in reverse topo order).] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Gia_Man_t * Gia_ManDupCofAllInt( Gia_Man_t * p, Vec_Int_t * vSigs, int fVerbose ) { Vec_Int_t * vSigsNew, * vTemp; Gia_Man_t * pAig, * pCof, * pNew; int iVar; if ( fVerbose ) { printf( "Cofactoring %d signals.\n", Vec_IntSize(vSigs) ); Gia_ManPrintStats( p, NULL ); } if ( Vec_IntSize( vSigs ) > 200 ) { printf( "Too many signals to cofactor.\n" ); return NULL; } pAig = Gia_ManDup( p ); vSigsNew = Vec_IntDup( vSigs ); while ( Vec_IntSize(vSigsNew) > 0 ) { Vec_IntSort( vSigsNew, 0 ); iVar = Vec_IntPop( vSigsNew ); // Gia_ManCreateRefs( pAig ); // printf( "ref count = %d\n", Gia_ObjRefNum( pAig, Gia_ManObj(pAig, iVar) ) ); // ABC_FREE( pAig->pRefs ); pCof = Gia_ManDupCofInt( pAig, iVar ); pNew = Gia_ManCleanup( pCof ); vSigsNew = Gia_ManTransfer( pAig, pCof, pNew, vTemp = vSigsNew ); Vec_IntFree( vTemp ); Gia_ManStop( pAig ); Gia_ManStop( pCof ); pAig = pNew; if ( fVerbose ) printf( "Cofactored variable %d.\n", iVar ); if ( fVerbose ) Gia_ManPrintStats( pAig, NULL ); } Vec_IntFree( vSigsNew ); return pAig; } /**Function************************************************************* Synopsis [Cofactors all variables whose fanout is higher than this.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Gia_Man_t * Gia_ManDupCofAll( Gia_Man_t * p, int nFanLim, int fVerbose ) { Gia_Man_t * pNew; Vec_Int_t * vSigs = Gia_ManCofVars( p, nFanLim ); pNew = Gia_ManDupCofAllInt( p, vSigs, fVerbose ); Vec_IntFree( vSigs ); return pNew; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END