| /**CFile**************************************************************** |
| |
| FileName [ivyFastMap.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [And-Inverter Graph package.] |
| |
| Synopsis [Fast FPGA mapping.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - May 11, 2006.] |
| |
| Revision [$Id: ivyFastMap.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "ivy.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #define IVY_INFINITY 10000 |
| |
| typedef struct Ivy_SuppMan_t_ Ivy_SuppMan_t; |
| struct Ivy_SuppMan_t_ |
| { |
| int nLimit; // the limit on the number of inputs |
| int nObjs; // the number of entries |
| int nSize; // size of each entry in bytes |
| char * pMem; // memory allocated |
| Vec_Vec_t * vLuts; // the array of nodes used in the mapping |
| }; |
| |
| typedef struct Ivy_Supp_t_ Ivy_Supp_t; |
| struct Ivy_Supp_t_ |
| { |
| char nSize; // the number of support nodes |
| char fMark; // multipurpose mask |
| char fMark2; // multipurpose mask |
| char fMark3; // multipurpose mask |
| int nRefs; // the number of references |
| short Delay; // the delay of the node |
| short DelayR; // the reverse delay of the node |
| int pArray[0]; // the support nodes |
| }; |
| |
| static inline Ivy_Supp_t * Ivy_ObjSupp( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| return (Ivy_Supp_t *)(((Ivy_SuppMan_t*)pAig->pData)->pMem + pObj->Id * ((Ivy_SuppMan_t*)pAig->pData)->nSize); |
| } |
| static inline Ivy_Supp_t * Ivy_ObjSuppStart( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSupp; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| pSupp->fMark = 0; |
| pSupp->Delay = 0; |
| pSupp->nSize = 1; |
| pSupp->pArray[0] = pObj->Id; |
| return pSupp; |
| } |
| |
| static void Ivy_FastMapPrint( Ivy_Man_t * pAig, int Delay, int Area, abctime Time, char * pStr ); |
| static int Ivy_FastMapDelay( Ivy_Man_t * pAig ); |
| static int Ivy_FastMapArea( Ivy_Man_t * pAig ); |
| static void Ivy_FastMapNode( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit ); |
| static void Ivy_FastMapNodeArea( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit ); |
| static int Ivy_FastMapMerge( Ivy_Supp_t * pSupp0, Ivy_Supp_t * pSupp1, Ivy_Supp_t * pSupp, int nLimit ); |
| static void Ivy_FastMapRequired( Ivy_Man_t * pAig, int Delay, int fSetInter ); |
| static void Ivy_FastMapRecover( Ivy_Man_t * pAig, int nLimit ); |
| static int Ivy_FastMapNodeDelay( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ); |
| static int Ivy_FastMapNodeAreaRefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ); |
| static int Ivy_FastMapNodeAreaDerefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ); |
| static void Ivy_FastMapNodeRecover( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld ); |
| static int Ivy_FastMapNodeRef( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ); |
| static int Ivy_FastMapNodeDeref( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ); |
| |
| |
| extern abctime s_MappingTime; |
| extern int s_MappingMem; |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast K-LUT mapping of the AIG.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapPerform( Ivy_Man_t * pAig, int nLimit, int fRecovery, int fVerbose ) |
| { |
| Ivy_SuppMan_t * pMan; |
| Ivy_Obj_t * pObj; |
| int i, Delay, Area; |
| abctime clk, clkTotal = Abc_Clock(); |
| // start the memory for supports |
| pMan = ABC_ALLOC( Ivy_SuppMan_t, 1 ); |
| memset( pMan, 0, sizeof(Ivy_SuppMan_t) ); |
| pMan->nLimit = nLimit; |
| pMan->nObjs = Ivy_ManObjIdMax(pAig) + 1; |
| pMan->nSize = sizeof(Ivy_Supp_t) + nLimit * sizeof(int); |
| pMan->pMem = (char *)ABC_ALLOC( char, pMan->nObjs * pMan->nSize ); |
| memset( pMan->pMem, 0, pMan->nObjs * pMan->nSize ); |
| pMan->vLuts = Vec_VecAlloc( 100 ); |
| pAig->pData = pMan; |
| clk = Abc_Clock(); |
| // set the PI mapping |
| Ivy_ObjSuppStart( pAig, Ivy_ManConst1(pAig) ); |
| Ivy_ManForEachPi( pAig, pObj, i ) |
| Ivy_ObjSuppStart( pAig, pObj ); |
| // iterate through all nodes in the topological order |
| Ivy_ManForEachNode( pAig, pObj, i ) |
| Ivy_FastMapNode( pAig, pObj, nLimit ); |
| // find the best arrival time and area |
| Delay = Ivy_FastMapDelay( pAig ); |
| Area = Ivy_FastMapArea(pAig); |
| if ( fVerbose ) |
| Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Delay oriented mapping: " ); |
| |
| // 2-1-2 (doing 2-1-2-1-2 improves 0.5%) |
| |
| if ( fRecovery ) |
| { |
| clk = Abc_Clock(); |
| Ivy_FastMapRequired( pAig, Delay, 0 ); |
| // remap the nodes |
| Ivy_FastMapRecover( pAig, nLimit ); |
| Delay = Ivy_FastMapDelay( pAig ); |
| Area = Ivy_FastMapArea(pAig); |
| if ( fVerbose ) |
| Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 2 : " ); |
| |
| clk = Abc_Clock(); |
| Ivy_FastMapRequired( pAig, Delay, 0 ); |
| // iterate through all nodes in the topological order |
| Ivy_ManForEachNode( pAig, pObj, i ) |
| Ivy_FastMapNodeArea( pAig, pObj, nLimit ); |
| Delay = Ivy_FastMapDelay( pAig ); |
| Area = Ivy_FastMapArea(pAig); |
| if ( fVerbose ) |
| Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 1 : " ); |
| |
| clk = Abc_Clock(); |
| Ivy_FastMapRequired( pAig, Delay, 0 ); |
| // remap the nodes |
| Ivy_FastMapRecover( pAig, nLimit ); |
| Delay = Ivy_FastMapDelay( pAig ); |
| Area = Ivy_FastMapArea(pAig); |
| if ( fVerbose ) |
| Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 2 : " ); |
| } |
| |
| |
| s_MappingTime = Abc_Clock() - clkTotal; |
| s_MappingMem = pMan->nObjs * pMan->nSize; |
| /* |
| { |
| Vec_Ptr_t * vNodes; |
| vNodes = Vec_PtrAlloc( 100 ); |
| Vec_VecForEachEntry( Ivy_Obj_t *, pMan->vLuts, pObj, i, k ) |
| Vec_PtrPush( vNodes, pObj ); |
| Ivy_ManShow( pAig, 0, vNodes ); |
| Vec_PtrFree( vNodes ); |
| } |
| */ |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Cleans memory used for decomposition.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapStop( Ivy_Man_t * pAig ) |
| { |
| Ivy_SuppMan_t * p = (Ivy_SuppMan_t *)pAig->pData; |
| Vec_VecFree( p->vLuts ); |
| ABC_FREE( p->pMem ); |
| ABC_FREE( p ); |
| pAig->pData = NULL; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints statistics.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapPrint( Ivy_Man_t * pAig, int Delay, int Area, abctime Time, char * pStr ) |
| { |
| printf( "%s : Delay = %3d. Area = %6d. ", pStr, Delay, Area ); |
| ABC_PRT( "Time", Time ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes delay after LUT mapping.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapDelay( Ivy_Man_t * pAig ) |
| { |
| Ivy_Supp_t * pSupp; |
| Ivy_Obj_t * pObj; |
| int i, DelayMax = 0; |
| Ivy_ManForEachPo( pAig, pObj, i ) |
| { |
| pObj = Ivy_ObjFanin0(pObj); |
| if ( !Ivy_ObjIsNode(pObj) ) |
| continue; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| if ( DelayMax < pSupp->Delay ) |
| DelayMax = pSupp->Delay; |
| } |
| return DelayMax; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area after mapping.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapArea_rec( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Vec_t * vLuts ) |
| { |
| Ivy_Supp_t * pSupp; |
| int i, Counter; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| // skip visited nodes and PIs |
| if ( pSupp->fMark || pSupp->nSize == 1 ) |
| return 0; |
| pSupp->fMark = 1; |
| // compute the area of this node |
| Counter = 0; |
| for ( i = 0; i < pSupp->nSize; i++ ) |
| Counter += Ivy_FastMapArea_rec( pAig, Ivy_ManObj(pAig, pSupp->pArray[i]), vLuts ); |
| // add the node to the array of LUTs |
| Vec_VecPush( vLuts, pSupp->Delay, pObj ); |
| return 1 + Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area after mapping.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapArea( Ivy_Man_t * pAig ) |
| { |
| Vec_Vec_t * vLuts; |
| Ivy_Obj_t * pObj; |
| int i, Counter = 0; |
| // get the array to store the nodes |
| vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts; |
| Vec_VecClear( vLuts ); |
| // explore starting from each node |
| Ivy_ManForEachPo( pAig, pObj, i ) |
| Counter += Ivy_FastMapArea_rec( pAig, Ivy_ObjFanin0(pObj), vLuts ); |
| // clean the marks |
| Ivy_ManForEachNode( pAig, pObj, i ) |
| Ivy_ObjSupp( pAig, pObj )->fMark = 0; |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast mapping for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_ObjIsNodeInt1( Ivy_Obj_t * pObj ) |
| { |
| return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) == 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast mapping for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_ObjIsNodeInt2( Ivy_Obj_t * pObj ) |
| { |
| return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) <= 2; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast mapping for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Vec_IntRemoveDup( int * pArray, int nSize ) |
| { |
| int i, k; |
| if ( nSize < 2 ) |
| return nSize; |
| for ( i = k = 1; i < nSize; i++ ) |
| if ( pArray[i] != pArray[i-1] ) |
| pArray[k++] = pArray[i]; |
| return k; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast mapping for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeArea2( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit ) |
| { |
| static int Store[32], StoreSize; |
| static char Supp0[16], Supp1[16]; |
| static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0; |
| static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1; |
| Ivy_Obj_t * pFanin0, * pFanin1; |
| Ivy_Supp_t * pSupp0, * pSupp1, * pSupp; |
| int RetValue, DelayOld; |
| assert( nLimit <= 32 ); |
| assert( Ivy_ObjIsNode(pObj) ); |
| // get the fanins |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| // get the supports |
| pSupp0 = Ivy_ObjSupp( pAig, pFanin0 ); |
| pSupp1 = Ivy_ObjSupp( pAig, pFanin1 ); |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->fMark == 0 ); |
| // get the old delay of the node |
| DelayOld = Ivy_FastMapNodeDelay(pAig, pObj); |
| assert( DelayOld <= pSupp->DelayR ); |
| // copy the current cut |
| memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize ); |
| StoreSize = pSupp->nSize; |
| // get the fanin support |
| if ( Ivy_ObjRefs(pFanin0) > 1 && pSupp0->Delay < pSupp->DelayR ) |
| { |
| pSupp0 = pTemp0; |
| pSupp0->nSize = 1; |
| pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj); |
| } |
| // get the fanin support |
| if ( Ivy_ObjRefs(pFanin1) > 1 && pSupp1->Delay < pSupp->DelayR ) |
| { |
| pSupp1 = pTemp1; |
| pSupp1->nSize = 1; |
| pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj); |
| } |
| // merge the cuts |
| if ( pSupp0->nSize < pSupp1->nSize ) |
| RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit ); |
| else |
| RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit ); |
| if ( !RetValue ) |
| { |
| pSupp->nSize = 2; |
| pSupp->pArray[0] = Ivy_ObjFaninId0(pObj); |
| pSupp->pArray[1] = Ivy_ObjFaninId1(pObj); |
| } |
| // check the resulting delay |
| pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj); |
| if ( pSupp->Delay > pSupp->DelayR ) |
| { |
| pSupp->nSize = StoreSize; |
| memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize ); |
| pSupp->Delay = DelayOld; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast mapping for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeArea( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit ) |
| { |
| static int Store[32], StoreSize; |
| static char Supp0[16], Supp1[16]; |
| static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0; |
| static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1; |
| Ivy_Obj_t * pFanin0, * pFanin1; |
| Ivy_Supp_t * pSupp0, * pSupp1, * pSupp; |
| int RetValue, DelayOld, RefsOld; |
| int AreaBef, AreaAft; |
| assert( nLimit <= 32 ); |
| assert( Ivy_ObjIsNode(pObj) ); |
| // get the fanins |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| // get the supports |
| pSupp0 = Ivy_ObjSupp( pAig, pFanin0 ); |
| pSupp1 = Ivy_ObjSupp( pAig, pFanin1 ); |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->fMark == 0 ); |
| |
| // get the area |
| if ( pSupp->nRefs == 0 ) |
| AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj ); |
| else |
| AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| // if ( AreaBef == 1 ) |
| // return; |
| |
| // deref the cut if the node is refed |
| if ( pSupp->nRefs != 0 ) |
| Ivy_FastMapNodeDeref( pAig, pObj ); |
| |
| // get the old delay of the node |
| DelayOld = Ivy_FastMapNodeDelay(pAig, pObj); |
| assert( DelayOld <= pSupp->DelayR ); |
| // copy the current cut |
| memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize ); |
| StoreSize = pSupp->nSize; |
| // get the fanin support |
| if ( Ivy_ObjRefs(pFanin0) > 2 && pSupp0->Delay < pSupp->DelayR ) |
| // if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results |
| { |
| pSupp0 = pTemp0; |
| pSupp0->nSize = 1; |
| pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj); |
| } |
| // get the fanin support |
| if ( Ivy_ObjRefs(pFanin1) > 2 && pSupp1->Delay < pSupp->DelayR ) |
| // if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR ) |
| { |
| pSupp1 = pTemp1; |
| pSupp1->nSize = 1; |
| pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj); |
| } |
| // merge the cuts |
| if ( pSupp0->nSize < pSupp1->nSize ) |
| RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit ); |
| else |
| RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit ); |
| if ( !RetValue ) |
| { |
| pSupp->nSize = 2; |
| pSupp->pArray[0] = Ivy_ObjFaninId0(pObj); |
| pSupp->pArray[1] = Ivy_ObjFaninId1(pObj); |
| } |
| |
| // check the resulting delay |
| pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj); |
| |
| RefsOld = pSupp->nRefs; pSupp->nRefs = 0; |
| AreaAft = Ivy_FastMapNodeAreaDerefed( pAig, pObj ); |
| pSupp->nRefs = RefsOld; |
| |
| if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR ) |
| // if ( pSupp->Delay > pSupp->DelayR ) |
| { |
| pSupp->nSize = StoreSize; |
| memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize ); |
| pSupp->Delay = DelayOld; |
| // printf( "-" ); |
| } |
| // else |
| // printf( "+" ); |
| |
| if ( pSupp->nRefs != 0 ) |
| Ivy_FastMapNodeRef( pAig, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs fast mapping for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNode( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit ) |
| { |
| Ivy_Supp_t * pSupp0, * pSupp1, * pSupp; |
| int fFaninParam = 2; |
| int RetValue; |
| assert( Ivy_ObjIsNode(pObj) ); |
| // get the supports |
| pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) ); |
| pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) ); |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| pSupp->fMark = 0; |
| // get the delays |
| if ( pSupp0->Delay == pSupp1->Delay ) |
| pSupp->Delay = (pSupp0->Delay == 0) ? pSupp0->Delay + 1: pSupp0->Delay; |
| else if ( pSupp0->Delay > pSupp1->Delay ) |
| { |
| pSupp->Delay = pSupp0->Delay; |
| pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) ); |
| pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj); |
| } |
| else // if ( pSupp0->Delay < pSupp1->Delay ) |
| { |
| pSupp->Delay = pSupp1->Delay; |
| pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) ); |
| pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj); |
| } |
| // merge the cuts |
| if ( pSupp0->nSize < pSupp1->nSize ) |
| RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit ); |
| else |
| RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit ); |
| if ( !RetValue ) |
| { |
| pSupp->Delay++; |
| if ( fFaninParam == 2 ) |
| { |
| pSupp->nSize = 2; |
| pSupp->pArray[0] = Ivy_ObjFaninId0(pObj); |
| pSupp->pArray[1] = Ivy_ObjFaninId1(pObj); |
| } |
| else if ( fFaninParam == 3 ) |
| { |
| Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB; |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| pSupp->nSize = 0; |
| // process the first fanin |
| if ( Ivy_ObjIsNodeInt1(pFanin0) ) |
| { |
| pFaninA = Ivy_ObjFanin0(pFanin0); |
| pFaninB = Ivy_ObjFanin1(pFanin0); |
| if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) ) |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0); |
| else |
| { |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA); |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB); |
| } |
| } |
| else |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0); |
| // process the second fanin |
| if ( Ivy_ObjIsNodeInt1(pFanin1) ) |
| { |
| pFaninA = Ivy_ObjFanin0(pFanin1); |
| pFaninB = Ivy_ObjFanin1(pFanin1); |
| if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) ) |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1); |
| else |
| { |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA); |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB); |
| } |
| } |
| else |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1); |
| // sort the fanins |
| Vec_IntSelectSort( pSupp->pArray, pSupp->nSize ); |
| pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize ); |
| assert( pSupp->pArray[0] < pSupp->pArray[1] ); |
| } |
| else if ( fFaninParam == 4 ) |
| { |
| Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB; |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| pSupp->nSize = 0; |
| // consider the case when exactly one of them is internal |
| if ( Ivy_ObjIsNodeInt1(pFanin0) ^ Ivy_ObjIsNodeInt1(pFanin1) ) |
| { |
| pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) ); |
| pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) ); |
| if ( Ivy_ObjIsNodeInt1(pFanin0) && pSupp0->nSize < nLimit ) |
| { |
| pSupp->Delay = IVY_MAX( pSupp0->Delay, pSupp1->Delay + 1 ); |
| pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) ); |
| pSupp1->pArray[0] = Ivy_ObjId(pFanin1); |
| // merge the cuts |
| RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit ); |
| assert( RetValue ); |
| assert( pSupp->nSize > 1 ); |
| return; |
| } |
| if ( Ivy_ObjIsNodeInt1(pFanin1) && pSupp1->nSize < nLimit ) |
| { |
| pSupp->Delay = IVY_MAX( pSupp1->Delay, pSupp0->Delay + 1 ); |
| pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) ); |
| pSupp0->pArray[0] = Ivy_ObjId(pFanin0); |
| // merge the cuts |
| RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit ); |
| assert( RetValue ); |
| assert( pSupp->nSize > 1 ); |
| return; |
| } |
| } |
| // process the first fanin |
| if ( Ivy_ObjIsNodeInt1(pFanin0) ) |
| { |
| pFaninA = Ivy_ObjFanin0(pFanin0); |
| pFaninB = Ivy_ObjFanin1(pFanin0); |
| if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) ) |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0); |
| else |
| { |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA); |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB); |
| } |
| } |
| else |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0); |
| // process the second fanin |
| if ( Ivy_ObjIsNodeInt1(pFanin1) ) |
| { |
| pFaninA = Ivy_ObjFanin0(pFanin1); |
| pFaninB = Ivy_ObjFanin1(pFanin1); |
| if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) ) |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1); |
| else |
| { |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA); |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB); |
| } |
| } |
| else |
| pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1); |
| // sort the fanins |
| Vec_IntSelectSort( pSupp->pArray, pSupp->nSize ); |
| pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize ); |
| assert( pSupp->pArray[0] < pSupp->pArray[1] ); |
| assert( pSupp->nSize > 1 ); |
| } |
| } |
| assert( pSupp->Delay > 0 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Merges two supports] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapMerge( Ivy_Supp_t * pSupp0, Ivy_Supp_t * pSupp1, Ivy_Supp_t * pSupp, int nLimit ) |
| { |
| int i, k, c; |
| assert( pSupp0->nSize >= pSupp1->nSize ); |
| // the case of the largest cut sizes |
| if ( pSupp0->nSize == nLimit && pSupp1->nSize == nLimit ) |
| { |
| for ( i = 0; i < pSupp0->nSize; i++ ) |
| if ( pSupp0->pArray[i] != pSupp1->pArray[i] ) |
| return 0; |
| for ( i = 0; i < pSupp0->nSize; i++ ) |
| pSupp->pArray[i] = pSupp0->pArray[i]; |
| pSupp->nSize = pSupp0->nSize; |
| return 1; |
| } |
| // the case when one of the cuts is the largest |
| if ( pSupp0->nSize == nLimit ) |
| { |
| for ( i = 0; i < pSupp1->nSize; i++ ) |
| { |
| for ( k = pSupp0->nSize - 1; k >= 0; k-- ) |
| if ( pSupp0->pArray[k] == pSupp1->pArray[i] ) |
| break; |
| if ( k == -1 ) // did not find |
| return 0; |
| } |
| for ( i = 0; i < pSupp0->nSize; i++ ) |
| pSupp->pArray[i] = pSupp0->pArray[i]; |
| pSupp->nSize = pSupp0->nSize; |
| return 1; |
| } |
| |
| // compare two cuts with different numbers |
| i = k = 0; |
| for ( c = 0; c < nLimit; c++ ) |
| { |
| if ( k == pSupp1->nSize ) |
| { |
| if ( i == pSupp0->nSize ) |
| { |
| pSupp->nSize = c; |
| return 1; |
| } |
| pSupp->pArray[c] = pSupp0->pArray[i++]; |
| continue; |
| } |
| if ( i == pSupp0->nSize ) |
| { |
| if ( k == pSupp1->nSize ) |
| { |
| pSupp->nSize = c; |
| return 1; |
| } |
| pSupp->pArray[c] = pSupp1->pArray[k++]; |
| continue; |
| } |
| if ( pSupp0->pArray[i] < pSupp1->pArray[k] ) |
| { |
| pSupp->pArray[c] = pSupp0->pArray[i++]; |
| continue; |
| } |
| if ( pSupp0->pArray[i] > pSupp1->pArray[k] ) |
| { |
| pSupp->pArray[c] = pSupp1->pArray[k++]; |
| continue; |
| } |
| pSupp->pArray[c] = pSupp0->pArray[i++]; |
| k++; |
| } |
| if ( i < pSupp0->nSize || k < pSupp1->nSize ) |
| return 0; |
| pSupp->nSize = c; |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates integer vector with the support of the node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapReadSupp( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Int_t * vLeaves ) |
| { |
| Ivy_Supp_t * pSupp; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| vLeaves->nCap = 8; |
| vLeaves->nSize = pSupp->nSize; |
| vLeaves->pArray = pSupp->pArray; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Sets the required times of the intermediate nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapRequired_rec( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Ivy_Obj_t * pRoot, int DelayR ) |
| { |
| Ivy_Supp_t * pSupp; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| if ( pObj != pRoot && (pSupp->nRefs > 0 || Ivy_ObjIsCi(pObj)) ) |
| return; |
| Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin0(pObj), pRoot, DelayR ); |
| Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin1(pObj), pRoot, DelayR ); |
| // assert( pObj == pRoot || pSupp->DelayR == IVY_INFINITY ); |
| pSupp->DelayR = DelayR; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the required times for each node.] |
| |
| Description [Sets reference counters for each node.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapRequired( Ivy_Man_t * pAig, int Delay, int fSetInter ) |
| { |
| Vec_Vec_t * vLuts; |
| Vec_Ptr_t * vNodes; |
| Ivy_Obj_t * pObj; |
| Ivy_Supp_t * pSupp, * pSuppF; |
| int i, k, c; |
| // clean the required times |
| Ivy_ManForEachPi( pAig, pObj, i ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| pSupp->DelayR = IVY_INFINITY; |
| pSupp->nRefs = 0; |
| } |
| Ivy_ManForEachNode( pAig, pObj, i ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| pSupp->DelayR = IVY_INFINITY; |
| pSupp->nRefs = 0; |
| } |
| // set the required times of the POs |
| Ivy_ManForEachPo( pAig, pObj, i ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) ); |
| pSupp->DelayR = Delay; |
| pSupp->nRefs++; |
| } |
| // get the levelized nodes used in the mapping |
| vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts; |
| // propagate the required times |
| Vec_VecForEachLevelReverse( vLuts, vNodes, i ) |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, k ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->nRefs > 0 ); |
| for ( c = 0; c < pSupp->nSize; c++ ) |
| { |
| pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) ); |
| pSuppF->DelayR = IVY_MIN( pSuppF->DelayR, pSupp->DelayR - 1 ); |
| pSuppF->nRefs++; |
| } |
| } |
| /* |
| // print out some of the required times |
| Ivy_ManForEachPi( pAig, pObj, i ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| printf( "%d ", pSupp->DelayR ); |
| } |
| printf( "\n" ); |
| */ |
| |
| if ( fSetInter ) |
| { |
| // set the required times of the intermediate nodes |
| Vec_VecForEachLevelReverse( vLuts, vNodes, i ) |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, k ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| Ivy_FastMapRequired_rec( pAig, pObj, pObj, pSupp->DelayR ); |
| } |
| // make sure that all required times are assigned |
| Ivy_ManForEachNode( pAig, pObj, i ) |
| { |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->DelayR < IVY_INFINITY ); |
| } |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs area recovery for each node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapRecover( Ivy_Man_t * pAig, int nLimit ) |
| { |
| Vec_Ptr_t * vFront, * vFrontOld; |
| Ivy_Obj_t * pObj; |
| int i; |
| vFront = Vec_PtrAlloc( nLimit ); |
| vFrontOld = Vec_PtrAlloc( nLimit ); |
| Ivy_ManCleanTravId( pAig ); |
| // iterate through all nodes in the topological order |
| Ivy_ManForEachNode( pAig, pObj, i ) |
| Ivy_FastMapNodeRecover( pAig, pObj, nLimit, vFront, vFrontOld ); |
| Vec_PtrFree( vFrontOld ); |
| Vec_PtrFree( vFront ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the delay of the cut rooted at this node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeDelay( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSupp, * pSuppF; |
| int c, Delay = 0; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| for ( c = 0; c < pSupp->nSize; c++ ) |
| { |
| pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) ); |
| Delay = IVY_MAX( Delay, pSuppF->Delay ); |
| } |
| return 1 + Delay; |
| } |
| |
| |
| /**function************************************************************* |
| |
| synopsis [References the cut.] |
| |
| description [This procedure is similar to the procedure NodeReclaim.] |
| |
| sideeffects [] |
| |
| seealso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeRef( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSupp, * pSuppF; |
| Ivy_Obj_t * pNodeChild; |
| int aArea, i; |
| // start the area of this cut |
| aArea = 1; |
| // go through the children |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->nSize > 1 ); |
| for ( i = 0; i < pSupp->nSize; i++ ) |
| { |
| pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]); |
| pSuppF = Ivy_ObjSupp( pAig, pNodeChild ); |
| assert( pSuppF->nRefs >= 0 ); |
| if ( pSuppF->nRefs++ > 0 ) |
| continue; |
| if ( pSuppF->nSize == 1 ) |
| continue; |
| aArea += Ivy_FastMapNodeRef( pAig, pNodeChild ); |
| } |
| return aArea; |
| } |
| |
| /**function************************************************************* |
| |
| synopsis [Dereferences the cut.] |
| |
| description [This procedure is similar to the procedure NodeRecusiveDeref.] |
| |
| sideeffects [] |
| |
| seealso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeDeref( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSupp, * pSuppF; |
| Ivy_Obj_t * pNodeChild; |
| int aArea, i; |
| // start the area of this cut |
| aArea = 1; |
| // go through the children |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->nSize > 1 ); |
| for ( i = 0; i < pSupp->nSize; i++ ) |
| { |
| pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]); |
| pSuppF = Ivy_ObjSupp( pAig, pNodeChild ); |
| assert( pSuppF->nRefs > 0 ); |
| if ( --pSuppF->nRefs > 0 ) |
| continue; |
| if ( pSuppF->nSize == 1 ) |
| continue; |
| aArea += Ivy_FastMapNodeDeref( pAig, pNodeChild ); |
| } |
| return aArea; |
| } |
| |
| /**function************************************************************* |
| |
| synopsis [Computes the exact area associated with the cut.] |
| |
| description [] |
| |
| sideeffects [] |
| |
| seealso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeAreaRefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSupp; |
| int aResult, aResult2; |
| if ( Ivy_ObjIsCi(pObj) ) |
| return 0; |
| assert( Ivy_ObjIsNode(pObj) ); |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->nRefs > 0 ); |
| aResult = Ivy_FastMapNodeDeref( pAig, pObj ); |
| aResult2 = Ivy_FastMapNodeRef( pAig, pObj ); |
| assert( aResult == aResult2 ); |
| return aResult; |
| } |
| |
| /**function************************************************************* |
| |
| synopsis [Computes the exact area associated with the cut.] |
| |
| description [] |
| |
| sideeffects [] |
| |
| seealso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeAreaDerefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSupp; |
| int aResult, aResult2; |
| if ( Ivy_ObjIsCi(pObj) ) |
| return 0; |
| assert( Ivy_ObjIsNode(pObj) ); |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| assert( pSupp->nRefs == 0 ); |
| aResult2 = Ivy_FastMapNodeRef( pAig, pObj ); |
| aResult = Ivy_FastMapNodeDeref( pAig, pObj ); |
| assert( aResult == aResult2 ); |
| return aResult; |
| } |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Counts the number of nodes with no external fanout.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapCutCost( Ivy_Man_t * pAig, Vec_Ptr_t * vFront ) |
| { |
| Ivy_Supp_t * pSuppF; |
| Ivy_Obj_t * pFanin; |
| int i, Counter = 0; |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i ) |
| { |
| pSuppF = Ivy_ObjSupp( pAig, pFanin ); |
| if ( pSuppF->nRefs == 0 ) |
| Counter++; |
| } |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs area recovery for each node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapMark_rec( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| if ( Ivy_ObjIsTravIdCurrent(pAig, pObj) ) |
| return; |
| assert( Ivy_ObjIsNode(pObj) ); |
| Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin0(pObj) ); |
| Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin1(pObj) ); |
| Ivy_ObjSetTravIdCurrent(pAig, pObj); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns 1 if the number of fanins will grow.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeWillGrow( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Obj_t * pFanin0, * pFanin1; |
| assert( Ivy_ObjIsNode(pObj) ); |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| return !Ivy_ObjIsTravIdCurrent(pAig, pFanin0) && !Ivy_ObjIsTravIdCurrent(pAig, pFanin1); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the increase in the number of fanins with no external refs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeFaninCost( Ivy_Man_t * pAig, Ivy_Obj_t * pObj ) |
| { |
| Ivy_Supp_t * pSuppF; |
| Ivy_Obj_t * pFanin; |
| int Counter = 0; |
| assert( Ivy_ObjIsNode(pObj) ); |
| // check if the node has external refs |
| pSuppF = Ivy_ObjSupp( pAig, pObj ); |
| if ( pSuppF->nRefs == 0 ) |
| Counter--; |
| // increment the number of fanins without external refs |
| pFanin = Ivy_ObjFanin0(pObj); |
| pSuppF = Ivy_ObjSupp( pAig, pFanin ); |
| if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 ) |
| Counter++; |
| // increment the number of fanins without external refs |
| pFanin = Ivy_ObjFanin1(pObj); |
| pSuppF = Ivy_ObjSupp( pAig, pFanin ); |
| if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 ) |
| Counter++; |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Updates the frontier.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeFaninUpdate( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Ptr_t * vFront ) |
| { |
| Ivy_Obj_t * pFanin; |
| assert( Ivy_ObjIsNode(pObj) ); |
| Vec_PtrRemove( vFront, pObj ); |
| pFanin = Ivy_ObjFanin0(pObj); |
| if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) ) |
| { |
| Ivy_ObjSetTravIdCurrent(pAig, pFanin); |
| Vec_PtrPush( vFront, pFanin ); |
| } |
| pFanin = Ivy_ObjFanin1(pObj); |
| if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) ) |
| { |
| Ivy_ObjSetTravIdCurrent(pAig, pFanin); |
| Vec_PtrPush( vFront, pFanin ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compacts the number of external refs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeFaninCompact0( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront ) |
| { |
| Ivy_Obj_t * pFanin; |
| int i; |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i ) |
| { |
| if ( Ivy_ObjIsCi(pFanin) ) |
| continue; |
| if ( Ivy_FastMapNodeWillGrow(pAig, pFanin) ) |
| continue; |
| if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 ) |
| { |
| Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront ); |
| return 1; |
| } |
| } |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compacts the number of external refs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeFaninCompact1( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront ) |
| { |
| Ivy_Obj_t * pFanin; |
| int i; |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i ) |
| { |
| if ( Ivy_ObjIsCi(pFanin) ) |
| continue; |
| if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) < 0 ) |
| { |
| Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront ); |
| return 1; |
| } |
| } |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compacts the number of external refs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeFaninCompact2( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront ) |
| { |
| Ivy_Obj_t * pFanin; |
| int i; |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i ) |
| { |
| if ( Ivy_ObjIsCi(pFanin) ) |
| continue; |
| if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 ) |
| { |
| Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront ); |
| return 1; |
| } |
| } |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compacts the number of external refs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_FastMapNodeFaninCompact_int( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront ) |
| { |
| if ( Ivy_FastMapNodeFaninCompact0(pAig, pObj, nLimit, vFront) ) |
| return 1; |
| if ( Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact1(pAig, pObj, nLimit, vFront) ) |
| return 1; |
| if ( Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact2(pAig, pObj, nLimit, vFront) ) |
| return 1; |
| assert( Vec_PtrSize(vFront) <= nLimit ); |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compacts the number of external refs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeFaninCompact( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront ) |
| { |
| while ( Ivy_FastMapNodeFaninCompact_int( pAig, pObj, nLimit, vFront ) ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prepares node mapping.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodePrepare( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld ) |
| { |
| Ivy_Supp_t * pSupp; |
| Ivy_Obj_t * pFanin; |
| int i; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| // expand the cut downwards from the given place |
| Vec_PtrClear( vFront ); |
| Vec_PtrClear( vFrontOld ); |
| Ivy_ManIncrementTravId( pAig ); |
| for ( i = 0; i < pSupp->nSize; i++ ) |
| { |
| pFanin = Ivy_ManObj(pAig, pSupp->pArray[i]); |
| Vec_PtrPush( vFront, pFanin ); |
| Vec_PtrPush( vFrontOld, pFanin ); |
| Ivy_ObjSetTravIdCurrent( pAig, pFanin ); |
| } |
| // mark the nodes in the cone |
| Ivy_FastMapMark_rec( pAig, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Updates the frontier.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeUpdate( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Ptr_t * vFront ) |
| { |
| Ivy_Supp_t * pSupp; |
| Ivy_Obj_t * pFanin; |
| int i; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| // deref node's cut |
| Ivy_FastMapNodeDeref( pAig, pObj ); |
| // update the node's cut |
| pSupp->nSize = Vec_PtrSize(vFront); |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i ) |
| pSupp->pArray[i] = pFanin->Id; |
| // ref the new cut |
| Ivy_FastMapNodeRef( pAig, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs area recovery for each node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeRecover2( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld ) |
| { |
| Ivy_Supp_t * pSupp; |
| int CostBef, CostAft; |
| int AreaBef, AreaAft; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| // if ( pSupp->nRefs == 0 ) |
| // return; |
| if ( pSupp->nRefs == 0 ) |
| AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj ); |
| else |
| AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| // get the area |
| if ( AreaBef == 1 ) |
| return; |
| |
| if ( pSupp->nRefs == 0 ) |
| { |
| pSupp->nRefs = 1000000; |
| Ivy_FastMapNodeRef( pAig, pObj ); |
| } |
| // the cut is non-trivial |
| Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld ); |
| // iteratively modify the cut |
| CostBef = Ivy_FastMapCutCost( pAig, vFront ); |
| Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront ); |
| CostAft = Ivy_FastMapCutCost( pAig, vFront ); |
| assert( CostBef >= CostAft ); |
| // update the node |
| Ivy_FastMapNodeUpdate( pAig, pObj, vFront ); |
| // get the new area |
| AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| if ( AreaAft > AreaBef ) |
| { |
| Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld ); |
| AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| assert( AreaAft == AreaBef ); |
| } |
| if ( pSupp->nRefs == 1000000 ) |
| { |
| pSupp->nRefs = 0; |
| Ivy_FastMapNodeDeref( pAig, pObj ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs area recovery for each node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeRecover( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld ) |
| { |
| Ivy_Supp_t * pSupp; |
| int CostBef, CostAft; |
| int AreaBef, AreaAft; |
| int DelayOld; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj ); |
| assert( pSupp->Delay <= pSupp->DelayR ); |
| if ( pSupp->nRefs == 0 ) |
| return; |
| // get the area |
| AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| // if ( AreaBef == 1 ) |
| // return; |
| // the cut is non-trivial |
| Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld ); |
| // iteratively modify the cut |
| Ivy_FastMapNodeDeref( pAig, pObj ); |
| CostBef = Ivy_FastMapCutCost( pAig, vFront ); |
| Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront ); |
| CostAft = Ivy_FastMapCutCost( pAig, vFront ); |
| Ivy_FastMapNodeRef( pAig, pObj ); |
| assert( CostBef >= CostAft ); |
| // update the node |
| Ivy_FastMapNodeUpdate( pAig, pObj, vFront ); |
| pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj ); |
| // get the new area |
| AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR ) |
| { |
| Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld ); |
| AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| assert( AreaAft == AreaBef ); |
| pSupp->Delay = DelayOld; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs area recovery for each node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_FastMapNodeRecover4( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld ) |
| { |
| Ivy_Supp_t * pSupp; |
| int CostBef, CostAft; |
| int AreaBef, AreaAft; |
| int DelayOld; |
| pSupp = Ivy_ObjSupp( pAig, pObj ); |
| DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj ); |
| assert( pSupp->Delay <= pSupp->DelayR ); |
| // if ( pSupp->nRefs == 0 ) |
| // return; |
| // AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| // get the area |
| if ( pSupp->nRefs == 0 ) |
| AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj ); |
| else |
| AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| if ( AreaBef == 1 ) |
| return; |
| |
| if ( pSupp->nRefs == 0 ) |
| { |
| pSupp->nRefs = 1000000; |
| Ivy_FastMapNodeRef( pAig, pObj ); |
| } |
| // the cut is non-trivial |
| Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld ); |
| // iteratively modify the cut |
| CostBef = Ivy_FastMapCutCost( pAig, vFront ); |
| Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront ); |
| CostAft = Ivy_FastMapCutCost( pAig, vFront ); |
| assert( CostBef >= CostAft ); |
| // update the node |
| Ivy_FastMapNodeUpdate( pAig, pObj, vFront ); |
| pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj ); |
| // get the new area |
| AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR ) |
| { |
| Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld ); |
| AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj ); |
| assert( AreaAft == AreaBef ); |
| pSupp->Delay = DelayOld; |
| } |
| if ( pSupp->nRefs == 1000000 ) |
| { |
| pSupp->nRefs = 0; |
| Ivy_FastMapNodeDeref( pAig, pObj ); |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
