From 4812c90424dfc40d26725244723887a2d16ddfd9 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 1 Oct 2007 08:01:00 -0700 Subject: Version abc71001 --- src/aig/ivy/ivyFastMap.c | 1593 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1593 insertions(+) create mode 100644 src/aig/ivy/ivyFastMap.c (limited to 'src/aig/ivy/ivyFastMap.c') diff --git a/src/aig/ivy/ivyFastMap.c b/src/aig/ivy/ivyFastMap.c new file mode 100644 index 00000000..c4a043f2 --- /dev/null +++ b/src/aig/ivy/ivyFastMap.c @@ -0,0 +1,1593 @@ +/**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" + +//////////////////////////////////////////////////////////////////////// +/// 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, int 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 int 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, clk, clkTotal = clock(); + // start the memory for supports + pMan = 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 *)malloc( pMan->nObjs * pMan->nSize ); + memset( pMan->pMem, 0, pMan->nObjs * pMan->nSize ); + pMan->vLuts = Vec_VecAlloc( 100 ); + pAig->pData = pMan; +clk = 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, clock() - clk, "Delay oriented mapping: " ); + +// 2-1-2 (doing 2-1-2-1-2 improves 0.5%) + + if ( fRecovery ) + { +clk = 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, clock() - clk, "Area recovery 2 : " ); + +clk = 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, clock() - clk, "Area recovery 1 : " ); + +clk = 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, clock() - clk, "Area recovery 2 : " ); + } + + + s_MappingTime = clock() - clkTotal; + s_MappingMem = pMan->nObjs * pMan->nSize; +/* + { + Vec_Ptr_t * vNodes; + vNodes = Vec_PtrAlloc( 100 ); + Vec_VecForEachEntry( 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 = pAig->pData; + Vec_VecFree( p->vLuts ); + free( p->pMem ); + free( p ); + pAig->pData = NULL; +} + +/**Function************************************************************* + + Synopsis [Prints statistics.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ivy_FastMapPrint( Ivy_Man_t * pAig, int Delay, int Area, int Time, char * pStr ) +{ + printf( "%s : Delay = %3d. Area = %6d. ", pStr, Delay, Area ); + 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 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 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 void Vec_IntSelectSort( int * pArray, int nSize ) +{ + int temp, i, j, best_i; + for ( i = 0; i < nSize-1; i++ ) + { + best_i = i; + for ( j = i+1; j < nSize; j++ ) + if ( pArray[j] < pArray[best_i] ) + best_i = j; + temp = pArray[i]; + pArray[i] = pArray[best_i]; + pArray[best_i] = temp; + } +} + +/**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[pSupp->nSize++] = Ivy_ObjId(pFanin0); + else + { + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA); + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB); + } + } + else + pSupp->pArray[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[pSupp->nSize++] = Ivy_ObjId(pFanin1); + else + { + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA); + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB); + } + } + else + pSupp->pArray[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[pSupp->nSize++] = Ivy_ObjId(pFanin0); + else + { + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA); + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB); + } + } + else + pSupp->pArray[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[pSupp->nSize++] = Ivy_ObjId(pFanin1); + else + { + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA); + pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB); + } + } + else + pSupp->pArray[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( 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( 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( 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( 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( 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( 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( 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; + if ( pObj->Id == 102 ) + { + int x = 0; + } + // 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 /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3