| /**CFile**************************************************************** |
| |
| FileName [giaBalance.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Scalable AIG package.] |
| |
| Synopsis [AIG balancing.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: giaBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "gia.h" |
| #include "misc/vec/vecHash.h" |
| #include "misc/vec/vecQue.h" |
| #include "opt/dau/dau.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #define BAL_LEAF_MAX 6 |
| #define BAL_CUT_MAX 8 |
| #define BAL_SUPER 50 |
| #define BAL_NO_LEAF 31 |
| #define BAL_NO_FUNC 134217727 // (1<<27)-1 |
| |
| typedef struct Bal_Cut_t_ Bal_Cut_t; |
| struct Bal_Cut_t_ |
| { |
| word Sign; // signature |
| int Delay; // delay |
| unsigned iFunc : 27; // function (BAL_NO_FUNC) |
| unsigned nLeaves : 5; // leaf number (Bal_NO_LEAF) |
| int pLeaves[BAL_LEAF_MAX]; // leaves |
| }; |
| |
| // operation manager |
| typedef struct Bal_Man_t_ Bal_Man_t; |
| struct Bal_Man_t_ |
| { |
| Gia_Man_t * pGia; // user AIG |
| int nLutSize; // LUT size |
| int nCutNum; // cut number |
| int fCutMin; // cut minimization |
| int fVerbose; // verbose |
| Gia_Man_t * pNew; // derived AIG |
| Vec_Int_t * vCosts; // cost of supergate nodes |
| Vec_Ptr_t * vCutSets; // object cutsets |
| abctime clkStart; // starting the clock |
| }; |
| |
| static inline Bal_Man_t * Bal_GiaMan( Gia_Man_t * p ) { return (Bal_Man_t *)p->pData; } |
| |
| static inline int Bal_ObjCost( Bal_Man_t * p, int i ) { return Vec_IntEntry(p->vCosts, i); } |
| static inline int Bal_LitCost( Bal_Man_t * p, int i ) { return Bal_ObjCost(p, Abc_Lit2Var(i)); } |
| static inline int Bal_ObjDelay( Bal_Man_t * p, int i ) { return Bal_ObjCost(p, i) >> 4; } |
| static inline int Bal_LitDelay( Bal_Man_t * p, int i ) { return Bal_ObjDelay(p, Abc_Lit2Var(i)); } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Bal_Man_t * Bal_ManAlloc( Gia_Man_t * pGia, Gia_Man_t * pNew, int nLutSize, int nCutNum, int fVerbose ) |
| { |
| Bal_Man_t * p; |
| p = ABC_CALLOC( Bal_Man_t, 1 ); |
| p->clkStart = Abc_Clock(); |
| p->pGia = pGia; |
| p->pNew = pNew; |
| p->nLutSize = nLutSize; |
| p->nCutNum = nCutNum; |
| p->fVerbose = fVerbose; |
| p->vCosts = Vec_IntAlloc( 3 * Gia_ManObjNum(pGia) / 2 ); |
| p->vCutSets = Vec_PtrAlloc( 3 * Gia_ManObjNum(pGia) / 2 ); |
| Vec_IntFill( p->vCosts, Gia_ManObjNum(pNew), 0 ); |
| Vec_PtrFill( p->vCutSets, Gia_ManObjNum(pNew), NULL ); |
| pNew->pData = p; |
| return p; |
| } |
| void Bal_ManFree( Bal_Man_t * p ) |
| { |
| Vec_PtrFreeFree( p->vCutSets ); |
| Vec_IntFree( p->vCosts ); |
| ABC_FREE( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Bal_CutCountBits( 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 Bal_CutGetSign( int * pLeaves, int nLeaves ) |
| { |
| word Sign = 0; int i; |
| for ( i = 0; i < nLeaves; i++ ) |
| Sign |= ((word)1) << (pLeaves[i] & 0x3F); |
| return Sign; |
| } |
| static inline int Bal_CutCreateUnit( Bal_Cut_t * p, int i, int Delay ) |
| { |
| p->iFunc = 2; |
| p->Delay = Delay; |
| p->nLeaves = 1; |
| p->pLeaves[0] = i; |
| p->Sign = ((word)1) << (i & 0x3F); |
| return 1; |
| } |
| static inline int Bal_ManPrepareSet( Bal_Man_t * p, int iObj, int Index, int fUnit, Bal_Cut_t ** ppCutSet ) |
| { |
| static Bal_Cut_t CutTemp[3]; int i; |
| if ( Vec_PtrEntry(p->vCutSets, iObj) == NULL || fUnit ) |
| return Bal_CutCreateUnit( (*ppCutSet = CutTemp + Index), iObj, Bal_ObjDelay(p, iObj)+1 ); |
| *ppCutSet = (Bal_Cut_t *)Vec_PtrEntry(p->vCutSets, iObj); |
| for ( i = 0; i < p->nCutNum; i++ ) |
| if ( (*ppCutSet)[i].nLeaves == BAL_NO_LEAF ) |
| return i; |
| return i; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Check correctness of cuts.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Bal_CutCheck( Bal_Cut_t * pBase, Bal_Cut_t * pCut ) // check if pCut is contained in pBase |
| { |
| int nSizeB = pBase->nLeaves; |
| int nSizeC = pCut->nLeaves; |
| int i, * pB = pBase->pLeaves; |
| int k, * pC = pCut->pLeaves; |
| 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 Bal_SetCheckArray( Bal_Cut_t ** ppCuts, int nCuts ) |
| { |
| Bal_Cut_t * pCut0, * pCut1; |
| int i, k, m, n, Value; |
| assert( nCuts > 0 ); |
| for ( i = 0; i < nCuts; i++ ) |
| { |
| pCut0 = ppCuts[i]; |
| assert( pCut0->nLeaves <= BAL_LEAF_MAX ); |
| assert( pCut0->Sign == Bal_CutGetSign(pCut0->pLeaves, pCut0->nLeaves) ); |
| // check duplicates |
| for ( m = 0; m < (int)pCut0->nLeaves; m++ ) |
| for ( n = m + 1; n < (int)pCut0->nLeaves; n++ ) |
| assert( pCut0->pLeaves[m] < pCut0->pLeaves[n] ); |
| // check pairs |
| for ( k = 0; k < nCuts; k++ ) |
| { |
| pCut1 = ppCuts[k]; |
| if ( pCut0 == pCut1 ) |
| continue; |
| // check containments |
| Value = Bal_CutCheck( pCut0, pCut1 ); |
| assert( Value == 0 ); |
| } |
| } |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Bal_CutMergeOrder( Bal_Cut_t * pCut0, Bal_Cut_t * pCut1, Bal_Cut_t * pCut, int nLutSize ) |
| { |
| int nSize0 = pCut0->nLeaves; |
| int nSize1 = pCut1->nLeaves; |
| int i, * pC0 = pCut0->pLeaves; |
| int k, * pC1 = pCut1->pLeaves; |
| int c, * pC = pCut->pLeaves; |
| // 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; |
| pCut->iFunc = BAL_NO_FUNC; |
| pCut->Sign = pCut0->Sign | pCut1->Sign; |
| pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay ); |
| 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; |
| pCut->iFunc = BAL_NO_FUNC; |
| pCut->Sign = pCut0->Sign | pCut1->Sign; |
| pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay ); |
| return 1; |
| |
| FlushCut1: |
| if ( c + nSize1 > nLutSize + k ) return 0; |
| while ( k < nSize1 ) |
| pC[c++] = pC1[k++]; |
| pCut->nLeaves = c; |
| pCut->iFunc = BAL_NO_FUNC; |
| pCut->Sign = pCut0->Sign | pCut1->Sign; |
| pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay ); |
| return 1; |
| } |
| static inline int Bal_CutMergeOrderMux( Bal_Cut_t * pCut0, Bal_Cut_t * pCut1, Bal_Cut_t * pCut2, Bal_Cut_t * pCut, int nLutSize ) |
| { |
| int x0, i0 = 0, nSize0 = pCut0->nLeaves, * pC0 = pCut0->pLeaves; |
| int x1, i1 = 0, nSize1 = pCut1->nLeaves, * pC1 = pCut1->pLeaves; |
| int x2, i2 = 0, nSize2 = pCut2->nLeaves, * pC2 = pCut2->pLeaves; |
| int xMin, c = 0, * pC = pCut->pLeaves; |
| while ( 1 ) |
| { |
| x0 = (i0 == nSize0) ? ABC_INFINITY : pC0[i0]; |
| x1 = (i1 == nSize1) ? ABC_INFINITY : pC1[i1]; |
| x2 = (i2 == nSize2) ? ABC_INFINITY : pC2[i2]; |
| xMin = Abc_MinInt( Abc_MinInt(x0, x1), x2 ); |
| if ( xMin == ABC_INFINITY ) break; |
| if ( c == nLutSize ) return 0; |
| pC[c++] = xMin; |
| if (x0 == xMin) i0++; |
| if (x1 == xMin) i1++; |
| if (x2 == xMin) i2++; |
| } |
| pCut->nLeaves = c; |
| pCut->iFunc = BAL_NO_FUNC; |
| pCut->Sign = pCut0->Sign | pCut1->Sign | pCut2->Sign; |
| pCut->Delay = Abc_MaxInt( pCut0->Delay, Abc_MaxInt(pCut1->Delay, pCut2->Delay) ); |
| return 1; |
| } |
| static inline int Bal_SetCutIsContainedOrder( Bal_Cut_t * pBase, Bal_Cut_t * pCut ) // check if pCut is contained in pBase |
| { |
| int i, nSizeB = pBase->nLeaves; |
| int k, nSizeC = pCut->nLeaves; |
| if ( nSizeB == nSizeC ) |
| { |
| for ( i = 0; i < nSizeB; i++ ) |
| if ( pBase->pLeaves[i] != pCut->pLeaves[i] ) |
| return 0; |
| return 1; |
| } |
| assert( nSizeB > nSizeC ); |
| if ( nSizeC == 0 ) |
| return 1; |
| 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 Bal_SetLastCutIsContained( Bal_Cut_t ** pCuts, int nCuts ) |
| { |
| int i; |
| for ( i = 0; i < nCuts; i++ ) |
| if ( pCuts[i]->nLeaves <= pCuts[nCuts]->nLeaves && (pCuts[i]->Sign & pCuts[nCuts]->Sign) == pCuts[i]->Sign && Bal_SetCutIsContainedOrder(pCuts[nCuts], pCuts[i]) ) |
| return 1; |
| return 0; |
| } |
| static inline int Bal_SetLastCutContains( Bal_Cut_t ** pCuts, int nCuts ) |
| { |
| int i, k, fChanges = 0; |
| for ( i = 0; i < nCuts; i++ ) |
| if ( pCuts[nCuts]->nLeaves < pCuts[i]->nLeaves && (pCuts[nCuts]->Sign & pCuts[i]->Sign) == pCuts[nCuts]->Sign && Bal_SetCutIsContainedOrder(pCuts[i], pCuts[nCuts]) ) |
| pCuts[i]->nLeaves = BAL_NO_LEAF, fChanges = 1; |
| if ( !fChanges ) |
| return nCuts; |
| for ( i = k = 0; i <= nCuts; i++ ) |
| { |
| if ( pCuts[i]->nLeaves == BAL_NO_LEAF ) |
| continue; |
| if ( k < i ) |
| ABC_SWAP( Bal_Cut_t *, pCuts[k], pCuts[i] ); |
| k++; |
| } |
| return k - 1; |
| } |
| static inline int Bal_CutCompareArea( Bal_Cut_t * pCut0, Bal_Cut_t * pCut1 ) |
| { |
| 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; |
| return 0; |
| } |
| static inline void Bal_SetSortByDelay( Bal_Cut_t ** pCuts, int nCuts ) |
| { |
| int i; |
| for ( i = nCuts; i > 0; i-- ) |
| { |
| if ( Bal_CutCompareArea(pCuts[i - 1], pCuts[i]) < 0 )//!= 1 ) |
| return; |
| ABC_SWAP( Bal_Cut_t *, pCuts[i - 1], pCuts[i] ); |
| } |
| } |
| static inline int Bal_SetAddCut( Bal_Cut_t ** pCuts, int nCuts, int nCutNum ) |
| { |
| if ( nCuts == 0 ) |
| return 1; |
| nCuts = Bal_SetLastCutContains(pCuts, nCuts); |
| Bal_SetSortByDelay( pCuts, nCuts ); |
| return Abc_MinInt( nCuts + 1, nCutNum - 1 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Bal_ManDeriveCuts( Bal_Man_t * p, int iFan0, int iFan1, int iFan2, int fCompl0, int fCompl1, int fCompl2, int fUnit0, int fUnit1, int fUnit2, int fIsXor, int Target, int fSave ) |
| { |
| Bal_Cut_t pCutSet[BAL_CUT_MAX], * pCutsR[BAL_CUT_MAX]; |
| Bal_Cut_t * pCutSet0, * pCutSet1, * pCutSet2; |
| int nCuts0 = Bal_ManPrepareSet( p, iFan0, 0, fUnit0, &pCutSet0 ); |
| int nCuts1 = Bal_ManPrepareSet( p, iFan1, 1, fUnit1, &pCutSet1 ); |
| Bal_Cut_t * pCut0, * pCut0Lim = pCutSet0 + nCuts0; |
| Bal_Cut_t * pCut1, * pCut1Lim = pCutSet1 + nCuts1; |
| int i, Cost, nCutsR = 0; |
| memset( pCutSet, 0, sizeof(Bal_Cut_t) * p->nCutNum ); |
| for ( i = 0; i < p->nCutNum; i++ ) |
| pCutsR[i] = pCutSet + i; |
| // enumerate cuts |
| if ( iFan2 > 0 ) |
| { |
| int nCuts2 = Bal_ManPrepareSet( p, iFan2, 2, fUnit2, &pCutSet2 ); |
| Bal_Cut_t * pCut2, * pCut2Lim = pCutSet2 + nCuts2; |
| for ( pCut0 = pCutSet0; pCut0 < pCut0Lim; pCut0++ ) |
| for ( pCut1 = pCutSet1; pCut1 < pCut1Lim; pCut1++ ) |
| for ( pCut2 = pCutSet2; pCut2 < pCut2Lim; pCut2++ ) |
| { |
| if ( Bal_CutCountBits(pCut0->Sign | pCut1->Sign | pCut2->Sign) > p->nLutSize ) |
| continue; |
| if ( !Bal_CutMergeOrderMux(pCut0, pCut1, pCut2, pCutsR[nCutsR], p->nLutSize) ) |
| continue; |
| assert( pCutsR[nCutsR]->Delay == Target ); |
| if ( Bal_SetLastCutIsContained(pCutsR, nCutsR) ) |
| continue; |
| // if ( p->fCutMin && Bal_CutComputeTruthMux(p, pCut0, pCut1, pCut2, fCompl0, fCompl1, fCompl2, pCutsR[nCutsR]) ) |
| // pCutsR[nCutsR]->Sign = Bal_CutGetSign(pCutsR[nCutsR]->pLeaves, pCutsR[nCutsR]->nLeaves); |
| nCutsR = Bal_SetAddCut( pCutsR, nCutsR, p->nCutNum ); |
| } |
| } |
| else |
| { |
| for ( pCut0 = pCutSet0; pCut0 < pCut0Lim; pCut0++ ) |
| for ( pCut1 = pCutSet1; pCut1 < pCut1Lim; pCut1++ ) |
| { |
| if ( Bal_CutCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize ) |
| continue; |
| if ( !Bal_CutMergeOrder(pCut0, pCut1, pCutsR[nCutsR], p->nLutSize) ) |
| continue; |
| assert( pCutsR[nCutsR]->Delay == Target ); |
| if ( Bal_SetLastCutIsContained(pCutsR, nCutsR) ) |
| continue; |
| // if ( p->fCutMin && Bal_CutComputeTruth(p, pCut0, pCut1, fCompl0, fCompl1, pCutsR[nCutsR], fIsXor) ) |
| // pCutsR[nCutsR]->Sign = Bal_CutGetSign(pCutsR[nCutsR]->pLeaves, pCutsR[nCutsR]->nLeaves); |
| nCutsR = Bal_SetAddCut( pCutsR, nCutsR, p->nCutNum ); |
| } |
| } |
| if ( nCutsR == 0 ) |
| return -1; |
| //printf( "%d ", nCutsR ); |
| Cost = ((pCutsR[0]->Delay << 4) | pCutsR[0]->nLeaves); |
| // verify |
| assert( nCutsR > 0 && nCutsR < p->nCutNum ); |
| assert( Bal_SetCheckArray(pCutsR, nCutsR) ); |
| // save cuts |
| if ( fSave && Cost >= 0 ) |
| { |
| pCutSet0 = ABC_CALLOC( Bal_Cut_t, p->nCutNum ); |
| Vec_PtrPush( p->vCutSets, pCutSet0 ); |
| assert( Vec_PtrSize(p->vCutSets) == Gia_ManObjNum(p->pNew) ); |
| for ( i = 0; i < nCutsR; i++ ) |
| pCutSet0[i] = *pCutsR[i]; |
| for ( ; i < p->nCutNum; i++ ) |
| pCutSet0[i].nLeaves = BAL_NO_LEAF; |
| Vec_IntPush( p->vCosts, Cost ); |
| assert( Vec_IntSize(p->vCosts) == Gia_ManObjNum(p->pNew) ); |
| } |
| return Cost; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Bal_ManSetGateLevel( Bal_Man_t * p, Gia_Obj_t * pObjOld, int iLitNew ) |
| { |
| int iFan0, iFan1, iFan2, Cost; |
| int fCompl0, fCompl1, fCompl2; |
| int fUnit0, fUnit1, fUnit2; |
| int Delay0, Delay1, Delay2, DelayMax; |
| int iObjNew = Abc_Lit2Var(iLitNew); |
| Gia_Obj_t * pObjNew = Gia_ManObj( p->pNew, iObjNew ); |
| int fMux = Gia_ObjIsMux(p->pNew, pObjNew); |
| if ( iObjNew < Vec_PtrSize(p->vCutSets) ) |
| return -1; |
| iFan0 = Gia_ObjFaninId0( pObjNew, iObjNew ); |
| iFan1 = Gia_ObjFaninId1( pObjNew, iObjNew ); |
| iFan2 = fMux ? Gia_ObjFaninId2(p->pNew, iObjNew) : 0; |
| fCompl0 = Gia_ObjFaninC0( pObjNew ); |
| fCompl1 = Gia_ObjFaninC1( pObjNew ); |
| fCompl2 = fMux ? Gia_ObjFaninC2(p->pNew, pObjNew) : 0; |
| Delay0 = Bal_ObjDelay( p, iFan0 ); |
| Delay1 = Bal_ObjDelay( p, iFan1 ); |
| Delay2 = Bal_ObjDelay( p, iFan2 ); |
| DelayMax = Abc_MaxInt( Delay0, Abc_MaxInt(Delay1, Delay2) ); |
| fUnit0 = (int)(Delay0 != DelayMax); |
| fUnit1 = (int)(Delay1 != DelayMax); |
| fUnit2 = (int)(Delay2 != DelayMax); |
| if ( DelayMax > 0 ) |
| { |
| //printf( "A" ); |
| Cost = Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, Gia_ObjIsXor(pObjNew), DelayMax, 1 ); |
| //printf( "B" ); |
| if ( Cost >= 0 ) |
| return Cost; |
| } |
| DelayMax++; |
| fUnit0 = fUnit1 = fUnit2 = 1; |
| //printf( "A" ); |
| Cost = Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, Gia_ObjIsXor(pObjNew), DelayMax, 1 ); |
| //printf( "B" ); |
| assert( Cost >= 0 ); |
| return Cost; |
| } |
| int Bal_ManEvalTwo( Bal_Man_t * p, int iLitNew0, int iLitNew1, int iLitNew2, int fIsXor ) |
| { |
| int iFan0 = Abc_Lit2Var( iLitNew0 ); |
| int iFan1 = Abc_Lit2Var( iLitNew1 ); |
| int iFan2 = Abc_Lit2Var( iLitNew2 ); |
| int fCompl0 = Abc_LitIsCompl( iLitNew0 ); |
| int fCompl1 = Abc_LitIsCompl( iLitNew1 ); |
| int fCompl2 = Abc_LitIsCompl( iLitNew2 ); |
| int Delay0 = Bal_ObjDelay( p, iFan0 ); |
| int Delay1 = Bal_ObjDelay( p, iFan1 ); |
| int Delay2 = Bal_ObjDelay( p, iFan2 ); |
| int DelayMax = Abc_MaxInt( Delay0, Abc_MaxInt(Delay1, Delay2) ); |
| int fUnit0 = (int)(Delay0 != DelayMax); |
| int fUnit1 = (int)(Delay1 != DelayMax); |
| int fUnit2 = (int)(Delay2 != DelayMax); |
| if ( DelayMax == 0 ) |
| return -1; |
| return Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, fIsXor, DelayMax, 0 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Sort literals by their cost.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Vec_IntSelectSortCostLit( Vec_Int_t * vSuper, Vec_Int_t * vCosts ) |
| { |
| int * pArray = Vec_IntArray(vSuper); |
| int nSize = Vec_IntSize(vSuper); |
| int i, j, best_i; |
| for ( i = 0; i < nSize-1; i++ ) |
| { |
| best_i = i; |
| for ( j = i+1; j < nSize; j++ ) |
| if ( Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[j])) > Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[best_i])) ) |
| best_i = j; |
| ABC_SWAP( int, pArray[i], pArray[best_i] ); |
| } |
| } |
| static inline void Vec_IntPushOrderCost2( Vec_Int_t * vSuper, Vec_Int_t * vCosts, int iLit ) |
| { |
| int i, nSize, * pArray; |
| Vec_IntPush( vSuper, iLit ); |
| pArray = Vec_IntArray(vSuper); |
| nSize = Vec_IntSize(vSuper); |
| for ( i = nSize-1; i > 0; i-- ) |
| { |
| if ( Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[i])) <= Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[i - 1])) ) |
| return; |
| ABC_SWAP( int, pArray[i], pArray[i - 1] ); |
| } |
| } |
| static inline int Vec_IntFindFirstSameDelayAsLast( Bal_Man_t * p, Vec_Int_t * vSuper ) |
| { |
| int i, DelayCur, Delay = Bal_LitDelay( p, Vec_IntEntryLast(vSuper) ); |
| assert( Vec_IntSize(vSuper) > 1 ); |
| for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- ) |
| { |
| DelayCur = Bal_LitDelay( p, Vec_IntEntry(vSuper, i-1) ); |
| assert( DelayCur >= Delay ); |
| if ( DelayCur > Delay ) |
| return i; |
| } |
| return i; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Select the best pair to merge.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Bal_ManFindBestPair( Bal_Man_t * p, Vec_Int_t * vSuper, Gia_Obj_t * pObj ) |
| { |
| int * pSuper = Vec_IntArray(vSuper); |
| int iBeg = Vec_IntFindFirstSameDelayAsLast( p, vSuper ); |
| int iEnd = Vec_IntSize(vSuper)-1; |
| int i, k, iBest = -1, kBest = -1, BestCost = ABC_INFINITY, Cost; |
| assert( iBeg <= iEnd ); |
| // check if we can add to the higher levels without increasing cost |
| for ( k = iBeg-1; k >= 0; k-- ) |
| for ( i = iEnd; i >= iBeg; i-- ) |
| { |
| Cost = Bal_ManEvalTwo( p, pSuper[i], pSuper[k], 0, Gia_ObjIsXor(pObj) ); |
| if ( Cost == -1 ) |
| continue; |
| if ( Cost == Bal_LitCost(p, pSuper[k]) ) |
| { |
| // printf( "A" ); |
| return (k << 16)|i; |
| } |
| if ( BestCost > Cost ) |
| BestCost = Cost, iBest = i, kBest = k; |
| } |
| if ( BestCost != ABC_INFINITY && (BestCost >> 4) == Bal_LitDelay(p, pSuper[kBest]) ) |
| { |
| // printf( "B" ); |
| return (kBest << 16)|iBest; |
| } |
| // check if some can be added to lowest level without increasing cost |
| BestCost = ABC_INFINITY; |
| for ( i = iBeg; i <= iEnd; i++ ) |
| for ( k = i+1; k <= iEnd; k++ ) |
| { |
| Cost = Bal_ManEvalTwo( p, pSuper[i], pSuper[k], 0, Gia_ObjIsXor(pObj) ); |
| if ( Cost == -1 ) |
| continue; |
| if ( Cost == Abc_MaxInt(Bal_LitCost(p, pSuper[i]), Bal_LitCost(p, pSuper[k])) ) |
| { |
| // printf( "C" ); |
| return (k << 16)|i; |
| } |
| if ( BestCost > Cost ) |
| BestCost = Cost, iBest = i, kBest = k; |
| } |
| if ( BestCost != ABC_INFINITY ) |
| { |
| // printf( "D" ); |
| return (kBest << 16)|iBest; |
| } |
| // printf( "E" ); |
| // group pairs from lowest level based on proximity |
| return (iEnd << 16)|(iEnd-1); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Simplify multi-input AND/XOR.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Gia_ManSimplifyXor( Vec_Int_t * vSuper ) |
| { |
| int i, k = 0, Prev = -1, This, fCompl = 0; |
| Vec_IntForEachEntry( vSuper, This, i ) |
| { |
| if ( This == 0 ) |
| continue; |
| if ( This == 1 ) |
| fCompl ^= 1; |
| else if ( Prev != This ) |
| Vec_IntWriteEntry( vSuper, k++, This ), Prev = This; |
| else |
| Prev = -1, k--; |
| } |
| Vec_IntShrink( vSuper, k ); |
| if ( Vec_IntSize( vSuper ) == 0 ) |
| Vec_IntPush( vSuper, fCompl ); |
| else if ( fCompl ) |
| Vec_IntWriteEntry( vSuper, 0, Abc_LitNot(Vec_IntEntry(vSuper, 0)) ); |
| } |
| static inline void Gia_ManSimplifyAnd( Vec_Int_t * vSuper ) |
| { |
| int i, k = 0, Prev = -1, This; |
| Vec_IntForEachEntry( vSuper, This, i ) |
| { |
| if ( This == 0 ) |
| { Vec_IntFill(vSuper, 1, 0); return; } |
| if ( This == 1 ) |
| continue; |
| if ( Prev == -1 || Abc_Lit2Var(Prev) != Abc_Lit2Var(This) ) |
| Vec_IntWriteEntry( vSuper, k++, This ), Prev = This; |
| else if ( Prev != This ) |
| { Vec_IntFill(vSuper, 1, 0); return; } |
| } |
| Vec_IntShrink( vSuper, k ); |
| if ( Vec_IntSize( vSuper ) == 0 ) |
| Vec_IntPush( vSuper, 1 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collect multi-input AND/XOR.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Gia_ManSuperCollectXor_rec( Gia_Man_t * p, Gia_Obj_t * pObj ) |
| { |
| assert( !Gia_IsComplement(pObj) ); |
| if ( !Gia_ObjIsXor(pObj) || |
| // Gia_ObjRefNum(p, pObj) > 1 || |
| Gia_ObjRefNum(p, pObj) > 3 || |
| // (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || |
| Vec_IntSize(p->vSuper) > BAL_SUPER ) |
| { |
| Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) ); |
| return; |
| } |
| assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ); |
| Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj) ); |
| Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj) ); |
| } |
| static inline void Gia_ManSuperCollectAnd_rec( Gia_Man_t * p, Gia_Obj_t * pObj ) |
| { |
| if ( Gia_IsComplement(pObj) || |
| !Gia_ObjIsAndReal(p, pObj) || |
| // Gia_ObjRefNum(p, pObj) > 1 || |
| Gia_ObjRefNum(p, pObj) > 3 || |
| // (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || |
| Vec_IntSize(p->vSuper) > BAL_SUPER ) |
| { |
| Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) ); |
| return; |
| } |
| Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) ); |
| Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) ); |
| } |
| static inline void Gia_ManSuperCollect( Gia_Man_t * p, Gia_Obj_t * pObj ) |
| { |
| // int nSize; |
| if ( p->vSuper == NULL ) |
| p->vSuper = Vec_IntAlloc( 1000 ); |
| else |
| Vec_IntClear( p->vSuper ); |
| if ( Gia_ObjIsXor(pObj) ) |
| { |
| assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ); |
| Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj) ); |
| Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj) ); |
| // nSize = Vec_IntSize(vSuper); |
| Vec_IntSort( p->vSuper, 0 ); |
| Gia_ManSimplifyXor( p->vSuper ); |
| // if ( nSize != Vec_IntSize(vSuper) ) |
| // printf( "X %d->%d ", nSize, Vec_IntSize(vSuper) ); |
| } |
| else if ( Gia_ObjIsAndReal(p, pObj) ) |
| { |
| Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) ); |
| Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) ); |
| // nSize = Vec_IntSize(vSuper); |
| Vec_IntSort( p->vSuper, 0 ); |
| Gia_ManSimplifyAnd( p->vSuper ); |
| // if ( nSize != Vec_IntSize(vSuper) ) |
| // printf( "A %d->%d ", nSize, Vec_IntSize(vSuper) ); |
| } |
| else assert( 0 ); |
| // if ( nSize > 10 ) |
| // printf( "%d ", nSize ); |
| assert( Vec_IntSize(p->vSuper) > 0 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Gia_ManCreateGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper ) |
| { |
| int iLit0 = Vec_IntPop(vSuper); |
| int iLit1 = Vec_IntPop(vSuper); |
| int iLit, i; |
| if ( !Gia_ObjIsXor(pObj) ) |
| iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 ); |
| else if ( pNew->pMuxes ) |
| iLit = Gia_ManHashXorReal( pNew, iLit0, iLit1 ); |
| else |
| iLit = Gia_ManHashXor( pNew, iLit0, iLit1 ); |
| Vec_IntPush( vSuper, iLit ); |
| Bal_ManSetGateLevel( Bal_GiaMan(pNew), pObj, iLit ); |
| // Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(iLit)) ); |
| // shift to the corrent location |
| for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- ) |
| { |
| int iLit1 = Vec_IntEntry(vSuper, i); |
| int iLit2 = Vec_IntEntry(vSuper, i-1); |
| if ( Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1)) <= Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) ) |
| break; |
| Vec_IntWriteEntry( vSuper, i, iLit2 ); |
| Vec_IntWriteEntry( vSuper, i-1, iLit1 ); |
| } |
| } |
| static inline int Gia_ManBalanceGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper, int * pLits, int nLits ) |
| { |
| Vec_IntClear( vSuper ); |
| if ( nLits == 1 ) |
| Vec_IntPush( vSuper, pLits[0] ); |
| else if ( nLits == 2 ) |
| { |
| Vec_IntPush( vSuper, pLits[0] ); |
| Vec_IntPush( vSuper, pLits[1] ); |
| Gia_ManCreateGate( pNew, pObj, vSuper ); |
| } |
| else if ( nLits > 2 ) |
| { |
| Bal_Man_t * p = Bal_GiaMan(pNew); int i; |
| for ( i = 0; i < nLits; i++ ) |
| Vec_IntPush( vSuper, pLits[i] ); |
| // sort by level/cut-size |
| Vec_IntSelectSortCostLit( vSuper, p->vCosts ); |
| // iterate till everything is grouped |
| while ( Vec_IntSize(vSuper) > 1 ) |
| { |
| int iLit, Res = Bal_ManFindBestPair( p, vSuper, pObj ); |
| int iBest = Vec_IntEntry( vSuper, Res >> 16 ); |
| int kBest = Vec_IntEntry( vSuper, Res & 0xFFFF ); |
| Vec_IntRemove( vSuper, iBest ); |
| Vec_IntRemove( vSuper, kBest ); |
| if ( Gia_ObjIsXor(pObj) ) |
| iLit = Gia_ManHashXorReal( pNew, iBest, kBest ); |
| else |
| iLit = Gia_ManHashAnd( pNew, iBest, kBest ); |
| Bal_ManSetGateLevel( p, pObj, iLit ); |
| Vec_IntPushOrderCost2( vSuper, p->vCosts, iLit ); |
| } |
| } |
| // consider trivial case |
| assert( Vec_IntSize(vSuper) == 1 ); |
| return Vec_IntEntry(vSuper, 0); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Gia_ManBalance_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj ) |
| { |
| int i, iLit, iBeg, iEnd; |
| if ( ~pObj->Value ) |
| return; |
| assert( Gia_ObjIsAnd(pObj) ); |
| // handle MUX |
| if ( Gia_ObjIsMux(p, pObj) ) |
| { |
| Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) ); |
| Gia_ManBalance_rec( pNew, p, Gia_ObjFanin1(pObj) ); |
| Gia_ManBalance_rec( pNew, p, Gia_ObjFanin2(p, pObj) ); |
| pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) ); |
| Bal_ManSetGateLevel( Bal_GiaMan(pNew), pObj, pObj->Value ); |
| // Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) ); |
| return; |
| } |
| // find supergate |
| Gia_ManSuperCollect( p, pObj ); |
| // save entries |
| if ( p->vStore == NULL ) |
| p->vStore = Vec_IntAlloc( 1000 ); |
| iBeg = Vec_IntSize( p->vStore ); |
| Vec_IntAppend( p->vStore, p->vSuper ); |
| iEnd = Vec_IntSize( p->vStore ); |
| // call recursively |
| Vec_IntForEachEntryStartStop( p->vStore, iLit, i, iBeg, iEnd ) |
| { |
| Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(iLit) ); |
| Gia_ManBalance_rec( pNew, p, pTemp ); |
| Vec_IntWriteEntry( p->vStore, i, Abc_LitNotCond(pTemp->Value, Abc_LitIsCompl(iLit)) ); |
| } |
| assert( Vec_IntSize(p->vStore) == iEnd ); |
| // consider general case |
| pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, Vec_IntEntryP(p->vStore, iBeg), iEnd-iBeg ); |
| Vec_IntShrink( p->vStore, iBeg ); |
| } |
| static inline Gia_Man_t * Gia_ManBalanceInt( Gia_Man_t * p, int nLutSize, int nCutNum, int fVerbose ) |
| { |
| Bal_Man_t * pMan; |
| Gia_Man_t * pNew, * pTemp; |
| Gia_Obj_t * pObj; |
| int i; |
| Gia_ManFillValue( p ); |
| Gia_ManCreateRefs( p ); |
| // start the new manager |
| pNew = Gia_ManStart( 3*Gia_ManObjNum(p)/2 ); |
| pNew->pName = Abc_UtilStrsav( p->pName ); |
| pNew->pSpec = Abc_UtilStrsav( p->pSpec ); |
| pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc ); |
| pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc ); |
| // create constant and inputs |
| Gia_ManConst0(p)->Value = 0; |
| Gia_ManForEachCi( p, pObj, i ) |
| pObj->Value = Gia_ManAppendCi( pNew ); |
| // create balancing manager |
| pMan = Bal_ManAlloc( p, pNew, nLutSize, nCutNum, fVerbose ); |
| // create internal nodes |
| Gia_ManHashStart( pNew ); |
| Gia_ManForEachCo( p, pObj, i ) |
| Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) ); |
| Gia_ManForEachCo( p, pObj, i ) |
| pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); |
| // if ( fVerbose ) |
| { |
| int nLevelMax = 0; |
| Gia_ManForEachCo( pNew, pObj, i ) |
| { |
| nLevelMax = Abc_MaxInt( nLevelMax, Bal_ObjDelay(pMan, Gia_ObjFaninId0p(pNew, pObj)) ); |
| // printf( "%d=%d ", i, Bal_ObjDelay(pMan, Gia_ObjFaninId0p(pNew, pObj)) ); |
| } |
| printf( "Best delay = %d\n", nLevelMax ); |
| } |
| |
| // assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) ); |
| Gia_ManHashStop( pNew ); |
| Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); |
| // delete manager |
| Bal_ManFree( pMan ); |
| // perform cleanup |
| pNew = Gia_ManCleanup( pTemp = pNew ); |
| Gia_ManStop( pTemp ); |
| return pNew; |
| } |
| Gia_Man_t * Gia_ManBalanceLut( Gia_Man_t * p, int nLutSize, int nCutNum, int fVerbose ) |
| { |
| Gia_Man_t * pNew, * pNew1, * pNew2; |
| if ( fVerbose ) Gia_ManPrintStats( p, NULL ); |
| pNew = Gia_ManDupMuxes( p, 2 ); |
| if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); |
| pNew1 = Gia_ManBalanceInt( pNew, nLutSize, nCutNum, fVerbose ); |
| if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL ); |
| Gia_ManStop( pNew ); |
| pNew2 = Gia_ManDupNoMuxes( pNew1 ); |
| if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL ); |
| Gia_ManStop( pNew1 ); |
| return pNew2; |
| } |
| |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
