From 13dd4eeb590099a7653eb648d34e1a26010b6beb Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 22 Jun 2014 00:50:07 -0700 Subject: Experiments with balancing. --- src/aig/gia/giaBalance2.c | 981 ++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/giaMan.c | 2 +- src/aig/gia/module.make | 1 + src/base/abci/abc.c | 80 ++++ 4 files changed, 1063 insertions(+), 1 deletion(-) create mode 100644 src/aig/gia/giaBalance2.c (limited to 'src') diff --git a/src/aig/gia/giaBalance2.c b/src/aig/gia/giaBalance2.c new file mode 100644 index 00000000..e3d62410 --- /dev/null +++ b/src/aig/gia/giaBalance2.c @@ -0,0 +1,981 @@ +/**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 + +typedef struct Bal_Cut_t_ Bal_Cut_t; +struct Bal_Cut_t_ +{ + word Sign; // signature + int Delay; // delay + unsigned iFunc : 27; // function + 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 = -1; + 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 = -1; + 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 = -1; + 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 = -1; + 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_IntPushOrderCost( 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_IntPushOrderCost( 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 + diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index a0880837..51a78472 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -385,7 +385,7 @@ void Gia_ManPrintChoiceStats( Gia_Man_t * p ) void Gia_ManPrintStats( Gia_Man_t * p, Gps_Par_t * pPars ) { extern float Gia_ManLevelAve( Gia_Man_t * p ); - if ( pPars->fMiter ) + if ( pPars && pPars->fMiter ) { Gia_ManPrintStatsMiter( p, 0 ); return; diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index 9664c78d..d3d84b48 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -3,6 +3,7 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaAiger.c \ src/aig/gia/giaAigerExt.c \ src/aig/gia/giaBalance.c \ + src/aig/gia/giaBalance2.c \ src/aig/gia/giaBidec.c \ src/aig/gia/giaCCof.c \ src/aig/gia/giaCex.c \ diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 3c2d0c4f..a7e8c384 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -350,6 +350,7 @@ static int Abc_CommandAbc9Bidec ( Abc_Frame_t * pAbc, int argc, cha static int Abc_CommandAbc9Shrink ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Fx ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Balance ( Abc_Frame_t * pAbc, int argc, char ** argv ); +static int Abc_CommandAbc9BalanceLut ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Syn2 ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Syn3 ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Syn4 ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -928,6 +929,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) Cmd_CommandAdd( pAbc, "ABC9", "&shrink", Abc_CommandAbc9Shrink, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&fx", Abc_CommandAbc9Fx, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&b", Abc_CommandAbc9Balance, 0 ); + Cmd_CommandAdd( pAbc, "ABC9", "&blut", Abc_CommandAbc9BalanceLut, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&syn2", Abc_CommandAbc9Syn2, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&syn3", Abc_CommandAbc9Syn3, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&syn4", Abc_CommandAbc9Syn4, 0 ); @@ -27755,6 +27757,84 @@ usage: return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_CommandAbc9BalanceLut( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + extern Gia_Man_t * Gia_ManBalanceLut( Gia_Man_t * p, int nLutSize, int nCutNum, int fVerbose ); + Gia_Man_t * pTemp = NULL; + int nLutSize = 6; + int nCutNum = 8; + int c, fVerbose = 0; + int fVeryVerbose = 0; + Extra_UtilGetoptReset(); + while ( ( c = Extra_UtilGetopt( argc, argv, "KCvwh" ) ) != EOF ) + { + switch ( c ) + { + case 'K': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-K\" should be followed by a char string.\n" ); + goto usage; + } + nLutSize = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nLutSize < 0 ) + goto usage; + break; + case 'C': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-C\" should be followed by a char string.\n" ); + goto usage; + } + nCutNum = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nCutNum < 0 ) + goto usage; + break; + case 'v': + fVerbose ^= 1; + break; + case 'w': + fVeryVerbose ^= 1; + break; + case 'h': + goto usage; + default: + goto usage; + } + } + if ( pAbc->pGia == NULL ) + { + Abc_Print( -1, "Abc_CommandAbc9BalanceLut(): There is no AIG.\n" ); + return 1; + } + pTemp = Gia_ManBalanceLut( pAbc->pGia, nLutSize, nCutNum, fVerbose ); + Abc_FrameUpdateGia( pAbc, pTemp ); + return 0; + +usage: + Abc_Print( -2, "usage: &blut [-KC num] [-vh]\n" ); + Abc_Print( -2, "\t performs AIG balancing for the given LUT size\n" ); + Abc_Print( -2, "\t-K num : LUT size for the mapping (2 <= K <= %d) [default = %d]\n", 6, nLutSize ); + Abc_Print( -2, "\t-C num : the max number of priority cuts (1 <= C <= %d) [default = %d]\n", 8, nCutNum ); + Abc_Print( -2, "\t-v : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); +// Abc_Print( -2, "\t-w : toggle printing additional information [default = %s]\n", fVeryVerbose? "yes": "no" ); + Abc_Print( -2, "\t-h : print the command usage\n"); + return 1; +} + /**Function************************************************************* Synopsis [] -- cgit v1.2.3