| /**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 <math.h> |
| #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 |
| |
