| /**CFile**************************************************************** |
| |
| FileName [gia.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Scalable AIG package.] |
| |
| Synopsis [] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "gia.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| /* |
| The code is based on the paper by F. A. Aloul, I. L. Markov, and K. A. Sakallah. |
| "FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic", Proc. GLSVLSI�03. |
| http://www.eecs.umich.edu/~imarkov/pubs/conf/glsvlsi03-force.pdf |
| */ |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| typedef struct Frc_Obj_t_ Frc_Obj_t; |
| struct Frc_Obj_t_ |
| { |
| unsigned fCi : 1; // terminal node CI |
| unsigned fCo : 1; // terminal node CO |
| unsigned fMark0 : 1; // first user-controlled mark |
| unsigned fMark1 : 1; // second user-controlled mark |
| unsigned nFanins : 28; // the number of fanins |
| unsigned nFanouts; // the number of fanouts |
| unsigned iFanout; // the current number of fanouts |
| int hHandle; // the handle of the node |
| int pPlace; // the placement of each node |
| union { |
| float fEdgeCenter; // center-of-gravity of the edge |
| unsigned iFanin; |
| }; |
| int Fanios[0]; // the array of fanins/fanouts |
| }; |
| |
| typedef struct Frc_Man_t_ Frc_Man_t; |
| struct Frc_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 nRegs; // the number of registers |
| int * pObjData; // the array containing data for objects |
| int nObjData; // the size of array to store the logic network |
| int fVerbose; // verbose output flag |
| int nCutCur; // current cut |
| int nCutMax; // max cut seen |
| }; |
| |
| static inline int Frc_ManRegNum( Frc_Man_t * p ) { return p->nRegs; } |
| static inline int Frc_ManCiNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCis); } |
| static inline int Frc_ManCoNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCos); } |
| static inline int Frc_ManPiNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCis) - p->nRegs; } |
| static inline int Frc_ManPoNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCos) - p->nRegs; } |
| static inline int Frc_ManObjNum( Frc_Man_t * p ) { return p->nObjs; } |
| static inline int Frc_ManNodeNum( Frc_Man_t * p ) { return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos); } |
| |
| static inline Frc_Obj_t * Frc_ManObj( Frc_Man_t * p, int hHandle ) { return (Frc_Obj_t *)(p->pObjData + hHandle); } |
| static inline Frc_Obj_t * Frc_ManCi( Frc_Man_t * p, int i ) { return Frc_ManObj( p, Vec_IntEntry(p->vCis,i) ); } |
| static inline Frc_Obj_t * Frc_ManCo( Frc_Man_t * p, int i ) { return Frc_ManObj( p, Vec_IntEntry(p->vCos,i) ); } |
| |
| static inline int Frc_ObjIsTerm( Frc_Obj_t * pObj ) { return pObj->fCi || pObj->fCo; } |
| static inline int Frc_ObjIsCi( Frc_Obj_t * pObj ) { return pObj->fCi; } |
| static inline int Frc_ObjIsCo( Frc_Obj_t * pObj ) { return pObj->fCo; } |
| static inline int Frc_ObjIsPi( Frc_Obj_t * pObj ) { return pObj->fCi && pObj->nFanins == 0; } |
| static inline int Frc_ObjIsPo( Frc_Obj_t * pObj ) { return pObj->fCo && pObj->nFanouts == 0; } |
| static inline int Frc_ObjIsNode( Frc_Obj_t * pObj ) { return!Frc_ObjIsTerm(pObj) && pObj->nFanins > 0; } |
| static inline int Frc_ObjIsConst0( Frc_Obj_t * pObj ) { return!Frc_ObjIsTerm(pObj) && pObj->nFanins == 0; } |
| |
| static inline int Frc_ObjSize( Frc_Obj_t * pObj ) { return sizeof(Frc_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; } |
| static inline int Frc_ObjFaninNum( Frc_Obj_t * pObj ) { return pObj->nFanins; } |
| static inline int Frc_ObjFanoutNum( Frc_Obj_t * pObj ) { return pObj->nFanouts; } |
| static inline Frc_Obj_t * Frc_ObjFanin( Frc_Obj_t * pObj, int i ) { return (Frc_Obj_t *)(((int *)pObj) - pObj->Fanios[i]); } |
| static inline Frc_Obj_t * Frc_ObjFanout( Frc_Obj_t * pObj, int i ) { return (Frc_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); } |
| |
| #define Frc_ManForEachObj( p, pObj, i ) \ |
| for ( i = 0; (i < p->nObjData) && (pObj = Frc_ManObj(p,i)); i += Frc_ObjSize(pObj) ) |
| #define Frc_ManForEachObjVec( vVec, p, pObj, i ) \ |
| for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Frc_ManObj(p, Vec_IntEntry(vVec,i))); i++ ) |
| |
| #define Frc_ManForEachNode( p, pObj, i ) \ |
| for ( i = 0; (i < p->nObjData) && (pObj = Frc_ManObj(p,i)); i += Frc_ObjSize(pObj) ) if ( Frc_ObjIsTerm(pObj) ) {} else |
| #define Frc_ManForEachCi( p, pObj, i ) \ |
| for ( i = 0; (i < Vec_IntSize(p->vCis)) && (pObj = Frc_ManObj(p,Vec_IntEntry(p->vCis,i))); i++ ) |
| #define Frc_ManForEachCo( p, pObj, i ) \ |
| for ( i = 0; (i < Vec_IntSize(p->vCos)) && (pObj = Frc_ManObj(p,Vec_IntEntry(p->vCos,i))); i++ ) |
| |
| #define Frc_ObjForEachFanin( pObj, pNext, i ) \ |
| for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Frc_ObjFanin(pObj,i)); i++ ) |
| #define Frc_ObjForEachFaninReverse( pObj, pNext, i ) \ |
| for ( i = (int)pObj->nFanins - 1; (i >= 0) && (pNext = Frc_ObjFanin(pObj,i)); i-- ) |
| #define Frc_ObjForEachFanout( pObj, pNext, i ) \ |
| for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Frc_ObjFanout(pObj,i)); i++ ) |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates fanin/fanout pair.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ObjAddFanin( Frc_Obj_t * pObj, Frc_Obj_t * pFanin ) |
| { |
| assert( pObj->iFanin < pObj->nFanins ); |
| assert( pFanin->iFanout < pFanin->nFanouts ); |
| pFanin->Fanios[pFanin->nFanins + pFanin->iFanout++] = |
| pObj->Fanios[pObj->iFanin++] = pObj->hHandle - pFanin->hHandle; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates logic network isomorphic to the given AIG.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Frc_Man_t * Frc_ManStartSimple( Gia_Man_t * pGia ) |
| { |
| Frc_Man_t * p; |
| Frc_Obj_t * pObjLog, * pFanLog; |
| Gia_Obj_t * pObj;//, * pObjRi, * pObjRo; |
| int i, nNodes, hHandle = 0; |
| // prepare the AIG |
| Gia_ManCreateRefs( pGia ); |
| // create logic network |
| p = ABC_CALLOC( Frc_Man_t, 1 ); |
| p->pGia = pGia; |
| p->nRegs = Gia_ManRegNum(pGia); |
| p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) ); |
| p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) ); |
| p->nObjData = (sizeof(Frc_Obj_t) / 4) * Gia_ManObjNum(pGia) + 2 * (2 * Gia_ManAndNum(pGia) + Gia_ManCoNum(pGia)); |
| p->pObjData = ABC_CALLOC( int, p->nObjData ); |
| // create constant node |
| Gia_ManConst0(pGia)->Value = hHandle; |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 0; |
| pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) ); |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| nNodes = 1; |
| p->nObjs++; |
| // create the PIs |
| Gia_ManForEachCi( pGia, pObj, i ) |
| { |
| // create PI object |
| pObj->Value = hHandle; |
| Vec_IntPush( p->vCis, hHandle ); |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 0; |
| pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj ); |
| pObjLog->fCi = 0; |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| p->nObjs++; |
| } |
| // create internal nodes |
| Gia_ManForEachAnd( pGia, pObj, i ) |
| { |
| assert( Gia_ObjRefNum( pGia, pObj ) > 0 ); |
| // create node object |
| pObj->Value = hHandle; |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 2; |
| pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj ); |
| // add fanins |
| pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) ); |
| Frc_ObjAddFanin( pObjLog, pFanLog ); |
| pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin1(pObj)) ); |
| Frc_ObjAddFanin( pObjLog, pFanLog ); |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| nNodes++; |
| p->nObjs++; |
| } |
| // create the POs |
| Gia_ManForEachCo( pGia, pObj, i ) |
| { |
| // create PO object |
| pObj->Value = hHandle; |
| Vec_IntPush( p->vCos, hHandle ); |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 1; |
| pObjLog->nFanouts = 0; |
| pObjLog->fCo = 1; |
| // add fanins |
| pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) ); |
| Frc_ObjAddFanin( pObjLog, pFanLog ); |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| p->nObjs++; |
| } |
| // connect registers |
| // Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i ) |
| // Frc_ObjAddFanin( Frc_ManObj(p,Gia_ObjValue(pObjRo)), Frc_ManObj(p,Gia_ObjValue(pObjRi)) ); |
| assert( nNodes == Frc_ManNodeNum(p) ); |
| assert( hHandle == p->nObjData ); |
| if ( hHandle != p->nObjData ) |
| printf( "Frc_ManStartSimple(): Fatal error in internal representation.\n" ); |
| // make sure the fanin/fanout counters are correct |
| Gia_ManForEachObj( pGia, pObj, i ) |
| { |
| if ( !~Gia_ObjValue(pObj) ) |
| continue; |
| pObjLog = Frc_ManObj( p, Gia_ObjValue(pObj) ); |
| assert( pObjLog->nFanins == pObjLog->iFanin ); |
| assert( pObjLog->nFanouts == pObjLog->iFanout ); |
| pObjLog->iFanin = pObjLog->iFanout = 0; |
| } |
| ABC_FREE( pGia->pRefs ); |
| return p; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collect the fanin IDs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManCollectSuper_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit ) |
| { |
| if ( pObj->fMark1 ) |
| return; |
| pObj->fMark1 = 1; |
| Vec_IntPush( vVisit, Gia_ObjId(p, pObj) ); |
| if ( pObj->fMark0 ) |
| { |
| Vec_IntPush( vSuper, Gia_ObjId(p, pObj) ); |
| return; |
| } |
| assert( Gia_ObjIsAnd(pObj) ); |
| Frc_ManCollectSuper_rec( p, Gia_ObjFanin0(pObj), vSuper, vVisit ); |
| Frc_ManCollectSuper_rec( p, Gia_ObjFanin1(pObj), vSuper, vVisit ); |
| |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collect the fanin IDs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManCollectSuper( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit ) |
| { |
| int Entry, i; |
| Vec_IntClear( vSuper ); |
| Vec_IntClear( vVisit ); |
| assert( pObj->fMark0 == 1 ); |
| pObj->fMark0 = 0; |
| Frc_ManCollectSuper_rec( p, pObj, vSuper, vVisit ); |
| pObj->fMark0 = 1; |
| Vec_IntForEachEntry( vVisit, Entry, i ) |
| Gia_ManObj(p, Entry)->fMark1 = 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Assigns references while removing the MUX/XOR ones.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManCreateRefsSpecial( Gia_Man_t * p ) |
| { |
| Gia_Obj_t * pObj, * pFan0, * pFan1; |
| Gia_Obj_t * pObjC, * pObjD0, * pObjD1; |
| int i; |
| assert( p->pRefs == NULL ); |
| Gia_ManCleanMark0( p ); |
| Gia_ManCreateRefs( p ); |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| assert( pObj->fMark0 == 0 ); |
| pFan0 = Gia_ObjFanin0(pObj); |
| pFan1 = Gia_ObjFanin1(pObj); |
| // skip nodes whose fanins are PIs or are already marked |
| if ( Gia_ObjIsCi(pFan0) || pFan0->fMark0 || |
| Gia_ObjIsCi(pFan1) || pFan1->fMark0 ) |
| continue; |
| // skip nodes that are not MUX type |
| if ( !Gia_ObjIsMuxType(pObj) ) |
| continue; |
| // the node is MUX type, mark it and its fanins |
| pObj->fMark0 = 1; |
| pFan0->fMark0 = 1; |
| pFan1->fMark0 = 1; |
| // deref the control |
| pObjC = Gia_ObjRecognizeMux( pObj, &pObjD1, &pObjD0 ); |
| Gia_ObjRefDec( p, Gia_Regular(pObjC) ); |
| if ( Gia_Regular(pObjD0) == Gia_Regular(pObjD1) ) |
| Gia_ObjRefDec( p, Gia_Regular(pObjD0) ); |
| } |
| Gia_ManForEachAnd( p, pObj, i ) |
| assert( Gia_ObjRefNum(p, pObj) > 0 ); |
| Gia_ManCleanMark0( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Assigns references while removing the MUX/XOR ones.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManTransformRefs( Gia_Man_t * p, int * pnObjs, int * pnFanios ) |
| { |
| Vec_Int_t * vSuper, * vVisit; |
| Gia_Obj_t * pObj, * pFanin; |
| int i, k, Counter; |
| assert( p->pRefs != NULL ); |
| |
| // mark nodes to be used in the logic network |
| Gia_ManCleanMark0( p ); |
| Gia_ManConst0(p)->fMark0 = 1; |
| // mark the inputs |
| Gia_ManForEachCi( p, pObj, i ) |
| pObj->fMark0 = 1; |
| // mark those nodes that have ref count more than 1 |
| Gia_ManForEachAnd( p, pObj, i ) |
| pObj->fMark0 = (Gia_ObjRefNum(p, pObj) > 1); |
| // mark the output drivers |
| Gia_ManForEachCoDriver( p, pObj, i ) |
| pObj->fMark0 = 1; |
| |
| // count the number of nodes |
| Counter = 0; |
| Gia_ManForEachObj( p, pObj, i ) |
| Counter += pObj->fMark0; |
| *pnObjs = Counter + Gia_ManCoNum(p); |
| |
| // reset the references |
| ABC_FREE( p->pRefs ); |
| p->pRefs = ABC_CALLOC( int, Gia_ManObjNum(p) ); |
| // reference from internal nodes |
| Counter = 0; |
| vSuper = Vec_IntAlloc( 100 ); |
| vVisit = Vec_IntAlloc( 100 ); |
| Gia_ManCleanMark1( p ); |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| if ( pObj->fMark0 == 0 ) |
| continue; |
| Frc_ManCollectSuper( p, pObj, vSuper, vVisit ); |
| Gia_ManForEachObjVec( vSuper, p, pFanin, k ) |
| { |
| assert( pFanin->fMark0 ); |
| Gia_ObjRefInc( p, pFanin ); |
| } |
| Counter += Vec_IntSize( vSuper ); |
| } |
| Gia_ManCheckMark1( p ); |
| Vec_IntFree( vSuper ); |
| Vec_IntFree( vVisit ); |
| // reference from outputs |
| Gia_ManForEachCoDriver( p, pObj, i ) |
| { |
| assert( pObj->fMark0 ); |
| Gia_ObjRefInc( p, pObj ); |
| } |
| *pnFanios = Counter + Gia_ManCoNum(p); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates logic network isomorphic to the given AIG.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Frc_Man_t * Frc_ManStart( Gia_Man_t * pGia ) |
| { |
| Frc_Man_t * p; |
| Frc_Obj_t * pObjLog, * pFanLog; |
| Gia_Obj_t * pObj, * pFanin;//, * pObjRi, * pObjRo; |
| Vec_Int_t * vSuper, * vVisit; |
| int nObjs, nFanios, nNodes = 0; |
| int i, k, hHandle = 0; |
| // prepare the AIG |
| // Gia_ManCreateRefs( pGia ); |
| Frc_ManCreateRefsSpecial( pGia ); |
| Frc_ManTransformRefs( pGia, &nObjs, &nFanios ); |
| Gia_ManFillValue( pGia ); |
| // create logic network |
| p = ABC_CALLOC( Frc_Man_t, 1 ); |
| p->pGia = pGia; |
| p->nRegs = Gia_ManRegNum(pGia); |
| p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) ); |
| p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) ); |
| p->nObjData = (sizeof(Frc_Obj_t) / 4) * nObjs + 2 * nFanios; |
| p->pObjData = ABC_CALLOC( int, p->nObjData ); |
| // create constant node |
| Gia_ManConst0(pGia)->Value = hHandle; |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 0; |
| pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) ); |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| nNodes++; |
| p->nObjs++; |
| // create the PIs |
| Gia_ManForEachCi( pGia, pObj, i ) |
| { |
| // create PI object |
| pObj->Value = hHandle; |
| Vec_IntPush( p->vCis, hHandle ); |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 0; |
| pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj ); |
| pObjLog->fCi = 1; |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| p->nObjs++; |
| } |
| // create internal nodes |
| vSuper = Vec_IntAlloc( 100 ); |
| vVisit = Vec_IntAlloc( 100 ); |
| Gia_ManForEachAnd( pGia, pObj, i ) |
| { |
| if ( pObj->fMark0 == 0 ) |
| { |
| assert( Gia_ObjRefNum( pGia, pObj ) == 0 ); |
| continue; |
| } |
| assert( Gia_ObjRefNum( pGia, pObj ) > 0 ); |
| Frc_ManCollectSuper( pGia, pObj, vSuper, vVisit ); |
| // create node object |
| pObj->Value = hHandle; |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = Vec_IntSize( vSuper ); |
| pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj ); |
| // add fanins |
| Gia_ManForEachObjVec( vSuper, pGia, pFanin, k ) |
| { |
| pFanLog = Frc_ManObj( p, Gia_ObjValue(pFanin) ); |
| Frc_ObjAddFanin( pObjLog, pFanLog ); |
| } |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| nNodes++; |
| p->nObjs++; |
| } |
| Vec_IntFree( vSuper ); |
| Vec_IntFree( vVisit ); |
| // create the POs |
| Gia_ManForEachCo( pGia, pObj, i ) |
| { |
| // create PO object |
| pObj->Value = hHandle; |
| Vec_IntPush( p->vCos, hHandle ); |
| pObjLog = Frc_ManObj( p, hHandle ); |
| pObjLog->hHandle = hHandle; |
| pObjLog->nFanins = 1; |
| pObjLog->nFanouts = 0; |
| pObjLog->fCo = 1; |
| // add fanins |
| pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) ); |
| Frc_ObjAddFanin( pObjLog, pFanLog ); |
| // count objects |
| hHandle += Frc_ObjSize( pObjLog ); |
| p->nObjs++; |
| } |
| // connect registers |
| // Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i ) |
| // Frc_ObjAddFanin( Frc_ManObj(p,Gia_ObjValue(pObjRo)), Frc_ManObj(p,Gia_ObjValue(pObjRi)) ); |
| Gia_ManCleanMark0( pGia ); |
| assert( nNodes == Frc_ManNodeNum(p) ); |
| assert( nObjs == p->nObjs ); |
| assert( hHandle == p->nObjData ); |
| if ( hHandle != p->nObjData ) |
| printf( "Frc_ManStart(): Fatal error in internal representation.\n" ); |
| // make sure the fanin/fanout counters are correct |
| Gia_ManForEachObj( pGia, pObj, i ) |
| { |
| if ( !~Gia_ObjValue(pObj) ) |
| continue; |
| pObjLog = Frc_ManObj( p, Gia_ObjValue(pObj) ); |
| assert( pObjLog->nFanins == pObjLog->iFanin ); |
| assert( pObjLog->nFanouts == pObjLog->iFanout ); |
| pObjLog->iFanin = pObjLog->iFanout = 0; |
| } |
| ABC_FREE( pGia->pRefs ); |
| return p; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates logic network isomorphic to the given AIG.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManPrintStats( Frc_Man_t * p ) |
| { |
| // if ( p->pName ) |
| // printf( "%8s : ", p->pName ); |
| printf( "i/o =%7d/%7d ", Frc_ManPiNum(p), Frc_ManPoNum(p) ); |
| if ( Frc_ManRegNum(p) ) |
| printf( "ff =%7d ", Frc_ManRegNum(p) ); |
| printf( "node =%8d ", Frc_ManNodeNum(p) ); |
| printf( "obj =%8d ", Frc_ManObjNum(p) ); |
| // printf( "lev =%5d ", Frc_ManLevelNum(p) ); |
| // printf( "cut =%5d ", Frc_ManCrossCut(p) ); |
| printf( "mem =%5.2f MB", 4.0*p->nObjData/(1<<20) ); |
| // printf( "obj =%5d ", Frc_ManObjNum(p) ); |
| printf( "\n" ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates logic network isomorphic to the given AIG.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManStop( Frc_Man_t * p ) |
| { |
| Vec_IntFree( p->vCis ); |
| Vec_IntFree( p->vCos ); |
| ABC_FREE( p->pObjData ); |
| ABC_FREE( p ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes cross cut size for the given order of POs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Frc_ManCrossCut_rec( Frc_Man_t * p, Frc_Obj_t * pObj ) |
| { |
| assert( pObj->iFanout > 0 ); |
| if ( pObj->iFanout-- == pObj->nFanouts ) |
| { |
| Frc_Obj_t * pFanin; |
| int i; |
| p->nCutCur++; |
| p->nCutMax = Abc_MaxInt( p->nCutMax, p->nCutCur ); |
| if ( !Frc_ObjIsCi(pObj) ) |
| Frc_ObjForEachFanin( pObj, pFanin, i ) |
| p->nCutCur -= Frc_ManCrossCut_rec( p, pFanin ); |
| } |
| return pObj->iFanout == 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes cross cut size for the given order of POs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Frc_ManCrossCut2_rec( Frc_Man_t * p, Frc_Obj_t * pObj ) |
| { |
| assert( pObj->iFanout > 0 ); |
| if ( pObj->iFanout-- == pObj->nFanouts ) |
| { |
| Frc_Obj_t * pFanin; |
| int i; |
| p->nCutCur++; |
| p->nCutMax = Abc_MaxInt( p->nCutMax, p->nCutCur ); |
| if ( !Frc_ObjIsCi(pObj) ) |
| Frc_ObjForEachFaninReverse( pObj, pFanin, i ) |
| p->nCutCur -= Frc_ManCrossCut2_rec( p, pFanin ); |
| } |
| return pObj->iFanout == 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes cross cut size for the given order of POs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Frc_ManCrossCut( Frc_Man_t * p, Vec_Int_t * vOrder, int fReverse ) |
| { |
| Frc_Obj_t * pObj; |
| int i; |
| assert( Vec_IntSize(vOrder) == Frc_ManCoNum(p) ); |
| p->nCutCur = 0; |
| p->nCutMax = 0; |
| Frc_ManForEachObj( p, pObj, i ) |
| pObj->iFanout = pObj->nFanouts; |
| Frc_ManForEachObjVec( vOrder, p, pObj, i ) |
| { |
| assert( Frc_ObjIsCo(pObj) ); |
| if ( fReverse ) |
| p->nCutCur -= Frc_ManCrossCut2_rec( p, Frc_ObjFanin(pObj,0) ); |
| else |
| p->nCutCur -= Frc_ManCrossCut_rec( p, Frc_ObjFanin(pObj,0) ); |
| } |
| assert( p->nCutCur == 0 ); |
| // Frc_ManForEachObj( p, pObj, i ) |
| // assert( pObj->iFanout == 0 ); |
| return p->nCutMax; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects CO handles.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Frc_ManCollectCos( Frc_Man_t * p ) |
| { |
| Vec_Int_t * vCoOrder; |
| Frc_Obj_t * pObj; |
| int i; |
| vCoOrder = Vec_IntAlloc( Frc_ManCoNum(p) ); |
| Frc_ManForEachCo( p, pObj, i ) |
| Vec_IntPush( vCoOrder, pObj->hHandle ); |
| return vCoOrder; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes cross cut size for the given order of POs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManCrossCutTest( Frc_Man_t * p, Vec_Int_t * vOrderInit ) |
| { |
| Vec_Int_t * vOrder; |
| // abctime clk = Abc_Clock(); |
| vOrder = vOrderInit? vOrderInit : Frc_ManCollectCos( p ); |
| printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 0 ) ); |
| printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 1 ) ); |
| Vec_IntReverseOrder( vOrder ); |
| printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 0 ) ); |
| printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 1 ) ); |
| Vec_IntReverseOrder( vOrder ); |
| if ( vOrder != vOrderInit ) |
| Vec_IntFree( vOrder ); |
| // ABC_PRT( "Time", Abc_Clock() - clk ); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Generates random placement.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManPlaceRandom( Frc_Man_t * p ) |
| { |
| Frc_Obj_t * pThis; |
| int * pPlacement; |
| int i, h, Temp, iNext, Counter; |
| pPlacement = ABC_ALLOC( int, p->nObjs ); |
| for ( i = 0; i < p->nObjs; i++ ) |
| pPlacement[i] = i; |
| for ( i = 0; i < p->nObjs; i++ ) |
| { |
| iNext = Gia_ManRandom( 0 ) % p->nObjs; |
| Temp = pPlacement[i]; |
| pPlacement[i] = pPlacement[iNext]; |
| pPlacement[iNext] = Temp; |
| } |
| Counter = 0; |
| Frc_ManForEachObj( p, pThis, h ) |
| pThis->pPlace = pPlacement[Counter++]; |
| ABC_FREE( pPlacement ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Shuffles array of random integers.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManArrayShuffle( Vec_Int_t * vArray ) |
| { |
| int i, iNext, Temp; |
| for ( i = 0; i < vArray->nSize; i++ ) |
| { |
| iNext = Gia_ManRandom( 0 ) % vArray->nSize; |
| Temp = vArray->pArray[i]; |
| vArray->pArray[i] = vArray->pArray[iNext]; |
| vArray->pArray[iNext] = Temp; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes cross cut size for the given order of POs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManPlaceDfs_rec( Frc_Man_t * p, Frc_Obj_t * pObj, int * piPlace ) |
| { |
| assert( pObj->iFanout > 0 ); |
| if ( pObj->iFanout-- == pObj->nFanouts ) |
| { |
| Frc_Obj_t * pFanin; |
| int i; |
| if ( !Frc_ObjIsCi(pObj) ) |
| Frc_ObjForEachFanin( pObj, pFanin, i ) |
| Frc_ManPlaceDfs_rec( p, pFanin, piPlace ); |
| pObj->pPlace = (*piPlace)++; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Generates DFS placement.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManPlaceDfs( Frc_Man_t * p, Vec_Int_t * vCoOrder ) |
| { |
| Frc_Obj_t * pObj; |
| int i, nPlaces = 0; |
| Frc_ManForEachObj( p, pObj, i ) |
| { |
| pObj->iFanout = pObj->nFanouts; |
| if ( pObj->nFanouts == 0 && !Frc_ObjIsCo(pObj) ) |
| pObj->pPlace = nPlaces++; |
| } |
| Frc_ManForEachObjVec( vCoOrder, p, pObj, i ) |
| { |
| assert( Frc_ObjIsCo(pObj) ); |
| Frc_ManPlaceDfs_rec( p, Frc_ObjFanin(pObj,0), &nPlaces ); |
| pObj->pPlace = nPlaces++; |
| } |
| assert( nPlaces == p->nObjs ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Generates DFS placement by trying both orders.] |
| |
| Description [Returns the cross cut size of the best order. ] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Frc_ManPlaceDfsBoth( Frc_Man_t * p, Vec_Int_t * vCoOrder, int * piCutSize2 ) |
| { |
| int nCutStart1, nCutStart2; |
| nCutStart1 = Frc_ManCrossCut( p, vCoOrder, 0 ); |
| Vec_IntReverseOrder( vCoOrder ); |
| nCutStart2 = Frc_ManCrossCut( p, vCoOrder, 0 ); |
| if ( nCutStart1 <= nCutStart2 ) |
| { |
| Vec_IntReverseOrder( vCoOrder ); // undo |
| Frc_ManPlaceDfs( p, vCoOrder ); |
| *piCutSize2 = nCutStart2; |
| return nCutStart1; |
| } |
| else |
| { |
| Frc_ManPlaceDfs( p, vCoOrder ); |
| Vec_IntReverseOrder( vCoOrder ); // undo |
| *piCutSize2 = nCutStart1; |
| return nCutStart2; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs iterative refinement of the given placement.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_ManPlacementRefine( Frc_Man_t * p, int nIters, int fVerbose ) |
| { |
| int fRandomize = 0; |
| Vec_Int_t * vCoOrder; |
| Frc_Obj_t * pThis, * pNext; |
| double CostThis, CostPrev; |
| float * pVertX, VertX; |
| int * pPermX, * pHandles; |
| int k, h, Iter, iMinX, iMaxX, Counter, nCutStart, nCutCur, nCutCur2, nCutPrev; |
| abctime clk = Abc_Clock(), clk2, clk2Total = 0; |
| // create starting one-dimensional placement |
| vCoOrder = Frc_ManCollectCos( p ); |
| if ( fRandomize ) |
| Frc_ManArrayShuffle( vCoOrder ); |
| nCutStart = Frc_ManPlaceDfsBoth( p, vCoOrder, &nCutCur2 ); |
| // refine placement |
| CostPrev = 0.0; |
| nCutPrev = nCutStart; |
| pHandles = ABC_ALLOC( int, p->nObjs ); |
| pVertX = ABC_ALLOC( float, p->nObjs ); |
| for ( Iter = 0; Iter < nIters; Iter++ ) |
| { |
| // compute centers of hyperedges |
| CostThis = 0.0; |
| Frc_ManForEachObj( p, pThis, h ) |
| { |
| iMinX = iMaxX = pThis->pPlace; |
| Frc_ObjForEachFanout( pThis, pNext, k ) |
| { |
| iMinX = Abc_MinInt( iMinX, pNext->pPlace ); |
| iMaxX = Abc_MaxInt( iMaxX, pNext->pPlace ); |
| } |
| pThis->fEdgeCenter = 0.5 * (iMaxX + iMinX); |
| CostThis += (iMaxX - iMinX); |
| } |
| // compute new centers of objects |
| Counter = 0; |
| Frc_ManForEachObj( p, pThis, h ) |
| { |
| VertX = pThis->fEdgeCenter; |
| Frc_ObjForEachFanin( pThis, pNext, k ) |
| VertX += pNext->fEdgeCenter; |
| pVertX[Counter] = VertX / (Frc_ObjFaninNum(pThis) + 1); |
| pHandles[Counter++] = h; |
| } |
| assert( Counter == Frc_ManObjNum(p) ); |
| // sort these numbers |
| clk2 = Abc_Clock(); |
| pPermX = Gia_SortFloats( pVertX, pHandles, p->nObjs ); |
| clk2Total += Abc_Clock() - clk2; |
| assert( pPermX == pHandles ); |
| Vec_IntClear( vCoOrder ); |
| for ( k = 0; k < p->nObjs; k++ ) |
| { |
| pThis = Frc_ManObj( p, pPermX[k] ); |
| pThis->pPlace = k; |
| if ( Frc_ObjIsCo(pThis) ) |
| Vec_IntPush( vCoOrder, pThis->hHandle ); |
| } |
| /* |
| printf( "Ordering of PIs:\n" ); |
| Frc_ManForEachCi( p, pThis, k ) |
| printf( "PI number = %7d. Object handle = %7d, Coordinate = %7d.\n", |
| k, pThis->hHandle, pThis->pPlace ); |
| */ |
| nCutCur = Frc_ManPlaceDfsBoth( p, vCoOrder, &nCutCur2 ); |
| // evaluate cost |
| if ( fVerbose ) |
| { |
| printf( "%2d : Span = %e ", Iter+1, CostThis ); |
| printf( "Cut = %6d (%5.2f %%) CutR = %6d ", nCutCur, 100.0*(nCutStart-nCutCur)/nCutStart, nCutCur2 ); |
| ABC_PRTn( "Total", Abc_Clock() - clk ); |
| ABC_PRT( "Sort", clk2Total ); |
| // Frc_ManCrossCutTest( p, vCoOrder ); |
| } |
| // if ( 1.0 * nCutPrev / nCutCur < 1.001 ) |
| // break; |
| nCutPrev = nCutCur; |
| } |
| ABC_FREE( pHandles ); |
| ABC_FREE( pVertX ); |
| Vec_IntFree( vCoOrder ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns 1 if all fanouts are COsw.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Frc_ObjFanoutsAreCos( Frc_Obj_t * pThis ) |
| { |
| Frc_Obj_t * pNext; |
| int i; |
| Frc_ObjForEachFanout( pThis, pNext, i ) |
| if ( !Frc_ObjIsCo(pNext) ) |
| return 0; |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the distances from the given set of objects.] |
| |
| Description [Returns one of the most distant objects.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Frc_DumpGraphIntoFile( Frc_Man_t * p ) |
| { |
| FILE * pFile; |
| Frc_Obj_t * pThis, * pNext; |
| int i, k, Counter = 0; |
| // assign numbers to CIs and internal nodes |
| Frc_ManForEachObj( p, pThis, i ) |
| { |
| if ( i && ((Frc_ObjIsCi(pThis) && !Frc_ObjFanoutsAreCos(pThis)) || Frc_ObjIsNode(pThis)) ) |
| pThis->iFanin = Counter++; |
| else |
| pThis->iFanin = ~0; |
| } |
| // assign numbers to all other nodes |
| pFile = fopen( "x\\large\\aig\\dg1.g", "w" ); |
| Frc_ManForEachObj( p, pThis, i ) |
| { |
| Frc_ObjForEachFanout( pThis, pNext, k ) |
| { |
| if ( ~pThis->iFanin && ~pNext->iFanin ) |
| fprintf( pFile, "%d %d\n", pThis->iFanin, pNext->iFanin ); |
| } |
| } |
| fclose( pFile ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Experiment with the FORCE algorithm.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void For_ManExperiment( Gia_Man_t * pGia, int nIters, int fClustered, int fVerbose ) |
| { |
| Frc_Man_t * p; |
| Gia_ManRandom( 1 ); |
| if ( fClustered ) |
| p = Frc_ManStart( pGia ); |
| else |
| p = Frc_ManStartSimple( pGia ); |
| // Frc_DumpGraphIntoFile( p ); |
| if ( fVerbose ) |
| Frc_ManPrintStats( p ); |
| // Frc_ManCrossCutTest( p, NULL ); |
| Frc_ManPlacementRefine( p, nIters, fVerbose ); |
| Frc_ManStop( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Experiment with the FORCE algorithm.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void For_ManFileExperiment() |
| { |
| FILE * pFile; |
| int * pBuffer; |
| int i, Size, Exp = 25; |
| abctime clk = Abc_Clock(); |
| int RetValue; |
| |
| Size = (1 << Exp); |
| printf( "2^%d machine words (%d bytes).\n", Exp, (int)sizeof(int) * Size ); |
| |
| pBuffer = ABC_ALLOC( int, Size ); |
| for ( i = 0; i < Size; i++ ) |
| pBuffer[i] = i; |
| ABC_PRT( "Fillup", Abc_Clock() - clk ); |
| |
| clk = Abc_Clock(); |
| pFile = fopen( "test.txt", "rb" ); |
| RetValue = fread( pBuffer, 1, sizeof(int) * Size, pFile ); |
| fclose( pFile ); |
| ABC_PRT( "Read ", Abc_Clock() - clk ); |
| |
| clk = Abc_Clock(); |
| pFile = fopen( "test.txt", "wb" ); |
| fwrite( pBuffer, 1, sizeof(int) * Size, pFile ); |
| fclose( pFile ); |
| ABC_PRT( "Write ", Abc_Clock() - clk ); |
| /* |
| 2^25 machine words (134217728 bytes). |
| Fillup = 0.06 sec |
| Read = 0.08 sec |
| Write = 1.81 sec |
| */ |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| ABC_NAMESPACE_IMPL_END |
| |
