/**CFile**************************************************************** FileName [giaKf.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Scalable AIG package.] Synopsis [Cut computation.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: giaKf.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "gia.h" #include "misc/vec/vecSet.h" #ifdef ABC_USE_PTHREADS #ifdef _WIN32 #include "../lib/pthread.h" #else #include #include #endif #endif ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// #ifndef ABC_USE_PTHREADS void Kf_ManSetDefaultPars( Jf_Par_t * pPars ) {} Gia_Man_t * Kf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ) { return NULL; } #else // pthreads are used #define KF_LEAF_MAX 16 #define KF_CUT_MAX 32 #define KF_PROC_MAX 32 #define KF_WORD_MAX ((KF_LEAF_MAX > 6) ? 1 << (KF_LEAF_MAX-6) : 1) #define KF_LOG_TABLE 8 #define KF_ADD_ON1 2 // offset in cut storage for each node (cut count; best cut) #define KF_ADD_ON2 4 // offset in cut storage for each cut (leaf count; function, cut delay; cut area) typedef struct Kf_Cut_t_ Kf_Cut_t; typedef struct Kf_Set_t_ Kf_Set_t; typedef struct Kf_Man_t_ Kf_Man_t; struct Kf_Cut_t_ { word Sign; // signature int Polar; // polarity int Delay; // delay float Area; // area int iFunc; // function int iNext; // next cut int nLeaves; // number of leaves int pLeaves[KF_LEAF_MAX]; }; struct Kf_Set_t_ { Kf_Man_t * pMan; // manager unsigned short nLutSize; // lut size unsigned short nCutNum; // cut count int nCuts0; // fanin0 cut count int nCuts1; // fanin1 cut count int nCuts; // resulting cut count int nTEntries; // hash table entries int TableMask; // hash table mask int pTable[1 << KF_LOG_TABLE]; int pValue[1 << KF_LOG_TABLE]; int pPlace[KF_LEAF_MAX]; int pList [KF_LEAF_MAX+1]; Kf_Cut_t pCuts0[KF_CUT_MAX]; Kf_Cut_t pCuts1[KF_CUT_MAX]; Kf_Cut_t pCutsR[KF_CUT_MAX*KF_CUT_MAX]; Kf_Cut_t * ppCuts[KF_CUT_MAX]; Kf_Cut_t * pCutBest; word CutCount[4]; // statistics }; struct Kf_Man_t_ { Gia_Man_t * pGia; // user's manager Jf_Par_t * pPars; // user's parameters Vec_Set_t pMem; // cut storage Vec_Int_t vCuts; // node params Vec_Int_t vTime; // node params Vec_Flt_t vArea; // node params Vec_Flt_t vRefs; // node params Vec_Int_t * vTemp; // temporary abctime clkStart; // starting time Kf_Set_t pSett[KF_PROC_MAX]; }; static inline int Kf_SetCutId( Kf_Set_t * p, Kf_Cut_t * pCut ) { return pCut - p->pCutsR; } static inline Kf_Cut_t * Kf_SetCut( Kf_Set_t * p, int i ) { return i >= 0 ? p->pCutsR + i : NULL; } static inline int Kf_ObjTime( Kf_Man_t * p, int i ) { return Vec_IntEntry(&p->vTime, i); } static inline float Kf_ObjArea( Kf_Man_t * p, int i ) { return Vec_FltEntry(&p->vArea, i); } static inline float Kf_ObjRefs( Kf_Man_t * p, int i ) { return Vec_FltEntry(&p->vRefs, i); } static inline void Kf_ObjSetCuts( Kf_Man_t * p, int i, Vec_Int_t * vVec ) { Vec_IntWriteEntry(&p->vCuts, i, Vec_SetAppend(&p->pMem, Vec_IntArray(vVec), Vec_IntSize(vVec))); } static inline int * Kf_ObjCuts( Kf_Man_t * p, int i ) { return (int *)Vec_SetEntry(&p->pMem, Vec_IntEntry(&p->vCuts, i)); } static inline int * Kf_ObjCuts0( Kf_Man_t * p, int i ) { return Kf_ObjCuts(p, Gia_ObjFaninId0(Gia_ManObj(p->pGia, i), i)); } static inline int * Kf_ObjCuts1( Kf_Man_t * p, int i ) { return Kf_ObjCuts(p, Gia_ObjFaninId1(Gia_ManObj(p->pGia, i), i)); } static inline int * Kf_ObjCutBest( Kf_Man_t * p, int i ) { int * pCuts = Kf_ObjCuts(p, i); return pCuts + pCuts[1]; } #define Kf_ObjForEachCutInt( pList, pCut, i ) for ( i = 0, pCut = pList + KF_ADD_ON1; i < pList[0]; i++, pCut += pCut[0] + KF_ADD_ON2 ) #define Kf_ListForEachCut( p, iList, pCut ) for ( pCut = Kf_SetCut(p, p->pList[iList]); pCut; pCut = Kf_SetCut(p, pCut->iNext) ) #define Kf_ListForEachCutP( p, iList, pCut, pPlace ) for ( pPlace = p->pList+iList, pCut = Kf_SetCut(p, *pPlace); pCut; pCut = Kf_SetCut(p, *pPlace) ) //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_SetLoadCuts( Kf_Cut_t * pCuts, int * pIntCuts ) { Kf_Cut_t * pCut; int k, * pIntCut, nCuts = 0; Kf_ObjForEachCutInt( pIntCuts, pIntCut, nCuts ) { pCut = pCuts + nCuts; pCut->Sign = 0; pCut->Polar = 0; pCut->iFunc = pIntCut[pIntCut[0] + 1]; pCut->Delay = pIntCut[pIntCut[0] + 2]; pCut->Area = Abc_Int2Float(pIntCut[pIntCut[0] + 3]); pCut->nLeaves = pIntCut[0]; for ( k = 0; k < pIntCut[0]; k++ ) { pCut->pLeaves[k] = Abc_Lit2Var(pIntCut[k+1]); pCut->Sign |= ((word)1) << (pCut->pLeaves[k] & 0x3F); if ( Abc_LitIsCompl(pIntCut[k+1]) ) pCut->Polar |= (1 << k); } } return nCuts; } static inline void Kf_SetPrepare( Kf_Set_t * p, int * pCuts0, int * pCuts1 ) { int i; // prepare hash table // for ( i = 0; i <= p->TableMask; i++ ) // assert( p->pTable[i] == 0 ); // prepare cut storage for ( i = 0; i <= p->nLutSize; i++ ) p->pList[i] = -1; // transfer cuts p->nCuts0 = Kf_SetLoadCuts( p->pCuts0, pCuts0 ); p->nCuts1 = Kf_SetLoadCuts( p->pCuts1, pCuts1 ); p->nCuts = 0; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Kf_ManStoreStart( Vec_Int_t * vTemp, int nCuts ) { Vec_IntClear( vTemp ); Vec_IntPush( vTemp, nCuts ); // cut count Vec_IntPush( vTemp, -1 ); // best offset } static inline void Kf_ManStoreAddUnit( Vec_Int_t * vTemp, int iObj, int Time, float Area ) { Vec_IntAddToEntry( vTemp, 0, 1 ); Vec_IntPush( vTemp, 1 ); // cut size Vec_IntPush( vTemp, Abc_Var2Lit(iObj, 0) ); // leaf Vec_IntPush( vTemp, 2 ); // function Vec_IntPush( vTemp, Time ); // delay Vec_IntPush( vTemp, Abc_Float2Int(Area) ); // area } static inline void Kf_ManSaveResults( Kf_Cut_t ** ppCuts, int nCuts, Kf_Cut_t * pCutBest, Vec_Int_t * vTemp ) { int i, k; assert( nCuts > 0 && nCuts < KF_CUT_MAX ); Kf_ManStoreStart( vTemp, nCuts ); for ( i = 0; i < nCuts; i++ ) { if ( ppCuts[i] == pCutBest ) Vec_IntWriteEntry( vTemp, 1, Vec_IntSize(vTemp) ); Vec_IntPush( vTemp, ppCuts[i]->nLeaves ); // Vec_IntPushArray( vTemp, ppCuts[i]->pLeaves, ppCuts[i]->nLeaves ); for ( k = 0; k < ppCuts[i]->nLeaves; k++ ) Vec_IntPush( vTemp, Abc_Var2Lit(ppCuts[i]->pLeaves[k], 0) ); Vec_IntPush( vTemp, ppCuts[i]->iFunc ); Vec_IntPush( vTemp, ppCuts[i]->Delay ); Vec_IntPush( vTemp, Abc_Float2Int(ppCuts[i]->Area) ); } assert( Vec_IntEntry(vTemp, 1) > 0 ); } static inline int Kf_SetCompareCuts( Kf_Cut_t * p1, Kf_Cut_t * p2 ) { if ( p1 == NULL || p2 == NULL ) return (p1 != NULL) - (p2 != NULL); if ( p1->nLeaves != p2->nLeaves ) return p1->nLeaves - p2->nLeaves; return memcmp( p1->pLeaves, p2->pLeaves, sizeof(int)*p1->nLeaves ); } static inline void Kf_SetAddToList( Kf_Set_t * p, Kf_Cut_t * pCut, int fSort ) { if ( !fSort ) pCut->iNext = p->pList[pCut->nLeaves], p->pList[pCut->nLeaves] = Kf_SetCutId(p, pCut); else { int Value, * pPlace; Kf_Cut_t * pTemp; Vec_IntSelectSort( pCut->pLeaves, pCut->nLeaves ); Kf_ListForEachCutP( p, pCut->nLeaves, pTemp, pPlace ) { if ( (Value = Kf_SetCompareCuts(pTemp, pCut)) > 0 ) break; assert( Value < 0 ); pPlace = &pTemp->iNext; } pCut->iNext = *pPlace, *pPlace = Kf_SetCutId(p, pCut); } } static inline int Kf_CutCompare( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, int fArea ) { if ( fArea ) { if ( pCut0->Area < pCut1->Area ) return -1; if ( pCut0->Area > pCut1->Area ) return 1; if ( pCut0->Delay < pCut1->Delay ) return -1; if ( pCut0->Delay > pCut1->Delay ) return 1; if ( pCut0->nLeaves < pCut1->nLeaves ) return -1; if ( pCut0->nLeaves > pCut1->nLeaves ) return 1; } else { if ( pCut0->Delay < pCut1->Delay ) return -1; if ( pCut0->Delay > pCut1->Delay ) return 1; if ( pCut0->nLeaves < pCut1->nLeaves ) return -1; if ( pCut0->nLeaves > pCut1->nLeaves ) return 1; if ( pCut0->Area < pCut1->Area ) return -1; if ( pCut0->Area > pCut1->Area ) return 1; } return 0; } static inline int Kf_SetStoreAddOne( Kf_Set_t * p, int nCuts, int nCutNum, Kf_Cut_t * pCut, int fArea ) { int i; p->ppCuts[nCuts] = pCut; if ( nCuts == 0 ) return 1; for ( i = nCuts; i > 0; i-- ) if ( Kf_CutCompare(p->ppCuts[i-1], p->ppCuts[i], fArea) > 0 ) ABC_SWAP( Kf_Cut_t *, p->ppCuts[i-1], p->ppCuts[i] ) else break; return Abc_MinInt( nCuts+1, nCutNum ); } static inline void Kf_SetSelectBest( Kf_Set_t * p, int fArea, int fSort ) { // int fArea = p->pMan->pPars->fArea; Kf_Cut_t * pCut; int i, nCuts = 0; for ( i = 0; i <= p->nLutSize; i++ ) Kf_ListForEachCut( p, i, pCut ) nCuts = Kf_SetStoreAddOne( p, nCuts, p->nCutNum-1, pCut, fArea ); assert( nCuts > 0 && nCuts < p->nCutNum ); p->nCuts = nCuts; p->pCutBest = p->ppCuts[0]; if ( !fSort ) return; // sort by size in the reverse order for ( i = 0; i <= p->nLutSize; i++ ) p->pList[i] = -1; for ( i = 0; i < nCuts; i++ ) Kf_SetAddToList( p, p->ppCuts[i], 0 ); p->nCuts = 0; for ( i = p->nLutSize; i >= 0; i-- ) Kf_ListForEachCut( p, i, pCut ) p->ppCuts[p->nCuts++] = pCut; assert( p->nCuts == nCuts ); } /**Function************************************************************* Synopsis [Check correctness of cuts.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_CheckCut( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase { int nSizeB = pBase->nLeaves; int nSizeC = pCut->nLeaves; int * pB = pBase->pLeaves; int * pC = pCut->pLeaves; int i, k; for ( i = 0; i < nSizeC; i++ ) { for ( k = 0; k < nSizeB; k++ ) if ( pC[i] == pB[k] ) break; if ( k == nSizeB ) return 0; } return 1; } static inline int Kf_CheckCuts( Kf_Set_t * p ) { Kf_Cut_t * pCut0, * pCut1; int i, k, m, n, Value; assert( p->nCuts > 0 ); for ( i = 0; i <= p->nLutSize; i++ ) Kf_ListForEachCut( p, i, pCut0 ) { // check duplicates for ( m = 0; m < pCut0->nLeaves; m++ ) for ( n = m+1; n < pCut0->nLeaves; n++ ) assert( pCut0->pLeaves[m] != pCut0->pLeaves[n] ); // check pairs for ( k = 0; k <= p->nLutSize; k++ ) Kf_ListForEachCut( p, k, pCut1 ) { if ( pCut0 == pCut1 ) continue; // check containments Value = Kf_CheckCut( pCut0, pCut1 ); assert( Value == 0 ); } } return 1; } /**Function************************************************************* Synopsis [Hash table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_HashLookup( Kf_Set_t * p, int i ) { int k; assert( i > 0 ); for ( k = i & p->TableMask; p->pTable[k]; k = (k + 1) & p->TableMask ) if ( p->pTable[k] == i ) return -1; return k; } static inline int Kf_HashFindOrAdd( Kf_Set_t * p, int i ) { int k = Kf_HashLookup( p, i ); if ( k == -1 ) return 0; if ( p->nTEntries == p->nLutSize ) return 1; assert( p->pTable[k] == 0 ); p->pTable[k] = i; p->pPlace[p->nTEntries] = k; p->pValue[k] = p->nTEntries++; return 0; } static inline void Kf_HashPopulate( Kf_Set_t * p, Kf_Cut_t * pCut ) { int i; assert( p->nTEntries == 0 ); for ( i = 0; i < pCut->nLeaves; i++ ) Kf_HashFindOrAdd( p, pCut->pLeaves[i] ); assert( p->nTEntries == pCut->nLeaves ); } static inline void Kf_HashCleanup( Kf_Set_t * p, int iStart ) { int i; for ( i = iStart; i < p->nTEntries; i++ ) p->pTable[p->pPlace[i]] = 0; p->nTEntries = iStart; } /**Function************************************************************* Synopsis [Cut merging with arbitary order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_SetCountBits( word i ) { i = i - ((i >> 1) & 0x5555555555555555); i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333); i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F); return (i*(0x0101010101010101))>>56; } static inline word Kf_SetCutGetSign( Kf_Cut_t * p ) { word Sign = 0; int i; for ( i = 0; i < p->nLeaves; i++ ) Sign |= ((word)1) << (p->pLeaves[i] & 0x3F); return Sign; } // returns 1 if the cut in hash table is dominated by the given one static inline int Kf_SetCutDominatedByThis( Kf_Set_t * p, Kf_Cut_t * pCut ) { int i; for ( i = 0; i < pCut->nLeaves; i++ ) if ( Kf_HashLookup(p, pCut->pLeaves[i]) >= 0 ) return 0; return 1; } static inline int Kf_SetRemoveDuplicates( Kf_Set_t * p, int nLeaves, word Sign ) { Kf_Cut_t * pCut; Kf_ListForEachCut( p, nLeaves, pCut ) if ( pCut->Sign == Sign && Kf_SetCutDominatedByThis(p, pCut) ) return 1; return 0; } static inline void Kf_SetFilter( Kf_Set_t * p ) { Kf_Cut_t * pCut0, * pCut1; int i, k, * pPlace; assert( p->nCuts > 0 ); for ( i = 0; i <= p->nLutSize; i++ ) Kf_ListForEachCutP( p, i, pCut0, pPlace ) { Kf_HashPopulate( p, pCut0 ); for ( k = 0; k < pCut0->nLeaves; k++ ) Kf_ListForEachCut( p, k, pCut1 ) if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutDominatedByThis(p, pCut1) ) { k = pCut0->nLeaves; p->nCuts--; break; } if ( k == pCut0->nLeaves + 1 ) // remove pCut0 *pPlace = pCut0->iNext; else pPlace = &pCut0->iNext; Kf_HashCleanup( p, 0 ); } assert( p->nCuts > 0 ); } static inline void Kf_SetMergePairs( Kf_Set_t * p, Kf_Cut_t * pCut0, Kf_Cut_t * pCuts, int nCuts, int fArea ) { Kf_Cut_t * pCut1, * pCutR; int i; Kf_HashPopulate( p, pCut0 ); for ( pCut1 = pCuts; pCut1 < pCuts + nCuts; pCut1++ ) { if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize ) continue; Kf_HashCleanup( p, pCut0->nLeaves ); for ( i = 0; i < pCut1->nLeaves; i++ ) if ( Kf_HashFindOrAdd(p, pCut1->pLeaves[i]) ) break; if ( i < pCut1->nLeaves ) continue; p->CutCount[1]++; if ( Kf_SetRemoveDuplicates(p, p->nTEntries, pCut0->Sign | pCut1->Sign) ) continue; // create new cut pCutR = p->pCutsR + p->nCuts++; pCutR->nLeaves = p->nTEntries; for ( i = 0; i < p->nTEntries; i++ ) pCutR->pLeaves[i] = p->pTable[p->pPlace[i]]; pCutR->Sign = pCut0->Sign | pCut1->Sign; pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay); pCutR->Area = pCut0->Area + pCut1->Area; // add new cut Kf_SetAddToList( p, pCutR, 0 ); } Kf_HashCleanup( p, 0 ); } static inline void Kf_SetMerge( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) { int c0, c1; Kf_SetPrepare( p, pCuts0, pCuts1 ); p->CutCount[0] += p->nCuts0 * p->nCuts1; // for ( c0 = 1; c0 < p->nCuts0; c0++ ) // assert( p->pCuts0[c0-1].nLeaves >= p->pCuts0[c0].nLeaves ); for ( c0 = c1 = 0; c0 < p->nCuts0 && c1 < p->nCuts1; ) { if ( p->pCuts0[c0].nLeaves >= p->pCuts1[c1].nLeaves ) Kf_SetMergePairs( p, p->pCuts0 + c0++, p->pCuts1 + c1, p->nCuts1 - c1, fArea ); else Kf_SetMergePairs( p, p->pCuts1 + c1++, p->pCuts0 + c0, p->nCuts0 - c0, fArea ); } p->CutCount[2] += p->nCuts; Kf_SetFilter( p ); // Kf_CheckCuts( p ); p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); Kf_SetSelectBest( p, fArea, 1 ); } /**Function************************************************************* Synopsis [Cut merging with fixed order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_SetCutIsContainedSimple( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase { int nSizeB = pBase->nLeaves; int nSizeC = pCut->nLeaves; int * pB = pBase->pLeaves; int * pC = pCut->pLeaves; int i, k; assert( nSizeB >= nSizeC ); for ( i = 0; i < nSizeC; i++ ) { for ( k = 0; k < nSizeB; k++ ) if ( pC[i] == pB[k] ) break; if ( k == nSizeB ) return 0; } return 1; } static inline int Kf_SetMergeSimpleOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize ) { int nSize0 = pCut0->nLeaves; int nSize1 = pCut1->nLeaves; int * pC0 = pCut0->pLeaves; int * pC1 = pCut1->pLeaves; int * pC = pCut->pLeaves; int i, k, c; // compare two cuts with different numbers c = nSize0; for ( i = 0; i < nSize1; i++ ) { for ( k = 0; k < nSize0; k++ ) if ( pC1[i] == pC0[k] ) break; if ( k < nSize0 ) continue; if ( c == nLutSize ) return 0; pC[c++] = pC1[i]; } for ( i = 0; i < nSize0; i++ ) pC[i] = pC0[i]; pCut->nLeaves = c; return 1; } static inline int Kf_SetRemoveDuplicatesSimple( Kf_Set_t * p, Kf_Cut_t * pCutNew ) { Kf_Cut_t * pCut; Kf_ListForEachCut( p, pCutNew->nLeaves, pCut ) if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedSimple(pCut, pCutNew) ) return 1; return 0; } static inline void Kf_SetFilterSimple( Kf_Set_t * p ) { Kf_Cut_t * pCut0, * pCut1; int i, k, * pPlace; assert( p->nCuts > 0 ); for ( i = 0; i <= p->nLutSize; i++ ) Kf_ListForEachCutP( p, i, pCut0, pPlace ) { for ( k = 0; k < pCut0->nLeaves; k++ ) Kf_ListForEachCut( p, k, pCut1 ) if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedSimple(pCut0, pCut1) ) { k = pCut0->nLeaves; p->nCuts--; break; } if ( k == pCut0->nLeaves + 1 ) // remove pCut0 *pPlace = pCut0->iNext; else pPlace = &pCut0->iNext; } assert( p->nCuts > 0 ); } static inline void Kf_SetMergeSimple( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) { Kf_Cut_t * pCut0, * pCut1, * pCutR; Kf_SetPrepare( p, pCuts0, pCuts1 ); p->CutCount[0] += p->nCuts0 * p->nCuts1; for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ ) for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ ) { if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize ) continue; p->CutCount[1]++; pCutR = p->pCutsR + p->nCuts; if ( !Kf_SetMergeSimpleOne(pCut0, pCut1, pCutR, p->nLutSize) ) continue; p->CutCount[2]++; pCutR->Sign = pCut0->Sign | pCut1->Sign; if ( Kf_SetRemoveDuplicatesSimple(p, pCutR) ) continue; p->nCuts++; if ( fCutMin ) { int nOldSupp = pCutR->nLeaves; // pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR ); assert( pCutR->nLeaves <= nOldSupp ); if ( pCutR->nLeaves < nOldSupp ) pCutR->Sign = Kf_SetCutGetSign( pCutR ); // delay and area are inaccurate } assert( pCutR->nLeaves > 1 ); pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay); pCutR->Area = pCut0->Area + pCut1->Area; // add new cut Kf_SetAddToList( p, pCutR, 0 ); } Kf_SetFilterSimple( p ); // Kf_CheckCuts( p ); p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); Kf_SetSelectBest( p, fArea, 1 ); } /**Function************************************************************* Synopsis [Cut merging with fixed order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_SetCutIsContainedOrder( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase { int nSizeB = pBase->nLeaves; int nSizeC = pCut->nLeaves; int i, k; if ( nSizeB == nSizeC ) { for ( i = 0; i < nSizeB; i++ ) if ( pBase->pLeaves[i] != pCut->pLeaves[i] ) return 0; return 1; } assert( nSizeB > nSizeC ); for ( i = k = 0; i < nSizeB; i++ ) { if ( pBase->pLeaves[i] > pCut->pLeaves[k] ) return 0; if ( pBase->pLeaves[i] == pCut->pLeaves[k] ) { if ( ++k == nSizeC ) return 1; } } return 0; } static inline int Kf_SetMergeOrderOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize ) { int nSize0 = pCut0->nLeaves; int nSize1 = pCut1->nLeaves; int * pC0 = pCut0->pLeaves; int * pC1 = pCut1->pLeaves; int * pC = pCut->pLeaves; int i, k, c; // the case of the largest cut sizes if ( nSize0 == nLutSize && nSize1 == nLutSize ) { for ( i = 0; i < nSize0; i++ ) { if ( pC0[i] != pC1[i] ) return 0; pC[i] = pC0[i]; } pCut->nLeaves = nLutSize; return 1; } // compare two cuts with different numbers i = k = c = 0; while ( 1 ) { if ( c == nLutSize ) return 0; if ( pC0[i] < pC1[k] ) { pC[c++] = pC0[i++]; if ( i >= nSize0 ) goto FlushCut1; } else if ( pC0[i] > pC1[k] ) { pC[c++] = pC1[k++]; if ( k >= nSize1 ) goto FlushCut0; } else { pC[c++] = pC0[i++]; k++; if ( i >= nSize0 ) goto FlushCut1; if ( k >= nSize1 ) goto FlushCut0; } } FlushCut0: if ( c + nSize0 > nLutSize + i ) return 0; while ( i < nSize0 ) pC[c++] = pC0[i++]; pCut->nLeaves = c; return 1; FlushCut1: if ( c + nSize1 > nLutSize + k ) return 0; while ( k < nSize1 ) pC[c++] = pC1[k++]; pCut->nLeaves = c; return 1; } static inline int Kf_SetRemoveDuplicatesOrder( Kf_Set_t * p, Kf_Cut_t * pCutNew ) { Kf_Cut_t * pCut; Kf_ListForEachCut( p, pCutNew->nLeaves, pCut ) if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedOrder(pCut, pCutNew) ) return 1; return 0; } static inline void Kf_SetFilterOrder( Kf_Set_t * p ) { Kf_Cut_t * pCut0, * pCut1; int i, k, * pPlace; assert( p->nCuts > 0 ); for ( i = 0; i <= p->nLutSize; i++ ) Kf_ListForEachCutP( p, i, pCut0, pPlace ) { for ( k = 0; k < pCut0->nLeaves; k++ ) Kf_ListForEachCut( p, k, pCut1 ) if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedOrder(pCut0, pCut1) ) { k = pCut0->nLeaves; p->nCuts--; break; } if ( k == pCut0->nLeaves + 1 ) // remove pCut0 *pPlace = pCut0->iNext; else pPlace = &pCut0->iNext; } assert( p->nCuts > 0 ); } /* int Kf_SetComputeTruth( Kf_Man_t * p, int iFuncLit0, int iFuncLit1, int * pCut0, int * pCut1, int * pCutOut ) { word uTruth[JF_WORD_MAX], uTruth0[JF_WORD_MAX], uTruth1[JF_WORD_MAX]; int fCompl, truthId; int LutSize = p->pPars->nLutSize; int nWords = Abc_Truth6WordNum(p->pPars->nLutSize); word * pTruth0 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit0)); word * pTruth1 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit1)); Abc_TtCopy( uTruth0, pTruth0, nWords, Abc_LitIsCompl(iFuncLit0) ); Abc_TtCopy( uTruth1, pTruth1, nWords, Abc_LitIsCompl(iFuncLit1) ); Abc_TtExpand( uTruth0, LutSize, pCut0 + 1, Kf_CutSize(pCut0), pCutOut + 1, Kf_CutSize(pCutOut) ); Abc_TtExpand( uTruth1, LutSize, pCut1 + 1, Kf_CutSize(pCut1), pCutOut + 1, Kf_CutSize(pCutOut) ); fCompl = (int)(uTruth0[0] & uTruth1[0] & 1); Abc_TtAnd( uTruth, uTruth0, uTruth1, nWords, fCompl ); pCutOut[0] = Abc_TtMinBase( uTruth, pCutOut + 1, pCutOut[0], LutSize ); assert( (uTruth[0] & 1) == 0 ); truthId = Vec_MemHashInsert(p->vTtMem, uTruth); return Abc_Var2Lit( truthId, fCompl ); } */ static inline void Kf_SetMergeOrder( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) { Kf_Cut_t * pCut0, * pCut1, * pCutR; Kf_SetPrepare( p, pCuts0, pCuts1 ); p->CutCount[0] += p->nCuts0 * p->nCuts1; for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ ) for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ ) { if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize ) continue; p->CutCount[1]++; pCutR = p->pCutsR + p->nCuts; if ( !Kf_SetMergeOrderOne(pCut0, pCut1, pCutR, p->nLutSize) ) continue; p->CutCount[2]++; pCutR->Sign = pCut0->Sign | pCut1->Sign; if ( Kf_SetRemoveDuplicatesOrder(p, pCutR) ) continue; p->nCuts++; if ( fCutMin ) { int nOldSupp = pCutR->nLeaves; // pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR ); assert( pCutR->nLeaves <= nOldSupp ); if ( pCutR->nLeaves < nOldSupp ) pCutR->Sign = Kf_SetCutGetSign( pCutR ); // delay and area are inaccurate } assert( pCutR->nLeaves > 1 ); pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay); pCutR->Area = pCut0->Area + pCut1->Area; // add new cut Kf_SetAddToList( p, pCutR, 0 ); } Kf_SetFilterOrder( p ); // Kf_CheckCuts( p ); p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); Kf_SetSelectBest( p, fArea, 1 ); } /**Function************************************************************* Synopsis [Cut operations.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Kf_CutSize( int * pCut ) { return pCut[0]; } static inline int Kf_CutFunc( int * pCut ) { return pCut[pCut[0] + 1]; } static inline int Kf_CutLeaf( int * pCut, int i ) { assert(i); return Abc_Lit2Var(pCut[i]); } static inline int Kf_CutTime( Kf_Man_t * p, int * pCut ) { int i, Time = 0; for ( i = 1; i <= Kf_CutSize(pCut); i++ ) Time = Abc_MaxInt( Time, Kf_ObjTime(p, Kf_CutLeaf(pCut, i)) ); return Time + 1; } static inline void Kf_CutRef( Kf_Man_t * p, int * pCut ) { int i; for ( i = 1; i <= Kf_CutSize(pCut); i++ ) Gia_ObjRefIncId( p->pGia, Kf_CutLeaf(pCut, i) ); } static inline void Kf_CutDeref( Kf_Man_t * p, int * pCut ) { int i; for ( i = 1; i <= Kf_CutSize(pCut); i++ ) Gia_ObjRefDecId( p->pGia, Kf_CutLeaf(pCut, i) ); } static inline void Kf_CutPrint( int * pCut ) { int i; printf( "%d {", Kf_CutSize(pCut) ); for ( i = 1; i <= Kf_CutSize(pCut); i++ ) printf( " %d", Kf_CutLeaf(pCut, i) ); printf( " } Func = %d\n", Kf_CutFunc(pCut) ); } static inline void Gia_CutSetPrint( int * pCuts ) { int i, * pCut; Kf_ObjForEachCutInt( pCuts, pCut, i ) Kf_CutPrint( pCut ); printf( "\n" ); } /**Function************************************************************* Synopsis [Computing delay/area.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Kf_ManComputeDelay( Kf_Man_t * p, int fEval ) { Gia_Obj_t * pObj; int i, Delay = 0; if ( fEval ) { Gia_ManForEachAnd( p->pGia, pObj, i ) if ( Gia_ObjRefNum(p->pGia, pObj) > 0 ) Vec_IntWriteEntry( &p->vTime, i, Kf_CutTime(p, Kf_ObjCutBest(p, i)) ); } Gia_ManForEachCoDriver( p->pGia, pObj, i ) { assert( Gia_ObjRefNum(p->pGia, pObj) > 0 ); Delay = Abc_MaxInt( Delay, Kf_ObjTime(p, Gia_ObjId(p->pGia, pObj)) ); } return Delay; } int Kf_ManComputeRefs( Kf_Man_t * p ) { Gia_Obj_t * pObj; float nRefsNew; int i, * pCut; float * pRefs = Vec_FltArray(&p->vRefs); float * pFlow = Vec_FltArray(&p->vArea); assert( p->pGia->pRefs != NULL ); memset( p->pGia->pRefs, 0, sizeof(int) * Gia_ManObjNum(p->pGia) ); p->pPars->Area = p->pPars->Edge = 0; Gia_ManForEachObjReverse( p->pGia, pObj, i ) { if ( Gia_ObjIsCo(pObj) || Gia_ObjIsBuf(pObj) ) Gia_ObjRefInc( p->pGia, Gia_ObjFanin0(pObj) ); else if ( Gia_ObjIsAnd(pObj) && Gia_ObjRefNum(p->pGia, pObj) > 0 ) { pCut = Kf_ObjCutBest(p, i); Kf_CutRef( p, pCut ); p->pPars->Edge += Kf_CutSize(pCut); p->pPars->Area++; } } // blend references and normalize flow for ( i = 0; i < Gia_ManObjNum(p->pGia); i++ ) { if ( p->pPars->fOptEdge ) nRefsNew = Abc_MaxFloat( 1, 0.8 * pRefs[i] + 0.2 * p->pGia->pRefs[i] ); else nRefsNew = Abc_MaxFloat( 1, 0.2 * pRefs[i] + 0.8 * p->pGia->pRefs[i] ); pFlow[i] = pFlow[i] * pRefs[i] / nRefsNew; pRefs[i] = nRefsNew; assert( pFlow[i] >= 0 ); } // compute delay p->pPars->Delay = Kf_ManComputeDelay( p, 1 ); return p->pPars->Area; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ #ifdef ABC_USE_PTHREADS #define PAR_THR_MAX 100 typedef struct Kf_ThData_t_ { Kf_Set_t * pSett; int Id; int Status; abctime clkUsed; } Kf_ThData_t; void * Kf_WorkerThread( void * pArg ) { Kf_ThData_t * pThData = (Kf_ThData_t *)pArg; Kf_Man_t * pMan = pThData->pSett->pMan; int fAreaOnly = pThData->pSett->pMan->pPars->fAreaOnly; int fCutMin = pThData->pSett->pMan->pPars->fCutMin; volatile int * pPlace = &pThData->Status; abctime clk; while ( 1 ) { while ( *pPlace == 0 ); assert( pThData->Status == 1 ); if ( pThData->Id == -1 ) { pthread_exit( NULL ); assert( 0 ); return NULL; } assert( pThData->Id >= 0 ); clk = Abc_Clock(); Kf_SetMergeOrder( pThData->pSett, Kf_ObjCuts0(pMan, pThData->Id), Kf_ObjCuts1(pMan, pThData->Id), fAreaOnly, fCutMin ); pThData->clkUsed += Abc_Clock() - clk; pThData->Status = 0; // printf( "Finished object %d\n", pThData->Id ); } assert( 0 ); return NULL; } #endif Vec_Int_t * Kf_ManCreateFaninCounts( Gia_Man_t * p ) { Vec_Int_t * vCounts; Gia_Obj_t * pObj; int i; vCounts = Vec_IntAlloc( Gia_ManObjNum(p) ); Gia_ManForEachObj( p, pObj, i ) { if ( Gia_ObjIsAnd(pObj) ) Vec_IntPush( vCounts, 2 - Gia_ObjIsCi(Gia_ObjFanin0(pObj)) - Gia_ObjIsCi(Gia_ObjFanin1(pObj)) ); else Vec_IntPush( vCounts, 0 ); } assert( Vec_IntSize(vCounts) == Gia_ManObjNum(p) ); return vCounts; } #ifdef ABC_USE_PTHREADS void Kf_ManComputeCuts( Kf_Man_t * p ) { pthread_t WorkerThread[PAR_THR_MAX]; Kf_ThData_t ThData[PAR_THR_MAX]; Vec_Int_t * vStack, * vFanins; Gia_Obj_t * pObj; int nProcs = p->pPars->nProcNum; int i, k, iFan, status, nCountFanins, fRunning; abctime clk, clkUsed = 0; assert( nProcs <= PAR_THR_MAX ); // start fanins vFanins = Kf_ManCreateFaninCounts( p->pGia ); Gia_ManStaticFanoutStart( p->pGia ); // start the stack vStack = Vec_IntAlloc( 1000 ); Gia_ManForEachObjReverse( p->pGia, pObj, k ) if ( Gia_ObjIsAnd(pObj) && Vec_IntEntry(vFanins, k) == 0 ) Vec_IntPush( vStack, k ); // start the threads for ( i = 0; i < nProcs; i++ ) { ThData[i].pSett = p->pSett + i; ThData[i].Id = -1; ThData[i].Status = 0; ThData[i].clkUsed = 0; status = pthread_create( WorkerThread + i, NULL, Kf_WorkerThread, (void *)(ThData + i) ); assert( status == 0 ); } nCountFanins = Vec_IntSum(vFanins); fRunning = 1; while ( nCountFanins > 0 || Vec_IntSize(vStack) > 0 || fRunning ) { for ( i = 0; i < nProcs; i++ ) { if ( ThData[i].Status ) continue; assert( ThData[i].Status == 0 ); if ( ThData[i].Id >= 0 ) { int iObj = ThData[i].Id; Kf_Set_t * pSett = p->pSett + i; //printf( "Closing obj %d with Thread %d:\n", iObj, i ); clk = Abc_Clock(); // finalize the results Kf_ManSaveResults( pSett->ppCuts, pSett->nCuts, pSett->pCutBest, p->vTemp ); Vec_IntWriteEntry( &p->vTime, iObj, pSett->pCutBest->Delay + 1 ); Vec_FltWriteEntry( &p->vArea, iObj, (pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, iObj) ); if ( pSett->pCutBest->nLeaves > 1 ) Kf_ManStoreAddUnit( p->vTemp, iObj, Kf_ObjTime(p, iObj), Kf_ObjArea(p, iObj) ); Kf_ObjSetCuts( p, iObj, p->vTemp ); //Gia_CutSetPrint( Kf_ObjCuts(p, iObj) ); clkUsed += Abc_Clock() - clk; // schedule other nodes Gia_ObjForEachFanoutStaticId( p->pGia, iObj, iFan, k ) { if ( !Gia_ObjIsAnd(Gia_ManObj(p->pGia, iFan)) ) continue; assert( Vec_IntEntry(vFanins, iFan) > 0 ); if ( Vec_IntAddToEntry(vFanins, iFan, -1) == 0 ) Vec_IntPush( vStack, iFan ); assert( nCountFanins > 0 ); nCountFanins--; } ThData[i].Id = -1; } if ( Vec_IntSize(vStack) > 0 ) { ThData[i].Id = Vec_IntPop( vStack ); ThData[i].Status = 1; //printf( "Scheduling %d for Thread %d\n", ThData[i].Id, i ); } } fRunning = 0; for ( i = 0; i < nProcs; i++ ) if ( ThData[i].Status == 1 || (ThData[i].Status == 0 && ThData[i].Id >= 0) ) fRunning = 1; // printf( "fRunning %d\n", fRunning ); } Vec_IntForEachEntry( vFanins, iFan, k ) if ( iFan != 0 ) { printf( "%d -> %d ", k, iFan ); Gia_ObjPrint( p->pGia, Gia_ManObj(p->pGia, k) ); } assert( Vec_IntSum(vFanins) == 0 ); // stop the threads for ( i = 0; i < nProcs; i++ ) { assert( ThData[i].Status == 0 ); ThData[i].Id = -1; ThData[i].Status = 1; } Gia_ManStaticFanoutStop( p->pGia ); Vec_IntFree( vStack ); Vec_IntFree( vFanins ); if ( !p->pPars->fVerbose ) return; // print runtime statistics printf( "Main : " ); Abc_PrintTime( 1, "Time", clkUsed ); for ( i = 0; i < nProcs; i++ ) { printf( "Thread %d : ", i ); Abc_PrintTime( 1, "Time", ThData[i].clkUsed ); } } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Kf_ManPrintStats( Kf_Man_t * p, char * pTitle ) { if ( !p->pPars->fVerbose ) return; printf( "%s : ", pTitle ); printf( "Level =%6lu ", p->pPars->Delay ); printf( "Area =%9lu ", p->pPars->Area ); printf( "Edge =%9lu ", p->pPars->Edge ); Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart ); fflush( stdout ); } void Kf_ManComputeMapping( Kf_Man_t * p ) { Gia_Obj_t * pObj; int i, iPi; if ( p->pPars->fVerbose ) { printf( "Aig: CI = %d CO = %d AND = %d ", Gia_ManCiNum(p->pGia), Gia_ManCoNum(p->pGia), Gia_ManAndNum(p->pGia) ); printf( "LutSize = %d CutMax = %d Threads = %d\n", p->pPars->nLutSize, p->pPars->nCutNum, p->pPars->nProcNum ); printf( "Computing cuts...\r" ); fflush( stdout ); } Gia_ManForEachCi( p->pGia, pObj, iPi ) { i = Gia_ObjId(p->pGia, pObj); Kf_ManStoreStart( p->vTemp, 0 ); Kf_ManStoreAddUnit( p->vTemp, i, 0, 0 ); assert( Vec_IntSize(p->vTemp) == 1 + KF_ADD_ON1 + KF_ADD_ON2 ); Kf_ObjSetCuts( p, i, p->vTemp ); } if ( p->pPars->nProcNum > 0 ) Kf_ManComputeCuts( p ); else { Gia_ManForEachAnd( p->pGia, pObj, i ) { if ( p->pPars->fCutHashing ) Kf_SetMerge( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); else if ( p->pPars->fCutSimple ) Kf_SetMergeSimple( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); else Kf_SetMergeOrder( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); Kf_ManSaveResults( p->pSett->ppCuts, p->pSett->nCuts, p->pSett->pCutBest, p->vTemp ); Vec_IntWriteEntry( &p->vTime, i, p->pSett->pCutBest->Delay + 1 ); Vec_FltWriteEntry( &p->vArea, i, (p->pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, i) ); if ( p->pSett->pCutBest->nLeaves > 1 ) Kf_ManStoreAddUnit( p->vTemp, i, Kf_ObjTime(p, i), Kf_ObjArea(p, i) ); Kf_ObjSetCuts( p, i, p->vTemp ); //Gia_CutSetPrint( Kf_ObjCuts(p, i) ); } } Kf_ManComputeRefs( p ); if ( p->pPars->fVerbose ) { printf( "CutPair = %lu ", p->pSett->CutCount[0] ); printf( "Merge = %lu ", p->pSett->CutCount[1] ); printf( "Eval = %lu ", p->pSett->CutCount[2] ); printf( "Cut = %lu ", p->pSett->CutCount[3] ); Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart ); printf( "Memory: " ); printf( "Gia = %.2f MB ", Gia_ManMemory(p->pGia) / (1<<20) ); printf( "Man = %.2f MB ", 4.0 * sizeof(int) * Gia_ManObjNum(p->pGia) / (1<<20) ); printf( "Cuts = %.2f MB ",Vec_ReportMemory(&p->pMem) / (1<<20) ); printf( "Set = %.2f KB ", 1.0 * sizeof(Kf_Set_t) / (1<<10) ); printf( "\n" ); fflush( stdout ); Kf_ManPrintStats( p, "Start" ); } } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Kf_ManSetInitRefs( Gia_Man_t * p, Vec_Flt_t * vRefs ) { Gia_Obj_t * pObj, * pCtrl, * pData0, * pData1; int i; Vec_FltFill( vRefs, Gia_ManObjNum(p), 0 ); Gia_ManForEachAnd( p, pObj, i ) { Vec_FltAddToEntry( vRefs, Gia_ObjFaninId0(pObj, i), 1 ); Vec_FltAddToEntry( vRefs, Gia_ObjFaninId1(pObj, i), 1 ); if ( !Gia_ObjIsMuxType(pObj) ) continue; // discount XOR/MUX pCtrl = Gia_ObjRecognizeMux( pObj, &pData1, &pData0 ); Vec_FltAddToEntry( vRefs, Gia_ObjId(p, Gia_Regular(pCtrl)), -1 ); if ( Gia_Regular(pData0) == Gia_Regular(pData1) ) Vec_FltAddToEntry( vRefs, Gia_ObjId(p, Gia_Regular(pData0)), -1 ); } Gia_ManForEachCo( p, pObj, i ) Vec_FltAddToEntry( vRefs, Gia_ObjFaninId0(pObj, Gia_ObjId(p, pObj)), 1 ); for ( i = 0; i < Gia_ManObjNum(p); i++ ) Vec_FltUpdateEntry( vRefs, i, 1 ); } Kf_Man_t * Kf_ManAlloc( Gia_Man_t * pGia, Jf_Par_t * pPars ) { Kf_Man_t * p; int i; assert( pPars->nLutSize <= KF_LEAF_MAX ); assert( pPars->nCutNum <= KF_CUT_MAX ); assert( pPars->nProcNum <= KF_PROC_MAX ); Vec_IntFreeP( &pGia->vMapping ); p = ABC_CALLOC( Kf_Man_t, 1 ); p->clkStart = Abc_Clock(); p->pGia = pGia; p->pPars = pPars; Vec_SetAlloc_( &p->pMem, 20 ); Vec_IntFill( &p->vCuts, Gia_ManObjNum(pGia), 0 ); Vec_IntFill( &p->vTime, Gia_ManObjNum(pGia), 0 ); Vec_FltFill( &p->vArea, Gia_ManObjNum(pGia), 0 ); Kf_ManSetInitRefs( pGia, &p->vRefs ); p->vTemp = Vec_IntAlloc( 1000 ); pGia->pRefs = ABC_CALLOC( int, Gia_ManObjNum(pGia) ); // prepare cut sets for ( i = 0; i < Abc_MaxInt(1, pPars->nProcNum); i++ ) { (p->pSett + i)->pMan = p; (p->pSett + i)->nLutSize = (unsigned short)pPars->nLutSize; (p->pSett + i)->nCutNum = (unsigned short)pPars->nCutNum; (p->pSett + i)->TableMask = (1 << KF_LOG_TABLE) - 1; } return p; } void Kf_ManFree( Kf_Man_t * p ) { ABC_FREE( p->pGia->pRefs ); ABC_FREE( p->vCuts.pArray ); ABC_FREE( p->vTime.pArray ); ABC_FREE( p->vArea.pArray ); ABC_FREE( p->vRefs.pArray ); Vec_IntFreeP( &p->vTemp ); Vec_SetFree_( &p->pMem ); ABC_FREE( p ); } Gia_Man_t * Kf_ManDerive( Kf_Man_t * p ) { Vec_Int_t * vMapping; Gia_Obj_t * pObj; int i, k, * pCut; assert( !p->pPars->fCutMin ); vMapping = Vec_IntAlloc( Gia_ManObjNum(p->pGia) + (int)p->pPars->Edge + (int)p->pPars->Area * 2 ); Vec_IntFill( vMapping, Gia_ManObjNum(p->pGia), 0 ); Gia_ManForEachAnd( p->pGia, pObj, i ) { if ( Gia_ObjIsBuf(pObj) || Gia_ObjRefNum(p->pGia, pObj) == 0 ) continue; pCut = Kf_ObjCutBest( p, i ); Vec_IntWriteEntry( vMapping, i, Vec_IntSize(vMapping) ); Vec_IntPush( vMapping, Kf_CutSize(pCut) ); for ( k = 1; k <= Kf_CutSize(pCut); k++ ) Vec_IntPush( vMapping, Kf_CutLeaf(pCut, k) ); Vec_IntPush( vMapping, i ); } assert( Vec_IntCap(vMapping) == 16 || Vec_IntSize(vMapping) == Vec_IntCap(vMapping) ); p->pGia->vMapping = vMapping; // Gia_ManMappingVerify( p->pGia ); return p->pGia; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Kf_ManSetDefaultPars( Jf_Par_t * pPars ) { memset( pPars, 0, sizeof(Jf_Par_t) ); pPars->nLutSize = 6; pPars->nCutNum = 8; pPars->nProcNum = 0; pPars->nRounds = 1; pPars->nVerbLimit = 5; pPars->DelayTarget = -1; pPars->fAreaOnly = 0; pPars->fOptEdge = 1; pPars->fCoarsen = 0; pPars->fCutMin = 0; pPars->fFuncDsd = 0; pPars->fGenCnf = 0; pPars->fPureAig = 0; pPars->fCutHashing = 0; pPars->fCutSimple = 0; pPars->fVerbose = 0; pPars->fVeryVerbose = 0; pPars->nLutSizeMax = KF_LEAF_MAX; pPars->nCutNumMax = KF_CUT_MAX; pPars->nProcNumMax = KF_PROC_MAX; } Gia_Man_t * Kf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ) { Kf_Man_t * p; Gia_Man_t * pNew; p = Kf_ManAlloc( pGia, pPars ); Kf_ManComputeMapping( p ); pNew = Kf_ManDerive( p ); Kf_ManFree( p ); return pNew; } #endif //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// #endif // pthreads are used ABC_NAMESPACE_IMPL_END