From ace340997bfbbbae838c5f06956d06511739f37d Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 22 Mar 2014 16:24:44 -0700 Subject: Experiments with mapping. --- src/aig/gia/giaKf.c | 959 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 959 insertions(+) create mode 100644 src/aig/gia/giaKf.c (limited to 'src/aig/gia/giaKf.c') diff --git a/src/aig/gia/giaKf.c b/src/aig/gia/giaKf.c new file mode 100644 index 00000000..e44c8bcb --- /dev/null +++ b/src/aig/gia/giaKf.c @@ -0,0 +1,959 @@ +/**CFile**************************************************************** + + FileName [giaCutt.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: giaCutt.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" +#include "misc/vec/vecSet.h" + +ABC_NAMESPACE_IMPL_START + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define KF_PROC_MAX 8 +#define KF_LEAF_MAX 8 +#define KF_WORD_MAX ((KF_LEAF_MAX > 6) ? 1 << (KF_LEAF_MAX-6) : 1) +#define KF_LOG_TABLE 8 +#define KF_NUM_MAX 16 + +#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]; + Kf_Cut_t pCuts0[KF_NUM_MAX]; + Kf_Cut_t pCuts1[KF_NUM_MAX]; + Kf_Cut_t pCutsR[KF_NUM_MAX*KF_NUM_MAX]; + Kf_Cut_t * ppCuts[KF_NUM_MAX]; + 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_ListForEachCutt( p, iList, pCut ) for ( pCut = Kf_SetCut(p, p->pList[iList]); pCut; pCut = Kf_SetCut(p, pCut->iNext) ) +#define Kf_ListForEachCuttP( 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_NUM_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_ListForEachCuttP( 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 Kf_Cut_t * Kf_SetSelectBest( Kf_Set_t * p, int fArea, int fSort ) +{ +// int fArea = p->pMan->pPars->fArea; + Kf_Cut_t * pCut, * pCutBest; + int i, nCuts = 0; + for ( i = 0; i <= p->nLutSize; i++ ) + Kf_ListForEachCutt( p, i, pCut ) + nCuts = Kf_SetStoreAddOne( p, nCuts, p->nCutNum-1, pCut, fArea ); + assert( nCuts > 0 && nCuts < p->nCutNum ); + p->nCuts = nCuts; + if ( !fSort ) + return p->ppCuts[0]; + // sort by size in the reverse order + pCutBest = p->ppCuts[0]; + 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_ListForEachCutt( p, i, pCut ) + p->ppCuts[p->nCuts++] = pCut; + assert( p->nCuts == nCuts ); + return pCutBest; +} + +/**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->pPlace[i] = 0; + p->nTEntries = iStart; +} + +/**Function************************************************************* + + Synopsis [Cut merging with arbitary order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +// 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_ListForEachCutt( 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_ListForEachCuttP( p, i, pCut0, pPlace ) + { + Kf_HashPopulate( p, pCut0 ); + for ( k = 0; k < pCut0->nLeaves; k++ ) + Kf_ListForEachCutt( p, k, pCut1 ) + if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutDominatedByThis(p, pCut1) ) + { k = pCut0->nLeaves + 1; 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++ ) + { + 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; + 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 Kf_Cut_t * Kf_SetMerge( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) +{ + int c0, c1; + Kf_SetPrepare( p, pCuts0, pCuts1 ); + 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 ); + } + Kf_SetFilter( p ); + p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum ); + return Kf_SetSelectBest( p, fArea, 1 ); +} + +/**Function************************************************************* + + Synopsis [Cut merging with fixed 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; +} +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_SetMergeOrder( 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_SetRemoveDuplicates2( Kf_Set_t * p, Kf_Cut_t * pCutNew ) +{ + Kf_Cut_t * pCut; + Kf_ListForEachCutt( p, pCutNew->nLeaves, pCut ) + if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedOrder(pCut, pCutNew) ) + return 1; + return 0; +} +static inline void Kf_SetFilter2( 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_ListForEachCuttP( p, i, pCut0, pPlace ) + { + for ( k = 0; k < pCut0->nLeaves; k++ ) + Kf_ListForEachCutt( p, k, pCut1 ) + if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedOrder(pCut0, pCut1) ) + { k = pCut0->nLeaves + 1; 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_TtStretch( uTruth0, LutSize, pCut0 + 1, Kf_CutSize(pCut0), pCutOut + 1, Kf_CutSize(pCutOut) ); + Abc_TtStretch( 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 Kf_Cut_t * Kf_SetMerge2( 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 ( Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize ) + continue; + p->CutCount[1]++; + pCutR = p->pCutsR + p->nCuts; + if ( !Kf_SetMergeOrder(pCut0, pCut1, pCutR, p->nLutSize) ) + continue; + p->CutCount[2]++; + pCutR->Sign = pCut0->Sign | pCut1->Sign; + if ( Kf_SetRemoveDuplicates2(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_SetFilter2( p ); + p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); + return Kf_SetSelectBest( p, fArea, 0 ); +} + + +/**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_CutPrintSetPrint( 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 [] + +***********************************************************************/ +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 ) +{ + Kf_Cut_t * pCutBest; + Gia_Obj_t * pObj; int i; + 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 Rounds = %d\n", p->pPars->nLutSize, p->pPars->nCutNum, p->pPars->nRounds ); + printf( "Computing cuts...\r" ); + fflush( stdout ); + } + Gia_ManForEachObj( p->pGia, pObj, i ) + { + if ( Gia_ObjIsCi(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 ); + } + else if ( Gia_ObjIsAnd(pObj) ) + { + pCutBest = Kf_SetMerge2( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); +// pCutBest = Kf_SetMerge( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); + Kf_ManSaveResults( p->pSett->ppCuts, p->pSett->nCuts, pCutBest, p->vTemp ); + Vec_IntWriteEntry( &p->vTime, i, pCutBest->Delay + 1 ); + Vec_FltWriteEntry( &p->vArea, i, (pCutBest->Area + 1)/Kf_ObjRefs(p, i) ); + if ( pCutBest->nLeaves > 1 ) + Kf_ManStoreAddUnit( p->vTemp, i, Kf_ObjTime(p, i), Kf_ObjArea(p, i) ); + Kf_ObjSetCuts( p, i, p->vTemp ); +// Gia_CutPrintSetPrint( 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->nLutSizeMax <= KF_LEAF_MAX ); + assert( pPars->nCutNumMax <= KF_NUM_MAX ); + assert( pPars->nProcNumMax <= 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 < pPars->nProcNumMax; 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->nRounds = 1; + pPars->nVerbLimit = 5; + pPars->DelayTarget = -1; + pPars->fAreaOnly = 1; + pPars->fOptEdge = 1; + pPars->fCoarsen = 0; + pPars->fCutMin = 0; + pPars->fFuncDsd = 0; + pPars->fGenCnf = 0; + pPars->fPureAig = 0; + pPars->fVerbose = 0; + pPars->fVeryVerbose = 0; + pPars->nLutSizeMax = KF_LEAF_MAX; + pPars->nCutNumMax = KF_NUM_MAX; + pPars->nProcNumMax = 1; +} +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; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + -- cgit v1.2.3