From e033a62282ef94ddca87a1778d66a4a4270ac1c3 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 16 Sep 2014 12:13:25 -0700 Subject: Code restructuring. --- src/aig/gia/giaBalAig.c | 989 +++++++++++++++++++++++++++++++++++++ src/aig/gia/giaBalLut.c | 982 +++++++++++++++++++++++++++++++++++++ src/aig/gia/giaBalMap.c | 326 +++++++++++++ src/aig/gia/giaBalance.c | 1178 --------------------------------------------- src/aig/gia/giaBalance2.c | 982 ------------------------------------- src/aig/gia/giaScript.c | 369 ++++++++++++++ src/aig/gia/giaSopb.c | 450 ----------------- src/aig/gia/module.make | 7 +- 8 files changed, 2670 insertions(+), 2613 deletions(-) create mode 100644 src/aig/gia/giaBalAig.c create mode 100644 src/aig/gia/giaBalLut.c create mode 100644 src/aig/gia/giaBalMap.c delete mode 100644 src/aig/gia/giaBalance.c delete mode 100644 src/aig/gia/giaBalance2.c create mode 100644 src/aig/gia/giaScript.c delete mode 100644 src/aig/gia/giaSopb.c (limited to 'src/aig/gia') diff --git a/src/aig/gia/giaBalAig.c b/src/aig/gia/giaBalAig.c new file mode 100644 index 00000000..b0d35cb8 --- /dev/null +++ b/src/aig/gia/giaBalAig.c @@ -0,0 +1,989 @@ +/**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 /// +//////////////////////////////////////////////////////////////////////// + +// operation manager +typedef struct Dam_Man_t_ Dam_Man_t; +struct Dam_Man_t_ +{ + Gia_Man_t * pGia; // user's AIG + Vec_Int_t * vNod2Set; // node ID into fanin set + Vec_Int_t * vDiv2Nod; // div ID into root node set + Vec_Int_t * vSetStore; // fanin set storage + Vec_Int_t * vNodStore; // root node set storage + Vec_Flt_t * vCounts; // occur counts + Vec_Int_t * vNodLevR; // node reverse level + Vec_Int_t * vDivLevR; // divisor reverse level + Vec_Int_t * vVisit; // visited MUXes + Vec_Que_t * vQue; // pairs by their weight + Hash_IntMan_t * vHash; // pair hash table + abctime clkStart; // starting the clock + int nLevelMax; // maximum level + int nDivs; // extracted divisor count + int nAnds; // total AND node count + int nGain; // total gain in AND nodes + int nGainX; // gain from XOR nodes +}; + +static inline int Dam_ObjHand( Dam_Man_t * p, int i ) { return i < Vec_IntSize(p->vNod2Set) ? Vec_IntEntry(p->vNod2Set, i) : 0; } +static inline int * Dam_ObjSet( Dam_Man_t * p, int i ) { int h = Dam_ObjHand(p, i); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vSetStore, h); } + +static inline int Dam_DivHand( Dam_Man_t * p, int d ) { return d < Vec_IntSize(p->vDiv2Nod) ? Vec_IntEntry(p->vDiv2Nod, d) : 0; } +static inline int * Dam_DivSet( Dam_Man_t * p, int d ) { int h = Dam_DivHand(p, d); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vNodStore, h); } + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Simplify multi-input AND/XOR.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +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)) ); +} +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 [] + +***********************************************************************/ +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) > 2 || + (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || + Vec_IntSize(p->vSuper) > 100 ) + { + 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) ); +} +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) > 2 || + (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || + Vec_IntSize(p->vSuper) > 100 ) + { + Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) ); + return; + } + Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) ); + Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) ); +} +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 [] + +***********************************************************************/ +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 ); + 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 ); + } +} +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 ) + { + // collect levels + int i, * pArray, * pPerm; + for ( i = 0; i < nLits; i++ ) + Vec_IntPush( vSuper, Gia_ObjLevelId(pNew, Abc_Lit2Var(pLits[i])) ); + // sort by level + Vec_IntGrow( vSuper, 4 * nLits ); + pArray = Vec_IntArray( vSuper ); + pPerm = pArray + nLits; + Abc_QuickSortCostData( pArray, nLits, 1, (word *)(pArray + 2 * nLits), pPerm ); + // collect in the increasing order of level + for ( i = 0; i < nLits; i++ ) + Vec_IntWriteEntry( vSuper, i, pLits[pPerm[i]] ); + Vec_IntShrink( vSuper, nLits ); +// Vec_IntForEachEntry( vSuper, iLit, i ) +// printf( "%d ", Gia_ObjLevel(pNew, Gia_ManObj( pNew, Abc_Lit2Var(iLit) )) ); +// printf( "\n" ); + // perform incremental extraction + while ( Vec_IntSize(vSuper) > 1 ) + Gia_ManCreateGate( pNew, pObj, vSuper ); + } + // consider trivial case + assert( Vec_IntSize(vSuper) == 1 ); + return Vec_IntEntry(vSuper, 0); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +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) ); + 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 ); +} +Gia_Man_t * Gia_ManBalanceInt( Gia_Man_t * p ) +{ + Gia_Man_t * pNew, * pTemp; + Gia_Obj_t * pObj; + int i; + Gia_ManFillValue( p ); + Gia_ManCreateRefs( p ); + // start the new manager + pNew = Gia_ManStart( Gia_ManObjNum(p) ); + 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 internal nodes + Gia_ManHashStart( pNew ); + Gia_ManForEachCo( p, pObj, i ) + { + Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) ); + pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + } + assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) ); + Gia_ManHashStop( pNew ); + Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); + // perform cleanup + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManBalance( Gia_Man_t * p, int fSimpleAnd, int fVerbose ) +{ + Gia_Man_t * pNew, * pNew1, * pNew2; + if ( fVerbose ) Gia_ManPrintStats( p, NULL ); + pNew = fSimpleAnd ? Gia_ManDup( p ) : Gia_ManDupMuxes( p, 2 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + pNew1 = Gia_ManBalanceInt( pNew ); + if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL ); + Gia_ManStop( pNew ); + pNew2 = Gia_ManDupNoMuxes( pNew1 ); + if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL ); + Gia_ManStop( pNew1 ); + return pNew2; +} + + + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Dam_Man_t * Dam_ManAlloc( Gia_Man_t * pGia ) +{ + Dam_Man_t * p; + p = ABC_CALLOC( Dam_Man_t, 1 ); + p->clkStart = Abc_Clock(); + p->vVisit = Vec_IntAlloc( 1000 ); + p->pGia = pGia; + return p; +} +void Dam_ManFree( Dam_Man_t * p ) +{ + Vec_IntFreeP( &p->vVisit ); + Vec_IntFreeP( &p->vDivLevR ); + Vec_IntFreeP( &p->vNodLevR ); + Vec_IntFreeP( &p->vNod2Set ); + Vec_IntFreeP( &p->vDiv2Nod ); + Vec_IntFreeP( &p->vSetStore ); + Vec_IntFreeP( &p->vNodStore ); + Vec_FltFreeP( &p->vCounts ); + Vec_QueFreeP( &p->vQue ); + Hash_IntManStop( p->vHash ); + ABC_FREE( p ); +} + +/**Function************************************************************* + + Synopsis [Collect initial multi-input gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Dam_ManCollectSets_rec( Dam_Man_t * p, int Id ) +{ + Gia_Obj_t * pObj; + int i, iBeg, iEnd, iLit; + if ( Dam_ObjHand(p, Id) || Id == 0 ) + return; + pObj = Gia_ManObj(p->pGia, Id); + if ( Gia_ObjIsCi(pObj) ) + return; + if ( Gia_ObjIsMux(p->pGia, pObj) ) + { + if ( pObj->fMark0 ) + return; + pObj->fMark0 = 1; + Vec_IntPush( p->vVisit, Id ); + Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) ); + Dam_ManCollectSets_rec( p, Gia_ObjFaninId1(pObj, Id) ); + Dam_ManCollectSets_rec( p, Gia_ObjFaninId2(p->pGia, Id) ); + p->nAnds += 3; + return; + } + Gia_ManSuperCollect( p->pGia, pObj ); + Vec_IntWriteEntry( p->vNod2Set, Id, Vec_IntSize(p->vSetStore) ); + Vec_IntPush( p->vSetStore, Vec_IntSize(p->pGia->vSuper) ); + p->nAnds += (1 + 2 * Gia_ObjIsXor(pObj)) * (Vec_IntSize(p->pGia->vSuper) - 1); + // save entries + iBeg = Vec_IntSize( p->vSetStore ); + Vec_IntAppend( p->vSetStore, p->pGia->vSuper ); + iEnd = Vec_IntSize( p->vSetStore ); + // call recursively + Vec_IntForEachEntryStartStop( p->vSetStore, iLit, i, iBeg, iEnd ) + Dam_ManCollectSets_rec( p, Abc_Lit2Var(iLit) ); +} +void Dam_ManCollectSets( Dam_Man_t * p ) +{ + Gia_Obj_t * pObj; + int i; + Gia_ManCreateRefs( p->pGia ); + p->vNod2Set = Vec_IntStart( Gia_ManObjNum(p->pGia) ); + p->vSetStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); + Vec_IntPush( p->vSetStore, -1 ); + Vec_IntClear( p->vVisit ); + Gia_ManForEachCo( p->pGia, pObj, i ) + Dam_ManCollectSets_rec( p, Gia_ObjFaninId0p(p->pGia, pObj) ); + ABC_FREE( p->pGia->pRefs ); + Gia_ManForEachObjVec( p->vVisit, p->pGia, pObj, i ) + pObj->fMark0 = 0; +} + +/**Function************************************************************* + + Synopsis [Create divisors.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Dam_ManDivSlack( Dam_Man_t * p, int iLit0, int iLit1, int LevR ) +{ + int Lev0 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit0))); + int Lev1 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit1))); + int Slack = p->nLevelMax - LevR - Abc_MaxInt(Lev0, Lev1) - 1 - (int)(iLit0 > iLit1); + return Abc_MinInt( Slack, 100 ); +} +void Dam_ManCreateMultiRefs( Dam_Man_t * p, Vec_Int_t ** pvRefsAnd, Vec_Int_t ** pvRefsXor ) +{ + Vec_Int_t * vRefsAnd, * vRefsXor; + Gia_Obj_t * pObj; + int i, k, * pSet; + vRefsAnd = Vec_IntStart( 2 * Gia_ManObjNum(p->pGia) ); + vRefsXor = Vec_IntStart( Gia_ManObjNum(p->pGia) ); + Gia_ManForEachAnd( p->pGia, pObj, i ) + { + if ( !Dam_ObjHand(p, i) ) + continue; + pSet = Dam_ObjSet(p, i); + if ( Gia_ObjIsXor(pObj) ) + for ( k = 1; k <= pSet[0]; k++ ) + { + assert( !Abc_LitIsCompl(pSet[k]) ); + Vec_IntAddToEntry( vRefsXor, Abc_Lit2Var(pSet[k]), 1 ); + } + else if ( Gia_ObjIsAndReal(p->pGia, pObj) ) + for ( k = 1; k <= pSet[0]; k++ ) + Vec_IntAddToEntry( vRefsAnd, pSet[k], 1 ); + else assert( 0 ); + } + *pvRefsAnd = vRefsAnd; + *pvRefsXor = vRefsXor; +} +void Dam_ManCreatePairs( Dam_Man_t * p, int fVerbose ) +{ + Gia_Obj_t * pObj; + Hash_IntMan_t * vHash; + Vec_Int_t * vRefsAnd, * vRefsXor, * vSuper, * vDivs, * vRemap, * vLevRMax; + int i, j, k, Num, FanK, FanJ, nRefs, iNode, iDiv, * pSet; + int nPairsAll = 0, nPairsTried = 0, nPairsUsed = 0, nPairsXor = 0; + int nDivsAll = 0, nDivsUsed = 0, nDivsXor = 0; + Dam_ManCollectSets( p ); + vSuper = p->pGia->vSuper; + vDivs = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); + vHash = Hash_IntManStart( Gia_ManObjNum(p->pGia)/2 ); + vLevRMax = Vec_IntStart( 1000 ); + Dam_ManCreateMultiRefs( p, &vRefsAnd, &vRefsXor ); + Gia_ManForEachAnd( p->pGia, pObj, i ) + { + if ( !Dam_ObjHand(p, i) ) + continue; + pSet = Dam_ObjSet(p, i); + nPairsAll += pSet[0] * (pSet[0] - 1) / 2; + Vec_IntClear(vSuper); + if ( Gia_ObjIsXor(pObj) ) + { + for ( k = 1; k <= pSet[0]; k++ ) + if ( Vec_IntEntry(vRefsXor, Abc_Lit2Var(pSet[k])) > 1 ) + Vec_IntPush( vSuper, pSet[k] ); + } + else if ( Gia_ObjIsAndReal(p->pGia, pObj) ) + { + for ( k = 1; k <= pSet[0]; k++ ) + if ( Vec_IntEntry(vRefsAnd, pSet[k]) > 1 ) + Vec_IntPush( vSuper, pSet[k] ); + } + else assert( 0 ); + if ( Vec_IntSize(vSuper) < 2 ) + continue; + // enumerate pairs + nPairsTried += Vec_IntSize(vSuper) * (Vec_IntSize(vSuper) - 1) / 2; + Vec_IntPush( vDivs, -i ); // remember node + Vec_IntForEachEntry( vSuper, FanK, k ) + Vec_IntForEachEntryStart( vSuper, FanJ, j, k+1 ) + { + if ( (FanK > FanJ) ^ Gia_ObjIsXor(pObj) ) + Num = Hash_Int2ManInsert( vHash, FanJ, FanK, 0 ); + else + Num = Hash_Int2ManInsert( vHash, FanK, FanJ, 0 ); + if ( Hash_Int2ObjInc( vHash, Num ) == 1 ) + { + nDivsUsed++; + nDivsXor += Gia_ObjIsXor(pObj); + } + Vec_IntPush( vDivs, Num ); // remember devisor + // update reverse level + if ( Num >= Vec_IntSize(vLevRMax) ) + Vec_IntFillExtra( vLevRMax, 3 * Vec_IntSize(vLevRMax) / 2, 0 ); + Vec_IntUpdateEntry( vLevRMax, Num, Vec_IntEntry(p->vNodLevR, i) ); + } + } + Vec_IntFree( vRefsAnd ); + Vec_IntFree( vRefsXor ); +// Hash_IntManProfile( vHash ); + // remove entries that appear only once + p->vHash = Hash_IntManStart( 3 * nDivsUsed /2 ); + p->vCounts = Vec_FltAlloc( 2 * nDivsUsed ); Vec_FltPush( p->vCounts, ABC_INFINITY ); + p->vQue = Vec_QueAlloc( Vec_FltCap(p->vCounts) ); + Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) ); + // mapping div to node + p->vDiv2Nod = Vec_IntAlloc( 2 * nDivsUsed ); Vec_IntPush( p->vDiv2Nod, ABC_INFINITY ); + p->vNodStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); Vec_IntPush( p->vNodStore, -1 ); + nDivsAll = Hash_IntManEntryNum(vHash); + vRemap = Vec_IntStartFull( nDivsAll+1 ); + for ( i = 1; i <= nDivsAll; i++ ) + { + nRefs = Hash_IntObjData2(vHash, i); + if ( nRefs < 2 ) + continue; + nPairsUsed += nRefs; + if ( Hash_IntObjData0(vHash, i) > Hash_IntObjData1(vHash, i) ) + nPairsXor += nRefs; + Num = Hash_Int2ManInsert( p->vHash, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), 0 ); + assert( Num == Hash_IntManEntryNum(p->vHash) ); + assert( Num == Vec_FltSize(p->vCounts) ); + Vec_FltPush( p->vCounts, nRefs + 0.005*Dam_ManDivSlack(p, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), Vec_IntEntry(vLevRMax, i)) ); + Vec_QuePush( p->vQue, Num ); + // remember divisors + assert( Num == Vec_IntSize(p->vDiv2Nod) ); + Vec_IntPush( p->vDiv2Nod, Vec_IntSize(p->vNodStore) ); + Vec_IntPush( p->vNodStore, 0 ); + Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 ); + // remember entry + Vec_IntWriteEntry( vRemap, i, Num ); + } + assert( Vec_FltSize(p->vCounts) == Hash_IntManEntryNum(p->vHash)+1 ); + assert( Vec_IntSize(p->vDiv2Nod) == nDivsUsed+1 ); + Hash_IntManStop( vHash ); + Vec_IntFree( vLevRMax ); + // fill in the divisors + iNode = -1; + Vec_IntForEachEntry( vDivs, iDiv, i ) + { + if ( iDiv < 0 ) + { + iNode = -iDiv; + continue; + } + Num = Vec_IntEntry( vRemap, iDiv ); + if ( Num == -1 ) + continue; + pSet = Dam_DivSet( p, Num ); + pSet[++pSet[0]] = iNode; + } + Vec_IntFree( vRemap ); + Vec_IntFree( vDivs ); + // create storage for reverse level of divisor during update + p->vDivLevR = Vec_IntStart( 2 * nDivsUsed ); + // make sure divisors are added correctly +// for ( i = 1; i <= nDivsUsed; i++ ) +// assert( Dam_DivSet(p, i)[0] == Vec_FltEntry(p->vCounts, i)+1 ); + if ( !fVerbose ) + return; + // print stats + printf( "Pairs:" ); + printf( " Total =%9d (%6.2f %%)", nPairsAll, 100.0 * nPairsAll / Abc_MaxInt(nPairsAll, 1) ); + printf( " Tried =%9d (%6.2f %%)", nPairsTried, 100.0 * nPairsTried / Abc_MaxInt(nPairsAll, 1) ); + printf( " Used =%9d (%6.2f %%)", nPairsUsed, 100.0 * nPairsUsed / Abc_MaxInt(nPairsAll, 1) ); + printf( " Xor =%9d (%6.2f %%)", nPairsXor, 100.0 * nPairsXor / Abc_MaxInt(nPairsAll, 1) ); + printf( "\n" ); + printf( "Div: " ); + printf( " Total =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) ); + printf( " Tried =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) ); + printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) ); + printf( " Xor =%9d (%6.2f %%)", nDivsXor, 100.0 * nDivsXor / Abc_MaxInt(nDivsAll, 1) ); + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Derives new AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Dam_ManMultiAig_rec( Dam_Man_t * pMan, Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj ) +{ + int i, * pSet; + if ( ~pObj->Value ) + return; + assert( Gia_ObjIsAnd(pObj) ); + pSet = Dam_ObjSet(pMan, Gia_ObjId(p, pObj)); + if ( pSet == NULL ) + { + Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) ); + Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin1(pObj) ); + if ( Gia_ObjIsMux(p, pObj) ) + { + Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin2(p, pObj) ); + pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) ); + } + else if ( Gia_ObjIsXor(pObj) ) + pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + else + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) ); + return; + } + assert( Gia_ObjIsXor(pObj) || Gia_ObjIsAndReal(p, pObj) ); + // call recursively + for ( i = 1; i <= pSet[0]; i++ ) + { + Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(pSet[i]) ); + Dam_ManMultiAig_rec( pMan, pNew, p, pTemp ); + pSet[i] = Abc_LitNotCond( pTemp->Value, Abc_LitIsCompl(pSet[i]) ); + } + // create balanced gate + pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, pSet + 1, pSet[0] ); +} +Gia_Man_t * Dam_ManMultiAig( Dam_Man_t * pMan ) +{ + Gia_Man_t * p = pMan->pGia; + Gia_Man_t * pNew, * pTemp; + Gia_Obj_t * pObj; + int i; + // start the new manager + pNew = Gia_ManStart( 2*Gia_ManObjNum(p) ); + 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_ManFillValue( p ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachCi( p, pObj, i ) + { + pObj->Value = Gia_ManAppendCi( pNew ); + Vec_IntWriteEntry( pNew->vLevels, Abc_Lit2Var(pObj->Value), Gia_ObjLevel(p, pObj) ); + } + // create internal nodes + Gia_ManHashStart( pNew ); + Gia_ManForEachCo( p, pObj, i ) + { + Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) ); + pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + } + assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) ); + Gia_ManHashStop( pNew ); + Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); + // perform cleanup + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [Updates the data-structure after extracting one divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Dam_PrintDiv( Dam_Man_t * p, int iDiv ) +{ + if ( iDiv == 0 ) + printf( "Final statistics after extracting %6d divisors: ", p->nDivs ); + else + { + char Buffer[100]; + int iData0 = Hash_IntObjData0(p->vHash, iDiv); + int iData1 = Hash_IntObjData1(p->vHash, iDiv); + printf( "Div%5d : ", p->nDivs+1 ); + printf( "D%-8d = ", iDiv ); + sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData0)? '!':' ', Abc_Lit2Var(iData0) ); + printf( "%8s ", Buffer ); + printf( "%c ", (iData0 < iData1) ? '*' : '+' ); + sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData1)? '!':' ', Abc_Lit2Var(iData1) ); + printf( "%8s ", Buffer ); + printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, iDiv) ); + } + printf( "Divs =%8d ", Hash_IntManEntryNum(p->vHash) ); + printf( "Ands =%8d ", p->nAnds - p->nGain ); + Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart ); +} +void Dam_PrintQue( Dam_Man_t * p ) +{ + int i; + printf( "Divisor queue: \n" ); + for ( i = 1; i <= Hash_IntManEntryNum(p->vHash); i++ ) + { + int iLit0 = Hash_IntObjData0(p->vHash, i); + int iLit1 = Hash_IntObjData1(p->vHash, i); + printf( "Div %7d : ", i ); + printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, i) ); + printf( "F = %c%c ", Abc_LitIsCompl(iLit0) ? '!': ' ', 'a' + Abc_Lit2Var(iLit0)-1 ); + printf( "%c ", (Hash_IntObjData0(p->vHash, i) < Hash_IntObjData1(p->vHash, i)) ? '*':'+' ); + printf( "%c%c ", Abc_LitIsCompl(iLit1) ? '!': ' ', 'a' + Abc_Lit2Var(iLit1)-1 ); + printf( "\n" ); + } +} +int Dam_ManUpdateNode( Dam_Man_t * p, int iObj, int iLit0, int iLit1, int iLitNew, Vec_Int_t * vDivs ) +{ + int * pSet = Dam_ObjSet( p, iObj ); + int i, k, c, Num, iLit, iLit2, fPres; + // check if literal can be found + for ( i = 1; i <= pSet[0]; i++ ) + if ( pSet[i] == iLit0 ) + break; + if ( i > pSet[0] ) + return 0; + // check if literal can be found + for ( i = 1; i <= pSet[0]; i++ ) + if ( pSet[i] == iLit1 ) + break; + if ( i > pSet[0] ) + return 0; + // compact literals + Vec_IntPush( vDivs, -iObj ); + for ( k = i = 1; i <= pSet[0]; i++ ) + { + if ( iLit0 == pSet[i] || iLit1 == pSet[i] ) + continue; + pSet[k++] = iLit = pSet[i]; + // reduce weights of the divisors + fPres = 0; + for ( c = 0; c < 2; c++ ) + { + iLit2 = c ? iLit1 : iLit0; + if ( (iLit > iLit2) ^ (iLit0 > iLit1) ) + Num = *Hash_Int2ManLookup( p->vHash, iLit2, iLit ); + else + Num = *Hash_Int2ManLookup( p->vHash, iLit, iLit2 ); + if ( Num > 0 ) + { + Vec_FltAddToEntry( p->vCounts, Num, -1 ); + if ( Vec_QueIsMember(p->vQue, Num) ) + { + Vec_QueUpdate( p->vQue, Num ); + fPres |= (1 << c); + } + } + } + if ( fPres != 3 ) + continue; + if ( (iLit > iLitNew) ^ (iLit0 > iLit1) ) + Num = Hash_Int2ManInsert( p->vHash, iLitNew, iLit, 0 ); + else + Num = Hash_Int2ManInsert( p->vHash, iLit, iLitNew, 0 ); + Hash_Int2ObjInc( p->vHash, Num ); + Vec_IntPush( vDivs, Num ); + // update reverse level + if ( Num >= Vec_IntSize(p->vDivLevR) ) + Vec_IntFillExtra( p->vDivLevR, 3 * Vec_IntSize(p->vDivLevR) / 2, 0 ); + Vec_IntUpdateEntry( p->vDivLevR, Num, Vec_IntEntry(p->vNodLevR, iObj) ); + } + pSet[k] = iLitNew; + pSet[0] = k; + return 1; +} +void Dam_ManUpdate( Dam_Man_t * p, int iDiv ) +{ + Vec_Int_t * vDivs = p->pGia->vSuper; + int iLit0 = Hash_IntObjData0(p->vHash, iDiv); + int iLit1 = Hash_IntObjData1(p->vHash, iDiv); + int i, iLitNew, * pSet, * pNods = Dam_DivSet( p, iDiv ); + int nPresent = 0, nPairsStart, nPairsStop, pPairsNew, nRefs; + int fThisIsXor = (iLit0 > iLit1), iDivTemp, iNode; +// Dam_PrintQue( p ); + if ( fThisIsXor ) + iLitNew = Gia_ManAppendXorReal( p->pGia, iLit0, iLit1 ); + else + iLitNew = Gia_ManAppendAnd( p->pGia, iLit0, iLit1 ); + Gia_ObjSetGateLevel( p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew)) ); +// printf( "%d ", Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew))) ); + // replace entries + assert( pNods[0] >= 2 ); + nPairsStart = Hash_IntManEntryNum(p->vHash) + 1; + Vec_IntClear( vDivs ); + for ( i = 1; i <= pNods[0]; i++ ) + nPresent += Dam_ManUpdateNode( p, pNods[i], iLit0, iLit1, iLitNew, vDivs ); + nPairsStop = Hash_IntManEntryNum(p->vHash) + 1; + // extend arrayvs + pPairsNew = 0; + Vec_FltFillExtra( p->vCounts, nPairsStop, 0 ); + Vec_IntFillExtra( p->vDiv2Nod, nPairsStop, -1 ); + for ( i = nPairsStart; i < nPairsStop; i++ ) + { + nRefs = Hash_IntObjData2(p->vHash, i); + if ( nRefs < 2 ) + continue; + Vec_FltWriteEntry( p->vCounts, i, nRefs + 0.001*Dam_ManDivSlack(p, Hash_IntObjData0(p->vHash, i), Hash_IntObjData1(p->vHash, i), Vec_IntEntry(p->vDivLevR, i)) ); + Vec_QuePush( p->vQue, i ); + // remember divisors + Vec_IntWriteEntry( p->vDiv2Nod, i, Vec_IntSize(p->vNodStore) ); + Vec_IntPush( p->vNodStore, 0 ); + Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 ); + pPairsNew++; + } +// printf( "Added %d new pairs\n", pPairsNew ); + // fill in the divisors + iNode = -1; + Vec_IntForEachEntry( vDivs, iDivTemp, i ) + { + if ( iDivTemp < 0 ) + { + iNode = -iDivTemp; + continue; + } + if ( Vec_IntEntry(p->vDiv2Nod, iDivTemp) == -1 ) + continue; + pSet = Dam_DivSet( p, iDivTemp ); + pSet[++pSet[0]] = iNode; + } + // make sure divisors are added correctly + for ( i = nPairsStart; i < nPairsStop; i++ ) + if ( Vec_IntEntry(p->vDiv2Nod, i) > 0 ) + assert( Dam_DivSet(p, i)[0] == Hash_IntObjData2(p->vHash, i) ); + // update costs + Vec_FltWriteEntry( p->vCounts, iDiv, 0 ); + p->nGain += (1 + 2 * fThisIsXor) * (nPresent - 1); + p->nGainX += 3 * fThisIsXor * (nPresent - 1); + p->nDivs++; +} + +/**Function************************************************************* + + Synopsis [Perform extraction for multi-input AND/XOR.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Dam_ManAreaBalanceInt( Gia_Man_t * pGia, Vec_Int_t * vCiLevels, int nNewNodesMax, int fVerbose, int fVeryVerbose ) +{ + Gia_Man_t * pNew; + Dam_Man_t * p; + int i, iDiv; + p = Dam_ManAlloc( pGia ); + p->nLevelMax = Gia_ManSetLevels( p->pGia, vCiLevels ); + p->vNodLevR = Gia_ManReverseLevel( p->pGia ); + Vec_IntFillExtra( p->pGia->vLevels, 3*Gia_ManObjNum(p->pGia)/2, 0 ); + Dam_ManCreatePairs( p, fVerbose ); + for ( i = 0; i < nNewNodesMax && Vec_QueTopPriority(p->vQue) >= 2; i++ ) + { + iDiv = Vec_QuePop(p->vQue); + if ( fVeryVerbose ) + Dam_PrintDiv( p, iDiv ); + Dam_ManUpdate( p, iDiv ); + } + if ( fVeryVerbose ) + Dam_PrintDiv( p, 0 ); + pNew = Dam_ManMultiAig( p ); + if ( fVerbose ) + { + int nDivsAll = Hash_IntManEntryNum(p->vHash); + int nDivsUsed = p->nDivs; + printf( "Div: " ); + printf( " Total =%9d (%6.2f %%) ", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) ); + printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) ); + printf( " Gain =%6d (%6.2f %%)", p->nGain, 100.0 * p->nGain / Abc_MaxInt(p->nAnds, 1) ); + printf( " GainX = %d ", p->nGainX ); + Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart ); + } + Dam_ManFree( p ); + return pNew; +} +Gia_Man_t * Gia_ManAreaBalance( Gia_Man_t * p, int fSimpleAnd, int nNewNodesMax, int fVerbose, int fVeryVerbose ) +{ + Gia_Man_t * pNew0, * pNew, * pNew1, * pNew2; + Vec_Int_t * vCiLevels; + // determine CI levels + if ( p->pManTime && p->vLevels == NULL ) + Gia_ManLevelWithBoxes( p ); + vCiLevels = Gia_ManGetCiLevels( p ); + // get the starting manager + pNew0 = Gia_ManHasMapping(p) ? (Gia_Man_t *)Dsm_ManDeriveGia(p, 0) : p; + if ( fVerbose ) Gia_ManPrintStats( pNew0, NULL ); + // derive internal manager + pNew = fSimpleAnd ? Gia_ManDup( pNew0 ) : Gia_ManDupMuxes( pNew0, 2 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + if ( pNew0 != p ) Gia_ManStop( pNew0 ); + // perform the operation + pNew1 = Dam_ManAreaBalanceInt( pNew, vCiLevels, nNewNodesMax, fVerbose, fVeryVerbose ); + if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL ); + Gia_ManStop( pNew ); + Vec_IntFreeP( &vCiLevels ); + // derive the final result + pNew2 = Gia_ManDupNoMuxes( pNew1 ); + if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL ); + Gia_ManStop( pNew1 ); + // normalize if needed + if ( !Gia_ManIsNormalized(pNew2) ) + { + pNew2 = Gia_ManDupNormalize( pNew1 = pNew2 ); + Gia_ManStop( pNew1 ); + } + Gia_ManTransferTiming( pNew2, p ); + return pNew2; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/giaBalLut.c b/src/aig/gia/giaBalLut.c new file mode 100644 index 00000000..73d2a6fb --- /dev/null +++ b/src/aig/gia/giaBalLut.c @@ -0,0 +1,982 @@ +/**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_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/giaBalMap.c b/src/aig/gia/giaBalMap.c new file mode 100644 index 00000000..b285daea --- /dev/null +++ b/src/aig/gia/giaBalMap.c @@ -0,0 +1,326 @@ +/**CFile**************************************************************** + + FileName [giaSopb.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [SOP balancing for a window.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: giaSopb.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManHighlight_rec( Gia_Man_t * p, int iObj ) +{ + Gia_Obj_t * pObj; + if ( Gia_ObjIsTravIdCurrentId(p, iObj) ) + return; + Gia_ObjSetTravIdCurrentId(p, iObj); + pObj = Gia_ManObj( p, iObj ); + if ( Gia_ObjIsAnd(pObj) ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId0(pObj, iObj) ); + if ( Gia_ObjIsAnd(pObj) ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId1(pObj, iObj) ); +} +void Gia_ManPrepareWin( Gia_Man_t * p, Vec_Int_t * vOuts, Vec_Int_t ** pvPis, Vec_Int_t ** pvPos, Vec_Int_t ** pvAnds, int fPoOnly ) +{ + Gia_Obj_t * pObj; + int i; + // mark the section + Gia_ManIncrementTravId( p ); + Gia_ManForEachCoVec( vOuts, p, pObj, i ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId0p(p, pObj) ); + // mark fanins of the outside area + Gia_ManCleanMark0( p ); + if ( fPoOnly ) + { + Gia_ManForEachCoVec( vOuts, p, pObj, i ) + Gia_ObjFanin0(pObj)->fMark0 = 1; + } + else + { + Gia_ManForEachObj1( p, pObj, i ) + { + if ( Gia_ObjIsCi(pObj) ) + continue; + if ( Gia_ObjIsAnd(pObj) && !Gia_ObjIsTravIdCurrentId(p, i) ) + continue; + Gia_ObjFanin0(pObj)->fMark0 = 1; + if ( Gia_ObjIsAnd(pObj) ) + Gia_ObjFanin1(pObj)->fMark0 = 1; + } + } + // collect pointed nodes + *pvPis = Vec_IntAlloc( 1000 ); + *pvPos = Vec_IntAlloc( 1000 ); + *pvAnds = Vec_IntAlloc( 1000 ); + Gia_ManForEachObj1( p, pObj, i ) + { + if ( !Gia_ObjIsTravIdCurrentId(p, i) ) + continue; + if ( Gia_ObjIsCi(pObj) ) + Vec_IntPush( *pvPis, i ); + else if ( pObj->fMark0 ) + Vec_IntPush( *pvPos, i ); + if ( Gia_ObjIsAnd(pObj) ) + Vec_IntPush( *pvAnds, i ); + } + Gia_ManCleanMark0( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManExtractWin( Gia_Man_t * p, Vec_Int_t * vOuts, int fPoOnly ) +{ + Vec_Int_t * vPis, * vPos, * vAnds; + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i; + Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, fPoOnly ); + // create AIG + pNew = Gia_ManStart( Vec_IntSize(vPis) + Vec_IntSize(vPos) + Vec_IntSize(vAnds) + 1 ); + pNew->pName = Abc_UtilStrsav( p->pName ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachObjVec( vPis, p, pObj, i ) + pObj->Value = Gia_ManAppendCi( pNew ); + Gia_ManForEachObjVec( vAnds, p, pObj, i ) + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachObjVec( vPos, p, pObj, i ) + Gia_ManAppendCo( pNew, pObj->Value ); + Vec_IntFree( vPis ); + Vec_IntFree( vPos ); + Vec_IntFree( vAnds ); + return pNew; +} +Gia_Man_t * Gia_ManInsertWin( Gia_Man_t * p, Vec_Int_t * vOuts, Gia_Man_t * pWin ) +{ + Vec_Int_t * vPos, * vPis, * vAnds; + Gia_Man_t * pNew, * pTemp; + Gia_Obj_t * pObj; + int i; + Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, 0 ); + // create AIG + pNew = Gia_ManStart( Gia_ManObjNum(p) - Vec_IntSize(vAnds) + Gia_ManAndNum(pWin) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + // inputs + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachCi( p, pObj, i ) + pObj->Value = Gia_ManAppendCi( pNew ); + Gia_ManConst0(pWin)->Value = 0; + Gia_ManForEachCi( pWin, pObj, i ) + pObj->Value = Gia_ManObj(p, Vec_IntEntry(vPis, i))->Value; + // internal nodes + Gia_ManHashAlloc( pNew ); + Gia_ManForEachAnd( pWin, pObj, i ) + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( pWin, pObj, i ) + Gia_ManObj( p, Vec_IntEntry(vPos, i) )->Value = Gia_ObjFanin0Copy(pObj); + Gia_ManForEachAnd( p, pObj, i ) + if ( !Gia_ObjIsTravIdCurrentId(p, i) ) + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( p, pObj, i ) + Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + Gia_ManHashStop( pNew ); + // cleanup + Vec_IntFree( vPis ); + Vec_IntFree( vPos ); + Vec_IntFree( vAnds ); + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManFindLatest( Gia_Man_t * p, int LevelMax, int nTimeWindow ) +{ + Gia_Obj_t * pObj; + Vec_Int_t * vOuts; + vOuts = Vec_IntAlloc( 1000 ); + if ( Gia_ManHasMapping(p) ) + { + int i, k, iFan, nLevels = 0; + int * pLevels = ABC_CALLOC( int, Gia_ManObjNum(p) ); + Gia_ManForEachLut( p, i ) + { + Gia_LutForEachFanin( p, i, iFan, k ) + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[iFan] ); + pLevels[i]++; + nLevels = Abc_MaxInt( nLevels, pLevels[i] ); + } + if ( nTimeWindow ) + LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels); + if ( nLevels < LevelMax ) + printf( "The maximum mapped level (%d) is less than the target level (%d).\n", nLevels, LevelMax ); + Gia_ManForEachCo( p, pObj, i ) + if ( pLevels[Gia_ObjFaninId0p(p, pObj)] >= LevelMax ) + Vec_IntPush( vOuts, i ); + ABC_FREE( pLevels ); + } + else + { + int i, nLevels = Gia_ManLevelNum( p ); + if ( nTimeWindow ) + LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels); + if ( nLevels < LevelMax ) + printf( "The maximum AIG level (%d) is less than the target level (%d).\n", nLevels, LevelMax ); + Gia_ManForEachCo( p, pObj, i ) + if ( Gia_ObjLevel(p, pObj) >= LevelMax ) + Vec_IntPush( vOuts, i ); + } + return vOuts; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManExtractWindow( Gia_Man_t * p, int LevelMax, int nTimeWindow, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pWin; + assert( !LevelMax != !nTimeWindow ); + vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); + if ( fVerbose ) + printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts, 1 ); + Vec_IntFree( vOuts ); + return pWin; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManPerformSopBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pNew, * pWin, * pWinNew; + assert( !LevelMax != !nTimeWindow ); + vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); + if ( fVerbose ) + printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts, 0 ); + pWinNew = Gia_ManPerformSopBalance( pWin, nCutNum, nRelaxRatio, fVerbose ); + Gia_ManStop( pWin ); + pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); + Gia_ManStop( pWinNew ); + Vec_IntFree( vOuts ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManPerformDsdBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pNew, * pWin, * pWinNew; + assert( !LevelMax != !nTimeWindow ); + vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); + if ( fVerbose ) + printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts, 0 ); + pWinNew = Gia_ManPerformDsdBalance( pWin, nLutSize, nCutNum, nRelaxRatio, fVerbose ); + Gia_ManStop( pWin ); + pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); + Gia_ManStop( pWinNew ); + Vec_IntFree( vOuts ); + return pNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/giaBalance.c b/src/aig/gia/giaBalance.c deleted file mode 100644 index 2ea0f5d0..00000000 --- a/src/aig/gia/giaBalance.c +++ /dev/null @@ -1,1178 +0,0 @@ -/**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 /// -//////////////////////////////////////////////////////////////////////// - -// operation manager -typedef struct Dam_Man_t_ Dam_Man_t; -struct Dam_Man_t_ -{ - Gia_Man_t * pGia; // user's AIG - Vec_Int_t * vNod2Set; // node ID into fanin set - Vec_Int_t * vDiv2Nod; // div ID into root node set - Vec_Int_t * vSetStore; // fanin set storage - Vec_Int_t * vNodStore; // root node set storage - Vec_Flt_t * vCounts; // occur counts - Vec_Int_t * vNodLevR; // node reverse level - Vec_Int_t * vDivLevR; // divisor reverse level - Vec_Int_t * vVisit; // visited MUXes - Vec_Que_t * vQue; // pairs by their weight - Hash_IntMan_t * vHash; // pair hash table - abctime clkStart; // starting the clock - int nLevelMax; // maximum level - int nDivs; // extracted divisor count - int nAnds; // total AND node count - int nGain; // total gain in AND nodes - int nGainX; // gain from XOR nodes -}; - -static inline int Dam_ObjHand( Dam_Man_t * p, int i ) { return i < Vec_IntSize(p->vNod2Set) ? Vec_IntEntry(p->vNod2Set, i) : 0; } -static inline int * Dam_ObjSet( Dam_Man_t * p, int i ) { int h = Dam_ObjHand(p, i); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vSetStore, h); } - -static inline int Dam_DivHand( Dam_Man_t * p, int d ) { return d < Vec_IntSize(p->vDiv2Nod) ? Vec_IntEntry(p->vDiv2Nod, d) : 0; } -static inline int * Dam_DivSet( Dam_Man_t * p, int d ) { int h = Dam_DivHand(p, d); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vNodStore, h); } - - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Simplify multi-input AND/XOR.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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)) ); -} -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 [] - -***********************************************************************/ -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) > 2 || - (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || - Vec_IntSize(p->vSuper) > 100 ) - { - 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) ); -} -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) > 2 || - (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || - Vec_IntSize(p->vSuper) > 100 ) - { - Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) ); - return; - } - Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) ); - Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) ); -} -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 [] - -***********************************************************************/ -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 ); - 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 ); - } -} -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 ) - { - // collect levels - int i, * pArray, * pPerm; - for ( i = 0; i < nLits; i++ ) - Vec_IntPush( vSuper, Gia_ObjLevelId(pNew, Abc_Lit2Var(pLits[i])) ); - // sort by level - Vec_IntGrow( vSuper, 4 * nLits ); - pArray = Vec_IntArray( vSuper ); - pPerm = pArray + nLits; - Abc_QuickSortCostData( pArray, nLits, 1, (word *)(pArray + 2 * nLits), pPerm ); - // collect in the increasing order of level - for ( i = 0; i < nLits; i++ ) - Vec_IntWriteEntry( vSuper, i, pLits[pPerm[i]] ); - Vec_IntShrink( vSuper, nLits ); -// Vec_IntForEachEntry( vSuper, iLit, i ) -// printf( "%d ", Gia_ObjLevel(pNew, Gia_ManObj( pNew, Abc_Lit2Var(iLit) )) ); -// printf( "\n" ); - // perform incremental extraction - while ( Vec_IntSize(vSuper) > 1 ) - Gia_ManCreateGate( pNew, pObj, vSuper ); - } - // consider trivial case - assert( Vec_IntSize(vSuper) == 1 ); - return Vec_IntEntry(vSuper, 0); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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) ); - 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 ); -} -Gia_Man_t * Gia_ManBalanceInt( Gia_Man_t * p ) -{ - Gia_Man_t * pNew, * pTemp; - Gia_Obj_t * pObj; - int i; - Gia_ManFillValue( p ); - Gia_ManCreateRefs( p ); - // start the new manager - pNew = Gia_ManStart( Gia_ManObjNum(p) ); - 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 internal nodes - Gia_ManHashStart( pNew ); - Gia_ManForEachCo( p, pObj, i ) - { - Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) ); - pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); - } - assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) ); - Gia_ManHashStop( pNew ); - Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); - // perform cleanup - pNew = Gia_ManCleanup( pTemp = pNew ); - Gia_ManStop( pTemp ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Gia_ManBalance( Gia_Man_t * p, int fSimpleAnd, int fVerbose ) -{ - Gia_Man_t * pNew, * pNew1, * pNew2; - if ( fVerbose ) Gia_ManPrintStats( p, NULL ); - pNew = fSimpleAnd ? Gia_ManDup( p ) : Gia_ManDupMuxes( p, 2 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - pNew1 = Gia_ManBalanceInt( pNew ); - if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL ); - Gia_ManStop( pNew ); - pNew2 = Gia_ManDupNoMuxes( pNew1 ); - if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL ); - Gia_ManStop( pNew1 ); - return pNew2; -} - - - - - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Dam_Man_t * Dam_ManAlloc( Gia_Man_t * pGia ) -{ - Dam_Man_t * p; - p = ABC_CALLOC( Dam_Man_t, 1 ); - p->clkStart = Abc_Clock(); - p->vVisit = Vec_IntAlloc( 1000 ); - p->pGia = pGia; - return p; -} -void Dam_ManFree( Dam_Man_t * p ) -{ - Vec_IntFreeP( &p->vVisit ); - Vec_IntFreeP( &p->vDivLevR ); - Vec_IntFreeP( &p->vNodLevR ); - Vec_IntFreeP( &p->vNod2Set ); - Vec_IntFreeP( &p->vDiv2Nod ); - Vec_IntFreeP( &p->vSetStore ); - Vec_IntFreeP( &p->vNodStore ); - Vec_FltFreeP( &p->vCounts ); - Vec_QueFreeP( &p->vQue ); - Hash_IntManStop( p->vHash ); - ABC_FREE( p ); -} - -/**Function************************************************************* - - Synopsis [Collect initial multi-input gates.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Dam_ManCollectSets_rec( Dam_Man_t * p, int Id ) -{ - Gia_Obj_t * pObj; - int i, iBeg, iEnd, iLit; - if ( Dam_ObjHand(p, Id) || Id == 0 ) - return; - pObj = Gia_ManObj(p->pGia, Id); - if ( Gia_ObjIsCi(pObj) ) - return; - if ( Gia_ObjIsMux(p->pGia, pObj) ) - { - if ( pObj->fMark0 ) - return; - pObj->fMark0 = 1; - Vec_IntPush( p->vVisit, Id ); - Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) ); - Dam_ManCollectSets_rec( p, Gia_ObjFaninId1(pObj, Id) ); - Dam_ManCollectSets_rec( p, Gia_ObjFaninId2(p->pGia, Id) ); - p->nAnds += 3; - return; - } - Gia_ManSuperCollect( p->pGia, pObj ); - Vec_IntWriteEntry( p->vNod2Set, Id, Vec_IntSize(p->vSetStore) ); - Vec_IntPush( p->vSetStore, Vec_IntSize(p->pGia->vSuper) ); - p->nAnds += (1 + 2 * Gia_ObjIsXor(pObj)) * (Vec_IntSize(p->pGia->vSuper) - 1); - // save entries - iBeg = Vec_IntSize( p->vSetStore ); - Vec_IntAppend( p->vSetStore, p->pGia->vSuper ); - iEnd = Vec_IntSize( p->vSetStore ); - // call recursively - Vec_IntForEachEntryStartStop( p->vSetStore, iLit, i, iBeg, iEnd ) - Dam_ManCollectSets_rec( p, Abc_Lit2Var(iLit) ); -} -void Dam_ManCollectSets( Dam_Man_t * p ) -{ - Gia_Obj_t * pObj; - int i; - Gia_ManCreateRefs( p->pGia ); - p->vNod2Set = Vec_IntStart( Gia_ManObjNum(p->pGia) ); - p->vSetStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); - Vec_IntPush( p->vSetStore, -1 ); - Vec_IntClear( p->vVisit ); - Gia_ManForEachCo( p->pGia, pObj, i ) - Dam_ManCollectSets_rec( p, Gia_ObjFaninId0p(p->pGia, pObj) ); - ABC_FREE( p->pGia->pRefs ); - Gia_ManForEachObjVec( p->vVisit, p->pGia, pObj, i ) - pObj->fMark0 = 0; -} - -/**Function************************************************************* - - Synopsis [Create divisors.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Dam_ManDivSlack( Dam_Man_t * p, int iLit0, int iLit1, int LevR ) -{ - int Lev0 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit0))); - int Lev1 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit1))); - int Slack = p->nLevelMax - LevR - Abc_MaxInt(Lev0, Lev1) - 1 - (int)(iLit0 > iLit1); - return Abc_MinInt( Slack, 100 ); -} -void Dam_ManCreateMultiRefs( Dam_Man_t * p, Vec_Int_t ** pvRefsAnd, Vec_Int_t ** pvRefsXor ) -{ - Vec_Int_t * vRefsAnd, * vRefsXor; - Gia_Obj_t * pObj; - int i, k, * pSet; - vRefsAnd = Vec_IntStart( 2 * Gia_ManObjNum(p->pGia) ); - vRefsXor = Vec_IntStart( Gia_ManObjNum(p->pGia) ); - Gia_ManForEachAnd( p->pGia, pObj, i ) - { - if ( !Dam_ObjHand(p, i) ) - continue; - pSet = Dam_ObjSet(p, i); - if ( Gia_ObjIsXor(pObj) ) - for ( k = 1; k <= pSet[0]; k++ ) - { - assert( !Abc_LitIsCompl(pSet[k]) ); - Vec_IntAddToEntry( vRefsXor, Abc_Lit2Var(pSet[k]), 1 ); - } - else if ( Gia_ObjIsAndReal(p->pGia, pObj) ) - for ( k = 1; k <= pSet[0]; k++ ) - Vec_IntAddToEntry( vRefsAnd, pSet[k], 1 ); - else assert( 0 ); - } - *pvRefsAnd = vRefsAnd; - *pvRefsXor = vRefsXor; -} -void Dam_ManCreatePairs( Dam_Man_t * p, int fVerbose ) -{ - Gia_Obj_t * pObj; - Hash_IntMan_t * vHash; - Vec_Int_t * vRefsAnd, * vRefsXor, * vSuper, * vDivs, * vRemap, * vLevRMax; - int i, j, k, Num, FanK, FanJ, nRefs, iNode, iDiv, * pSet; - int nPairsAll = 0, nPairsTried = 0, nPairsUsed = 0, nPairsXor = 0; - int nDivsAll = 0, nDivsUsed = 0, nDivsXor = 0; - Dam_ManCollectSets( p ); - vSuper = p->pGia->vSuper; - vDivs = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); - vHash = Hash_IntManStart( Gia_ManObjNum(p->pGia)/2 ); - vLevRMax = Vec_IntStart( 1000 ); - Dam_ManCreateMultiRefs( p, &vRefsAnd, &vRefsXor ); - Gia_ManForEachAnd( p->pGia, pObj, i ) - { - if ( !Dam_ObjHand(p, i) ) - continue; - pSet = Dam_ObjSet(p, i); - nPairsAll += pSet[0] * (pSet[0] - 1) / 2; - Vec_IntClear(vSuper); - if ( Gia_ObjIsXor(pObj) ) - { - for ( k = 1; k <= pSet[0]; k++ ) - if ( Vec_IntEntry(vRefsXor, Abc_Lit2Var(pSet[k])) > 1 ) - Vec_IntPush( vSuper, pSet[k] ); - } - else if ( Gia_ObjIsAndReal(p->pGia, pObj) ) - { - for ( k = 1; k <= pSet[0]; k++ ) - if ( Vec_IntEntry(vRefsAnd, pSet[k]) > 1 ) - Vec_IntPush( vSuper, pSet[k] ); - } - else assert( 0 ); - if ( Vec_IntSize(vSuper) < 2 ) - continue; - // enumerate pairs - nPairsTried += Vec_IntSize(vSuper) * (Vec_IntSize(vSuper) - 1) / 2; - Vec_IntPush( vDivs, -i ); // remember node - Vec_IntForEachEntry( vSuper, FanK, k ) - Vec_IntForEachEntryStart( vSuper, FanJ, j, k+1 ) - { - if ( (FanK > FanJ) ^ Gia_ObjIsXor(pObj) ) - Num = Hash_Int2ManInsert( vHash, FanJ, FanK, 0 ); - else - Num = Hash_Int2ManInsert( vHash, FanK, FanJ, 0 ); - if ( Hash_Int2ObjInc( vHash, Num ) == 1 ) - { - nDivsUsed++; - nDivsXor += Gia_ObjIsXor(pObj); - } - Vec_IntPush( vDivs, Num ); // remember devisor - // update reverse level - if ( Num >= Vec_IntSize(vLevRMax) ) - Vec_IntFillExtra( vLevRMax, 3 * Vec_IntSize(vLevRMax) / 2, 0 ); - Vec_IntUpdateEntry( vLevRMax, Num, Vec_IntEntry(p->vNodLevR, i) ); - } - } - Vec_IntFree( vRefsAnd ); - Vec_IntFree( vRefsXor ); -// Hash_IntManProfile( vHash ); - // remove entries that appear only once - p->vHash = Hash_IntManStart( 3 * nDivsUsed /2 ); - p->vCounts = Vec_FltAlloc( 2 * nDivsUsed ); Vec_FltPush( p->vCounts, ABC_INFINITY ); - p->vQue = Vec_QueAlloc( Vec_FltCap(p->vCounts) ); - Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) ); - // mapping div to node - p->vDiv2Nod = Vec_IntAlloc( 2 * nDivsUsed ); Vec_IntPush( p->vDiv2Nod, ABC_INFINITY ); - p->vNodStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); Vec_IntPush( p->vNodStore, -1 ); - nDivsAll = Hash_IntManEntryNum(vHash); - vRemap = Vec_IntStartFull( nDivsAll+1 ); - for ( i = 1; i <= nDivsAll; i++ ) - { - nRefs = Hash_IntObjData2(vHash, i); - if ( nRefs < 2 ) - continue; - nPairsUsed += nRefs; - if ( Hash_IntObjData0(vHash, i) > Hash_IntObjData1(vHash, i) ) - nPairsXor += nRefs; - Num = Hash_Int2ManInsert( p->vHash, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), 0 ); - assert( Num == Hash_IntManEntryNum(p->vHash) ); - assert( Num == Vec_FltSize(p->vCounts) ); - Vec_FltPush( p->vCounts, nRefs + 0.005*Dam_ManDivSlack(p, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), Vec_IntEntry(vLevRMax, i)) ); - Vec_QuePush( p->vQue, Num ); - // remember divisors - assert( Num == Vec_IntSize(p->vDiv2Nod) ); - Vec_IntPush( p->vDiv2Nod, Vec_IntSize(p->vNodStore) ); - Vec_IntPush( p->vNodStore, 0 ); - Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 ); - // remember entry - Vec_IntWriteEntry( vRemap, i, Num ); - } - assert( Vec_FltSize(p->vCounts) == Hash_IntManEntryNum(p->vHash)+1 ); - assert( Vec_IntSize(p->vDiv2Nod) == nDivsUsed+1 ); - Hash_IntManStop( vHash ); - Vec_IntFree( vLevRMax ); - // fill in the divisors - iNode = -1; - Vec_IntForEachEntry( vDivs, iDiv, i ) - { - if ( iDiv < 0 ) - { - iNode = -iDiv; - continue; - } - Num = Vec_IntEntry( vRemap, iDiv ); - if ( Num == -1 ) - continue; - pSet = Dam_DivSet( p, Num ); - pSet[++pSet[0]] = iNode; - } - Vec_IntFree( vRemap ); - Vec_IntFree( vDivs ); - // create storage for reverse level of divisor during update - p->vDivLevR = Vec_IntStart( 2 * nDivsUsed ); - // make sure divisors are added correctly -// for ( i = 1; i <= nDivsUsed; i++ ) -// assert( Dam_DivSet(p, i)[0] == Vec_FltEntry(p->vCounts, i)+1 ); - if ( !fVerbose ) - return; - // print stats - printf( "Pairs:" ); - printf( " Total =%9d (%6.2f %%)", nPairsAll, 100.0 * nPairsAll / Abc_MaxInt(nPairsAll, 1) ); - printf( " Tried =%9d (%6.2f %%)", nPairsTried, 100.0 * nPairsTried / Abc_MaxInt(nPairsAll, 1) ); - printf( " Used =%9d (%6.2f %%)", nPairsUsed, 100.0 * nPairsUsed / Abc_MaxInt(nPairsAll, 1) ); - printf( " Xor =%9d (%6.2f %%)", nPairsXor, 100.0 * nPairsXor / Abc_MaxInt(nPairsAll, 1) ); - printf( "\n" ); - printf( "Div: " ); - printf( " Total =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) ); - printf( " Tried =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) ); - printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) ); - printf( " Xor =%9d (%6.2f %%)", nDivsXor, 100.0 * nDivsXor / Abc_MaxInt(nDivsAll, 1) ); - printf( "\n" ); -} - -/**Function************************************************************* - - Synopsis [Derives new AIG.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Dam_ManMultiAig_rec( Dam_Man_t * pMan, Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj ) -{ - int i, * pSet; - if ( ~pObj->Value ) - return; - assert( Gia_ObjIsAnd(pObj) ); - pSet = Dam_ObjSet(pMan, Gia_ObjId(p, pObj)); - if ( pSet == NULL ) - { - Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) ); - Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin1(pObj) ); - if ( Gia_ObjIsMux(p, pObj) ) - { - Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin2(p, pObj) ); - pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) ); - } - else if ( Gia_ObjIsXor(pObj) ) - pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); - else - pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); - Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) ); - return; - } - assert( Gia_ObjIsXor(pObj) || Gia_ObjIsAndReal(p, pObj) ); - // call recursively - for ( i = 1; i <= pSet[0]; i++ ) - { - Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(pSet[i]) ); - Dam_ManMultiAig_rec( pMan, pNew, p, pTemp ); - pSet[i] = Abc_LitNotCond( pTemp->Value, Abc_LitIsCompl(pSet[i]) ); - } - // create balanced gate - pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, pSet + 1, pSet[0] ); -} -Gia_Man_t * Dam_ManMultiAig( Dam_Man_t * pMan ) -{ - Gia_Man_t * p = pMan->pGia; - Gia_Man_t * pNew, * pTemp; - Gia_Obj_t * pObj; - int i; - // start the new manager - pNew = Gia_ManStart( 2*Gia_ManObjNum(p) ); - 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_ManFillValue( p ); - Gia_ManConst0(p)->Value = 0; - Gia_ManForEachCi( p, pObj, i ) - { - pObj->Value = Gia_ManAppendCi( pNew ); - Vec_IntWriteEntry( pNew->vLevels, Abc_Lit2Var(pObj->Value), Gia_ObjLevel(p, pObj) ); - } - // create internal nodes - Gia_ManHashStart( pNew ); - Gia_ManForEachCo( p, pObj, i ) - { - Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) ); - pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); - } - assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) ); - Gia_ManHashStop( pNew ); - Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); - // perform cleanup - pNew = Gia_ManCleanup( pTemp = pNew ); - Gia_ManStop( pTemp ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [Updates the data-structure after extracting one divisor.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Dam_PrintDiv( Dam_Man_t * p, int iDiv ) -{ - if ( iDiv == 0 ) - printf( "Final statistics after extracting %6d divisors: ", p->nDivs ); - else - { - char Buffer[100]; - int iData0 = Hash_IntObjData0(p->vHash, iDiv); - int iData1 = Hash_IntObjData1(p->vHash, iDiv); - printf( "Div%5d : ", p->nDivs+1 ); - printf( "D%-8d = ", iDiv ); - sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData0)? '!':' ', Abc_Lit2Var(iData0) ); - printf( "%8s ", Buffer ); - printf( "%c ", (iData0 < iData1) ? '*' : '+' ); - sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData1)? '!':' ', Abc_Lit2Var(iData1) ); - printf( "%8s ", Buffer ); - printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, iDiv) ); - } - printf( "Divs =%8d ", Hash_IntManEntryNum(p->vHash) ); - printf( "Ands =%8d ", p->nAnds - p->nGain ); - Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart ); -} -void Dam_PrintQue( Dam_Man_t * p ) -{ - int i; - printf( "Divisor queue: \n" ); - for ( i = 1; i <= Hash_IntManEntryNum(p->vHash); i++ ) - { - int iLit0 = Hash_IntObjData0(p->vHash, i); - int iLit1 = Hash_IntObjData1(p->vHash, i); - printf( "Div %7d : ", i ); - printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, i) ); - printf( "F = %c%c ", Abc_LitIsCompl(iLit0) ? '!': ' ', 'a' + Abc_Lit2Var(iLit0)-1 ); - printf( "%c ", (Hash_IntObjData0(p->vHash, i) < Hash_IntObjData1(p->vHash, i)) ? '*':'+' ); - printf( "%c%c ", Abc_LitIsCompl(iLit1) ? '!': ' ', 'a' + Abc_Lit2Var(iLit1)-1 ); - printf( "\n" ); - } -} -int Dam_ManUpdateNode( Dam_Man_t * p, int iObj, int iLit0, int iLit1, int iLitNew, Vec_Int_t * vDivs ) -{ - int * pSet = Dam_ObjSet( p, iObj ); - int i, k, c, Num, iLit, iLit2, fPres; - // check if literal can be found - for ( i = 1; i <= pSet[0]; i++ ) - if ( pSet[i] == iLit0 ) - break; - if ( i > pSet[0] ) - return 0; - // check if literal can be found - for ( i = 1; i <= pSet[0]; i++ ) - if ( pSet[i] == iLit1 ) - break; - if ( i > pSet[0] ) - return 0; - // compact literals - Vec_IntPush( vDivs, -iObj ); - for ( k = i = 1; i <= pSet[0]; i++ ) - { - if ( iLit0 == pSet[i] || iLit1 == pSet[i] ) - continue; - pSet[k++] = iLit = pSet[i]; - // reduce weights of the divisors - fPres = 0; - for ( c = 0; c < 2; c++ ) - { - iLit2 = c ? iLit1 : iLit0; - if ( (iLit > iLit2) ^ (iLit0 > iLit1) ) - Num = *Hash_Int2ManLookup( p->vHash, iLit2, iLit ); - else - Num = *Hash_Int2ManLookup( p->vHash, iLit, iLit2 ); - if ( Num > 0 ) - { - Vec_FltAddToEntry( p->vCounts, Num, -1 ); - if ( Vec_QueIsMember(p->vQue, Num) ) - { - Vec_QueUpdate( p->vQue, Num ); - fPres |= (1 << c); - } - } - } - if ( fPres != 3 ) - continue; - if ( (iLit > iLitNew) ^ (iLit0 > iLit1) ) - Num = Hash_Int2ManInsert( p->vHash, iLitNew, iLit, 0 ); - else - Num = Hash_Int2ManInsert( p->vHash, iLit, iLitNew, 0 ); - Hash_Int2ObjInc( p->vHash, Num ); - Vec_IntPush( vDivs, Num ); - // update reverse level - if ( Num >= Vec_IntSize(p->vDivLevR) ) - Vec_IntFillExtra( p->vDivLevR, 3 * Vec_IntSize(p->vDivLevR) / 2, 0 ); - Vec_IntUpdateEntry( p->vDivLevR, Num, Vec_IntEntry(p->vNodLevR, iObj) ); - } - pSet[k] = iLitNew; - pSet[0] = k; - return 1; -} -void Dam_ManUpdate( Dam_Man_t * p, int iDiv ) -{ - Vec_Int_t * vDivs = p->pGia->vSuper; - int iLit0 = Hash_IntObjData0(p->vHash, iDiv); - int iLit1 = Hash_IntObjData1(p->vHash, iDiv); - int i, iLitNew, * pSet, * pNods = Dam_DivSet( p, iDiv ); - int nPresent = 0, nPairsStart, nPairsStop, pPairsNew, nRefs; - int fThisIsXor = (iLit0 > iLit1), iDivTemp, iNode; -// Dam_PrintQue( p ); - if ( fThisIsXor ) - iLitNew = Gia_ManAppendXorReal( p->pGia, iLit0, iLit1 ); - else - iLitNew = Gia_ManAppendAnd( p->pGia, iLit0, iLit1 ); - Gia_ObjSetGateLevel( p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew)) ); -// printf( "%d ", Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew))) ); - // replace entries - assert( pNods[0] >= 2 ); - nPairsStart = Hash_IntManEntryNum(p->vHash) + 1; - Vec_IntClear( vDivs ); - for ( i = 1; i <= pNods[0]; i++ ) - nPresent += Dam_ManUpdateNode( p, pNods[i], iLit0, iLit1, iLitNew, vDivs ); - nPairsStop = Hash_IntManEntryNum(p->vHash) + 1; - // extend arrayvs - pPairsNew = 0; - Vec_FltFillExtra( p->vCounts, nPairsStop, 0 ); - Vec_IntFillExtra( p->vDiv2Nod, nPairsStop, -1 ); - for ( i = nPairsStart; i < nPairsStop; i++ ) - { - nRefs = Hash_IntObjData2(p->vHash, i); - if ( nRefs < 2 ) - continue; - Vec_FltWriteEntry( p->vCounts, i, nRefs + 0.001*Dam_ManDivSlack(p, Hash_IntObjData0(p->vHash, i), Hash_IntObjData1(p->vHash, i), Vec_IntEntry(p->vDivLevR, i)) ); - Vec_QuePush( p->vQue, i ); - // remember divisors - Vec_IntWriteEntry( p->vDiv2Nod, i, Vec_IntSize(p->vNodStore) ); - Vec_IntPush( p->vNodStore, 0 ); - Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 ); - pPairsNew++; - } -// printf( "Added %d new pairs\n", pPairsNew ); - // fill in the divisors - iNode = -1; - Vec_IntForEachEntry( vDivs, iDivTemp, i ) - { - if ( iDivTemp < 0 ) - { - iNode = -iDivTemp; - continue; - } - if ( Vec_IntEntry(p->vDiv2Nod, iDivTemp) == -1 ) - continue; - pSet = Dam_DivSet( p, iDivTemp ); - pSet[++pSet[0]] = iNode; - } - // make sure divisors are added correctly - for ( i = nPairsStart; i < nPairsStop; i++ ) - if ( Vec_IntEntry(p->vDiv2Nod, i) > 0 ) - assert( Dam_DivSet(p, i)[0] == Hash_IntObjData2(p->vHash, i) ); - // update costs - Vec_FltWriteEntry( p->vCounts, iDiv, 0 ); - p->nGain += (1 + 2 * fThisIsXor) * (nPresent - 1); - p->nGainX += 3 * fThisIsXor * (nPresent - 1); - p->nDivs++; -} - -/**Function************************************************************* - - Synopsis [Perform extraction for multi-input AND/XOR.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Dam_ManAreaBalanceInt( Gia_Man_t * pGia, Vec_Int_t * vCiLevels, int nNewNodesMax, int fVerbose, int fVeryVerbose ) -{ - Gia_Man_t * pNew; - Dam_Man_t * p; - int i, iDiv; - p = Dam_ManAlloc( pGia ); - p->nLevelMax = Gia_ManSetLevels( p->pGia, vCiLevels ); - p->vNodLevR = Gia_ManReverseLevel( p->pGia ); - Vec_IntFillExtra( p->pGia->vLevels, 3*Gia_ManObjNum(p->pGia)/2, 0 ); - Dam_ManCreatePairs( p, fVerbose ); - for ( i = 0; i < nNewNodesMax && Vec_QueTopPriority(p->vQue) >= 2; i++ ) - { - iDiv = Vec_QuePop(p->vQue); - if ( fVeryVerbose ) - Dam_PrintDiv( p, iDiv ); - Dam_ManUpdate( p, iDiv ); - } - if ( fVeryVerbose ) - Dam_PrintDiv( p, 0 ); - pNew = Dam_ManMultiAig( p ); - if ( fVerbose ) - { - int nDivsAll = Hash_IntManEntryNum(p->vHash); - int nDivsUsed = p->nDivs; - printf( "Div: " ); - printf( " Total =%9d (%6.2f %%) ", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) ); - printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) ); - printf( " Gain =%6d (%6.2f %%)", p->nGain, 100.0 * p->nGain / Abc_MaxInt(p->nAnds, 1) ); - printf( " GainX = %d ", p->nGainX ); - Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart ); - } - Dam_ManFree( p ); - return pNew; -} -Gia_Man_t * Gia_ManAreaBalance( Gia_Man_t * p, int fSimpleAnd, int nNewNodesMax, int fVerbose, int fVeryVerbose ) -{ - Gia_Man_t * pNew0, * pNew, * pNew1, * pNew2; - Vec_Int_t * vCiLevels; - // determine CI levels - if ( p->pManTime && p->vLevels == NULL ) - Gia_ManLevelWithBoxes( p ); - vCiLevels = Gia_ManGetCiLevels( p ); - // get the starting manager - pNew0 = Gia_ManHasMapping(p) ? (Gia_Man_t *)Dsm_ManDeriveGia(p, 0) : p; - if ( fVerbose ) Gia_ManPrintStats( pNew0, NULL ); - // derive internal manager - pNew = fSimpleAnd ? Gia_ManDup( pNew0 ) : Gia_ManDupMuxes( pNew0, 2 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - if ( pNew0 != p ) Gia_ManStop( pNew0 ); - // perform the operation - pNew1 = Dam_ManAreaBalanceInt( pNew, vCiLevels, nNewNodesMax, fVerbose, fVeryVerbose ); - if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL ); - Gia_ManStop( pNew ); - Vec_IntFreeP( &vCiLevels ); - // derive the final result - pNew2 = Gia_ManDupNoMuxes( pNew1 ); - if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL ); - Gia_ManStop( pNew1 ); - // normalize if needed - if ( !Gia_ManIsNormalized(pNew2) ) - { - pNew2 = Gia_ManDupNormalize( pNew1 = pNew2 ); - Gia_ManStop( pNew1 ); - } - Gia_ManTransferTiming( pNew2, p ); - return pNew2; -} - -/**Function************************************************************* - - Synopsis [Synthesis script.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Gia_ManAigPrintPiLevels( Gia_Man_t * p ) -{ - Gia_Obj_t * pObj; - int i; - Gia_ManForEachPi( p, pObj, i ) - printf( "%d ", Gia_ObjLevel(p, pObj) ); - printf( "\n" ); -} - -/**Function************************************************************* - - Synopsis [Synthesis script.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Gia_ManAigSyn2( Gia_Man_t * pInit, int fOldAlgo, int fCoarsen, int fCutMin, int nRelaxRatio, int fDelayMin, int fVerbose, int fVeryVerbose ) -{ - Gia_Man_t * p, * pNew, * pTemp; - Jf_Par_t Pars, * pPars = &Pars; - if ( fOldAlgo ) - { - Jf_ManSetDefaultPars( pPars ); - pPars->fCutMin = fCutMin; - } - else - { - Lf_ManSetDefaultPars( pPars ); - pPars->fCutMin = fCutMin; - pPars->fCoarsen = fCoarsen; - pPars->nRelaxRatio = nRelaxRatio; - pPars->nAreaTuner = 1; - pPars->nCutNum = 4; - } - if ( fVerbose ) Gia_ManPrintStats( pInit, NULL ); - p = Gia_ManDup( pInit ); - Gia_ManTransferTiming( p, pInit ); - if ( Gia_ManAndNum(p) == 0 ) - return p; - // delay optimization - if ( fDelayMin && p->pManTime == NULL ) - { - int Area0, Area1, Delay0, Delay1; - int fCutMin = pPars->fCutMin; - int fCoarsen = pPars->fCoarsen; - int nRelaxRatio = pPars->nRelaxRatio; - pPars->fCutMin = 0; - pPars->fCoarsen = 0; - pPars->nRelaxRatio = 0; - // perform mapping - if ( fOldAlgo ) - Jf_ManPerformMapping( p, pPars ); - else - Lf_ManPerformMapping( p, pPars ); - Area0 = (int)pPars->Area; - Delay0 = (int)pPars->Delay; - // perform balancing - pNew = Gia_ManPerformDsdBalance( p, 6, 4, 0, 0 ); - // perform mapping again - if ( fOldAlgo ) - Jf_ManPerformMapping( pNew, pPars ); - else - Lf_ManPerformMapping( pNew, pPars ); - Area1 = (int)pPars->Area; - Delay1 = (int)pPars->Delay; - // choose the best result - if ( Delay1 < Delay0 - 1 || (Delay1 == Delay0 + 1 && 100.0 * (Area1 - Area0) / Area1 < 3.0) ) - { - Gia_ManStop( p ); - p = pNew; - } - else - { - Gia_ManStop( pNew ); - Vec_IntFreeP( &p->vMapping ); - } - // reset params - pPars->fCutMin = fCutMin; - pPars->fCoarsen = fCoarsen; - pPars->nRelaxRatio = nRelaxRatio; - } - // perform balancing - pNew = Gia_ManAreaBalance( p, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( p ); - // perform mapping - if ( fOldAlgo ) - pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); - else - pNew = Lf_ManPerformMapping( pTemp = pNew, pPars ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - if ( pTemp != pNew ) - Gia_ManStop( pTemp ); - // perform balancing - pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); - return pNew; -} -Gia_Man_t * Gia_ManAigSyn3( Gia_Man_t * p, int fVerbose, int fVeryVerbose ) -{ - Gia_Man_t * pNew, * pTemp; - Jf_Par_t Pars, * pPars = &Pars; - Jf_ManSetDefaultPars( pPars ); - pPars->nRelaxRatio = 40; - if ( fVerbose ) Gia_ManPrintStats( p, NULL ); - if ( Gia_ManAndNum(p) == 0 ) - return Gia_ManDup(p); - // perform balancing - pNew = Gia_ManAreaBalance( p, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - // perform mapping - pPars->nLutSize = 6; - pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); -// Gia_ManStop( pTemp ); - // perform balancing - pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); - // perform mapping - pPars->nLutSize = 4; - pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); -// Gia_ManStop( pTemp ); - // perform balancing - pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); - return pNew; -} -Gia_Man_t * Gia_ManAigSyn4( Gia_Man_t * p, int fVerbose, int fVeryVerbose ) -{ - Gia_Man_t * pNew, * pTemp; - Jf_Par_t Pars, * pPars = &Pars; - Jf_ManSetDefaultPars( pPars ); - pPars->nRelaxRatio = 40; - if ( fVerbose ) Gia_ManPrintStats( p, NULL ); - if ( Gia_ManAndNum(p) == 0 ) - return Gia_ManDup(p); -//Gia_ManAigPrintPiLevels( p ); - // perform balancing - pNew = Gia_ManAreaBalance( p, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - // perform mapping - pPars->nLutSize = 7; - pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); -// Gia_ManStop( pTemp ); - // perform extraction - pNew = Gia_ManPerformFx( pTemp = pNew, ABC_INFINITY, 0, 0, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); - // perform balancing - pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); - // perform mapping - pPars->nLutSize = 5; - pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); -// Gia_ManStop( pTemp ); - // perform extraction - pNew = Gia_ManPerformFx( pTemp = pNew, ABC_INFINITY, 0, 0, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); - // perform balancing - pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); - if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); - Gia_ManStop( pTemp ); -//Gia_ManAigPrintPiLevels( pNew ); - return pNew; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/gia/giaBalance2.c b/src/aig/gia/giaBalance2.c deleted file mode 100644 index 73d2a6fb..00000000 --- a/src/aig/gia/giaBalance2.c +++ /dev/null @@ -1,982 +0,0 @@ -/**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_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/giaScript.c b/src/aig/gia/giaScript.c new file mode 100644 index 00000000..cf58f794 --- /dev/null +++ b/src/aig/gia/giaScript.c @@ -0,0 +1,369 @@ +/**CFile**************************************************************** + + FileName [giaScript.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [Various hardcoded scripts.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: giaScript.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" +#include "base/main/main.h" +#include "base/cmd/cmd.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Synthesis script.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManAigPrintPiLevels( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + int i; + Gia_ManForEachPi( p, pObj, i ) + printf( "%d ", Gia_ObjLevel(p, pObj) ); + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Synthesis script.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManAigSyn2( Gia_Man_t * pInit, int fOldAlgo, int fCoarsen, int fCutMin, int nRelaxRatio, int fDelayMin, int fVerbose, int fVeryVerbose ) +{ + Gia_Man_t * p, * pNew, * pTemp; + Jf_Par_t Pars, * pPars = &Pars; + if ( fOldAlgo ) + { + Jf_ManSetDefaultPars( pPars ); + pPars->fCutMin = fCutMin; + } + else + { + Lf_ManSetDefaultPars( pPars ); + pPars->fCutMin = fCutMin; + pPars->fCoarsen = fCoarsen; + pPars->nRelaxRatio = nRelaxRatio; + pPars->nAreaTuner = 1; + pPars->nCutNum = 4; + } + if ( fVerbose ) Gia_ManPrintStats( pInit, NULL ); + p = Gia_ManDup( pInit ); + Gia_ManTransferTiming( p, pInit ); + if ( Gia_ManAndNum(p) == 0 ) + return p; + // delay optimization + if ( fDelayMin && p->pManTime == NULL ) + { + int Area0, Area1, Delay0, Delay1; + int fCutMin = pPars->fCutMin; + int fCoarsen = pPars->fCoarsen; + int nRelaxRatio = pPars->nRelaxRatio; + pPars->fCutMin = 0; + pPars->fCoarsen = 0; + pPars->nRelaxRatio = 0; + // perform mapping + if ( fOldAlgo ) + Jf_ManPerformMapping( p, pPars ); + else + Lf_ManPerformMapping( p, pPars ); + Area0 = (int)pPars->Area; + Delay0 = (int)pPars->Delay; + // perform balancing + pNew = Gia_ManPerformDsdBalance( p, 6, 4, 0, 0 ); + // perform mapping again + if ( fOldAlgo ) + Jf_ManPerformMapping( pNew, pPars ); + else + Lf_ManPerformMapping( pNew, pPars ); + Area1 = (int)pPars->Area; + Delay1 = (int)pPars->Delay; + // choose the best result + if ( Delay1 < Delay0 - 1 || (Delay1 == Delay0 + 1 && 100.0 * (Area1 - Area0) / Area1 < 3.0) ) + { + Gia_ManStop( p ); + p = pNew; + } + else + { + Gia_ManStop( pNew ); + Vec_IntFreeP( &p->vMapping ); + } + // reset params + pPars->fCutMin = fCutMin; + pPars->fCoarsen = fCoarsen; + pPars->nRelaxRatio = nRelaxRatio; + } + // perform balancing + pNew = Gia_ManAreaBalance( p, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( p ); + // perform mapping + if ( fOldAlgo ) + pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); + else + pNew = Lf_ManPerformMapping( pTemp = pNew, pPars ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + if ( pTemp != pNew ) + Gia_ManStop( pTemp ); + // perform balancing + pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); + return pNew; +} +Gia_Man_t * Gia_ManAigSyn3( Gia_Man_t * p, int fVerbose, int fVeryVerbose ) +{ + Gia_Man_t * pNew, * pTemp; + Jf_Par_t Pars, * pPars = &Pars; + Jf_ManSetDefaultPars( pPars ); + pPars->nRelaxRatio = 40; + if ( fVerbose ) Gia_ManPrintStats( p, NULL ); + if ( Gia_ManAndNum(p) == 0 ) + return Gia_ManDup(p); + // perform balancing + pNew = Gia_ManAreaBalance( p, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + // perform mapping + pPars->nLutSize = 6; + pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); +// Gia_ManStop( pTemp ); + // perform balancing + pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); + // perform mapping + pPars->nLutSize = 4; + pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); +// Gia_ManStop( pTemp ); + // perform balancing + pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); + return pNew; +} +Gia_Man_t * Gia_ManAigSyn4( Gia_Man_t * p, int fVerbose, int fVeryVerbose ) +{ + Gia_Man_t * pNew, * pTemp; + Jf_Par_t Pars, * pPars = &Pars; + Jf_ManSetDefaultPars( pPars ); + pPars->nRelaxRatio = 40; + if ( fVerbose ) Gia_ManPrintStats( p, NULL ); + if ( Gia_ManAndNum(p) == 0 ) + return Gia_ManDup(p); +//Gia_ManAigPrintPiLevels( p ); + // perform balancing + pNew = Gia_ManAreaBalance( p, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + // perform mapping + pPars->nLutSize = 7; + pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); +// Gia_ManStop( pTemp ); + // perform extraction + pNew = Gia_ManPerformFx( pTemp = pNew, ABC_INFINITY, 0, 0, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); + // perform balancing + pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); + // perform mapping + pPars->nLutSize = 5; + pNew = Jf_ManPerformMapping( pTemp = pNew, pPars ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); +// Gia_ManStop( pTemp ); + // perform extraction + pNew = Gia_ManPerformFx( pTemp = pNew, ABC_INFINITY, 0, 0, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); + // perform balancing + pNew = Gia_ManAreaBalance( pTemp = pNew, 0, ABC_INFINITY, fVeryVerbose, 0 ); + if ( fVerbose ) Gia_ManPrintStats( pNew, NULL ); + Gia_ManStop( pTemp ); +//Gia_ManAigPrintPiLevels( pNew ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManPerformMap( int nAnds, int nLutSize, int nCutNum, int fVerbose ) +{ + char Command[200]; + sprintf( Command, "&unmap; &lf -K %d -C %d -k; &save", nLutSize, nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); + if ( fVerbose ) + { + printf( "MAPPING:\n" ); + printf( "Mapping with &lf -k:\n" ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); + } + sprintf( Command, "&unmap; &lf -K %d -C %d; &save", nLutSize, nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); + if ( fVerbose ) + { + printf( "Mapping with &lf:\n" ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); + } + if ( (nLutSize == 4 && nAnds < 100000) || (nLutSize == 6 && nAnds < 2000) ) + { + sprintf( Command, "&unmap; &if -sz -S %d%d -K %d -C %d", nLutSize, nLutSize, 2*nLutSize-1, 2*nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); + Vec_IntFreeP( &Abc_FrameReadGia(Abc_FrameGetGlobalFrame())->vPacking ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&save" ); + if ( fVerbose ) + { + printf( "Mapping with &if -sz -S %d%d -K %d -C %d:\n", nLutSize, nLutSize, 2*nLutSize-1, 2*nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); + } + } + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&load" ); + if ( fVerbose ) + { + printf( "Mapping final:\n" ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); + } +} +void Gia_ManPerformRound( int fIsMapped, int nAnds, int nLevels, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + char Command[200]; + + // perform AIG-based synthesis + if ( nAnds < 50000 ) + { + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "" ); + sprintf( Command, "&dsdb; &dch -f; &if -K %d -C %d; &save", nLutSize, nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); + if ( fVerbose ) + { + printf( "Mapping with &dch -f; &if -K %d -C %d:\n", nLutSize, nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); + } + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); + } + + // perform AIG-based synthesis + if ( nAnds < 20000 ) + { + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "" ); + sprintf( Command, "&dsdb; &dch -f; &if -K %d -C %d; &save", nLutSize, nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); + if ( fVerbose ) + { + printf( "Mapping with &dch -f; &if -K %d -C %d:\n", nLutSize, nCutNum ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); + } + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); + } + + // perform first round of mapping + Gia_ManPerformMap( nAnds, nLutSize, nCutNum, fVerbose ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); + + // perform synthesis + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&dsdb" ); + + // perform second round of mapping + Gia_ManPerformMap( nAnds, nLutSize, nCutNum, fVerbose ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); + + // perform synthesis + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&syn2 -m -R 10; &dsdb" ); + + // prepare for final mapping + sprintf( Command, "&blut -a -K %d", nLutSize ); + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); + + // perform third round of mapping + Gia_ManPerformMap( nAnds, nLutSize, nCutNum, fVerbose ); +} +void Gia_ManPerformFlow( int fIsMapped, int nAnds, int nLevels, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + // remove comb equivs + if ( fIsMapped ) + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); + if ( Abc_FrameReadGia(Abc_FrameGetGlobalFrame())->pManTime ) + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&sweep" ); + else + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&fraig -c" ); + + // perform first round + Gia_ManPerformRound( fIsMapped, nAnds, nLevels, nLutSize, nCutNum, nRelaxRatio, fVerbose ); + + // perform synthesis + Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st; &sopb" ); + + // perform first round + Gia_ManPerformRound( fIsMapped, nAnds, nLevels, nLutSize, nCutNum, nRelaxRatio, fVerbose ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManAigSynch2( Gia_Man_t * p, int fVerbose ) +{ + return NULL; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/giaSopb.c b/src/aig/gia/giaSopb.c deleted file mode 100644 index 57de4cfe..00000000 --- a/src/aig/gia/giaSopb.c +++ /dev/null @@ -1,450 +0,0 @@ -/**CFile**************************************************************** - - FileName [giaSopb.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Scalable AIG package.] - - Synopsis [SOP balancing for a window.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: giaSopb.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "gia.h" -#include "base/main/main.h" -#include "base/cmd/cmd.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Gia_ManHighlight_rec( Gia_Man_t * p, int iObj ) -{ - Gia_Obj_t * pObj; - if ( Gia_ObjIsTravIdCurrentId(p, iObj) ) - return; - Gia_ObjSetTravIdCurrentId(p, iObj); - pObj = Gia_ManObj( p, iObj ); - if ( Gia_ObjIsAnd(pObj) ) - Gia_ManHighlight_rec( p, Gia_ObjFaninId0(pObj, iObj) ); - if ( Gia_ObjIsAnd(pObj) ) - Gia_ManHighlight_rec( p, Gia_ObjFaninId1(pObj, iObj) ); -} -void Gia_ManPrepareWin( Gia_Man_t * p, Vec_Int_t * vOuts, Vec_Int_t ** pvPis, Vec_Int_t ** pvPos, Vec_Int_t ** pvAnds, int fPoOnly ) -{ - Gia_Obj_t * pObj; - int i; - // mark the section - Gia_ManIncrementTravId( p ); - Gia_ManForEachCoVec( vOuts, p, pObj, i ) - Gia_ManHighlight_rec( p, Gia_ObjFaninId0p(p, pObj) ); - // mark fanins of the outside area - Gia_ManCleanMark0( p ); - if ( fPoOnly ) - { - Gia_ManForEachCoVec( vOuts, p, pObj, i ) - Gia_ObjFanin0(pObj)->fMark0 = 1; - } - else - { - Gia_ManForEachObj1( p, pObj, i ) - { - if ( Gia_ObjIsCi(pObj) ) - continue; - if ( Gia_ObjIsAnd(pObj) && !Gia_ObjIsTravIdCurrentId(p, i) ) - continue; - Gia_ObjFanin0(pObj)->fMark0 = 1; - if ( Gia_ObjIsAnd(pObj) ) - Gia_ObjFanin1(pObj)->fMark0 = 1; - } - } - // collect pointed nodes - *pvPis = Vec_IntAlloc( 1000 ); - *pvPos = Vec_IntAlloc( 1000 ); - *pvAnds = Vec_IntAlloc( 1000 ); - Gia_ManForEachObj1( p, pObj, i ) - { - if ( !Gia_ObjIsTravIdCurrentId(p, i) ) - continue; - if ( Gia_ObjIsCi(pObj) ) - Vec_IntPush( *pvPis, i ); - else if ( pObj->fMark0 ) - Vec_IntPush( *pvPos, i ); - if ( Gia_ObjIsAnd(pObj) ) - Vec_IntPush( *pvAnds, i ); - } - Gia_ManCleanMark0( p ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Gia_ManExtractWin( Gia_Man_t * p, Vec_Int_t * vOuts, int fPoOnly ) -{ - Vec_Int_t * vPis, * vPos, * vAnds; - Gia_Man_t * pNew; - Gia_Obj_t * pObj; - int i; - Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, fPoOnly ); - // create AIG - pNew = Gia_ManStart( Vec_IntSize(vPis) + Vec_IntSize(vPos) + Vec_IntSize(vAnds) + 1 ); - pNew->pName = Abc_UtilStrsav( p->pName ); - Gia_ManConst0(p)->Value = 0; - Gia_ManForEachObjVec( vPis, p, pObj, i ) - pObj->Value = Gia_ManAppendCi( pNew ); - Gia_ManForEachObjVec( vAnds, p, pObj, i ) - pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); - Gia_ManForEachObjVec( vPos, p, pObj, i ) - Gia_ManAppendCo( pNew, pObj->Value ); - Vec_IntFree( vPis ); - Vec_IntFree( vPos ); - Vec_IntFree( vAnds ); - return pNew; -} -Gia_Man_t * Gia_ManInsertWin( Gia_Man_t * p, Vec_Int_t * vOuts, Gia_Man_t * pWin ) -{ - Vec_Int_t * vPos, * vPis, * vAnds; - Gia_Man_t * pNew, * pTemp; - Gia_Obj_t * pObj; - int i; - Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, 0 ); - // create AIG - pNew = Gia_ManStart( Gia_ManObjNum(p) - Vec_IntSize(vAnds) + Gia_ManAndNum(pWin) ); - pNew->pName = Abc_UtilStrsav( p->pName ); - pNew->pSpec = Abc_UtilStrsav( p->pSpec ); - // inputs - Gia_ManConst0(p)->Value = 0; - Gia_ManForEachCi( p, pObj, i ) - pObj->Value = Gia_ManAppendCi( pNew ); - Gia_ManConst0(pWin)->Value = 0; - Gia_ManForEachCi( pWin, pObj, i ) - pObj->Value = Gia_ManObj(p, Vec_IntEntry(vPis, i))->Value; - // internal nodes - Gia_ManHashAlloc( pNew ); - Gia_ManForEachAnd( pWin, pObj, i ) - pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); - Gia_ManForEachCo( pWin, pObj, i ) - Gia_ManObj( p, Vec_IntEntry(vPos, i) )->Value = Gia_ObjFanin0Copy(pObj); - Gia_ManForEachAnd( p, pObj, i ) - if ( !Gia_ObjIsTravIdCurrentId(p, i) ) - pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); - Gia_ManForEachCo( p, pObj, i ) - Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); - Gia_ManHashStop( pNew ); - // cleanup - Vec_IntFree( vPis ); - Vec_IntFree( vPos ); - Vec_IntFree( vAnds ); - pNew = Gia_ManCleanup( pTemp = pNew ); - Gia_ManStop( pTemp ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Gia_ManFindLatest( Gia_Man_t * p, int LevelMax, int nTimeWindow ) -{ - Gia_Obj_t * pObj; - Vec_Int_t * vOuts; - vOuts = Vec_IntAlloc( 1000 ); - if ( Gia_ManHasMapping(p) ) - { - int i, k, iFan, nLevels = 0; - int * pLevels = ABC_CALLOC( int, Gia_ManObjNum(p) ); - Gia_ManForEachLut( p, i ) - { - Gia_LutForEachFanin( p, i, iFan, k ) - pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[iFan] ); - pLevels[i]++; - nLevels = Abc_MaxInt( nLevels, pLevels[i] ); - } - if ( nTimeWindow ) - LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels); - if ( nLevels < LevelMax ) - printf( "The maximum mapped level (%d) is less than the target level (%d).\n", nLevels, LevelMax ); - Gia_ManForEachCo( p, pObj, i ) - if ( pLevels[Gia_ObjFaninId0p(p, pObj)] >= LevelMax ) - Vec_IntPush( vOuts, i ); - ABC_FREE( pLevels ); - } - else - { - int i, nLevels = Gia_ManLevelNum( p ); - if ( nTimeWindow ) - LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels); - if ( nLevels < LevelMax ) - printf( "The maximum AIG level (%d) is less than the target level (%d).\n", nLevels, LevelMax ); - Gia_ManForEachCo( p, pObj, i ) - if ( Gia_ObjLevel(p, pObj) >= LevelMax ) - Vec_IntPush( vOuts, i ); - } - return vOuts; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Gia_ManExtractWindow( Gia_Man_t * p, int LevelMax, int nTimeWindow, int fVerbose ) -{ - Vec_Int_t * vOuts; - Gia_Man_t * pWin; - assert( !LevelMax != !nTimeWindow ); - vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); - if ( fVerbose ) - printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); - if ( Vec_IntSize(vOuts) == 0 ) - { - Vec_IntFree( vOuts ); - return Gia_ManDup( p ); - } - pWin = Gia_ManExtractWin( p, vOuts, 1 ); - Vec_IntFree( vOuts ); - return pWin; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Gia_ManPerformSopBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nCutNum, int nRelaxRatio, int fVerbose ) -{ - Vec_Int_t * vOuts; - Gia_Man_t * pNew, * pWin, * pWinNew; - assert( !LevelMax != !nTimeWindow ); - vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); - if ( fVerbose ) - printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); - if ( Vec_IntSize(vOuts) == 0 ) - { - Vec_IntFree( vOuts ); - return Gia_ManDup( p ); - } - pWin = Gia_ManExtractWin( p, vOuts, 0 ); - pWinNew = Gia_ManPerformSopBalance( pWin, nCutNum, nRelaxRatio, fVerbose ); - Gia_ManStop( pWin ); - pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); - Gia_ManStop( pWinNew ); - Vec_IntFree( vOuts ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Gia_Man_t * Gia_ManPerformDsdBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) -{ - Vec_Int_t * vOuts; - Gia_Man_t * pNew, * pWin, * pWinNew; - assert( !LevelMax != !nTimeWindow ); - vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); - if ( fVerbose ) - printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); - if ( Vec_IntSize(vOuts) == 0 ) - { - Vec_IntFree( vOuts ); - return Gia_ManDup( p ); - } - pWin = Gia_ManExtractWin( p, vOuts, 0 ); - pWinNew = Gia_ManPerformDsdBalance( pWin, nLutSize, nCutNum, nRelaxRatio, fVerbose ); - Gia_ManStop( pWin ); - pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); - Gia_ManStop( pWinNew ); - Vec_IntFree( vOuts ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Gia_ManPerformMap( int nAnds, int nLutSize, int nCutNum, int fVerbose ) -{ - char Command[200]; - sprintf( Command, "&unmap; &lf -K %d -C %d -k; &save", nLutSize, nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); - if ( fVerbose ) - { - printf( "MAPPING:\n" ); - printf( "Mapping with &lf -k:\n" ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); - } - sprintf( Command, "&unmap; &lf -K %d -C %d; &save", nLutSize, nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); - if ( fVerbose ) - { - printf( "Mapping with &lf:\n" ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); - } - if ( (nLutSize == 4 && nAnds < 100000) || (nLutSize == 6 && nAnds < 2000) ) - { - sprintf( Command, "&unmap; &if -sz -S %d%d -K %d -C %d", nLutSize, nLutSize, 2*nLutSize-1, 2*nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); - Vec_IntFreeP( &Abc_FrameReadGia(Abc_FrameGetGlobalFrame())->vPacking ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&save" ); - if ( fVerbose ) - { - printf( "Mapping with &if -sz -S %d%d -K %d -C %d:\n", nLutSize, nLutSize, 2*nLutSize-1, 2*nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); - } - } - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&load" ); - if ( fVerbose ) - { - printf( "Mapping final:\n" ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); - } -} -void Gia_ManPerformRound( int fIsMapped, int nAnds, int nLevels, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) -{ - char Command[200]; - - // perform AIG-based synthesis - if ( nAnds < 50000 ) - { - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "" ); - sprintf( Command, "&dsdb; &dch -f; &if -K %d -C %d; &save", nLutSize, nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); - if ( fVerbose ) - { - printf( "Mapping with &dch -f; &if -K %d -C %d:\n", nLutSize, nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); - } - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); - } - - // perform AIG-based synthesis - if ( nAnds < 20000 ) - { - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "" ); - sprintf( Command, "&dsdb; &dch -f; &if -K %d -C %d; &save", nLutSize, nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); - if ( fVerbose ) - { - printf( "Mapping with &dch -f; &if -K %d -C %d:\n", nLutSize, nCutNum ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&ps" ); - } - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); - } - - // perform first round of mapping - Gia_ManPerformMap( nAnds, nLutSize, nCutNum, fVerbose ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); - - // perform synthesis - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&dsdb" ); - - // perform second round of mapping - Gia_ManPerformMap( nAnds, nLutSize, nCutNum, fVerbose ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); - - // perform synthesis - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&syn2 -m -R 10; &dsdb" ); - - // prepare for final mapping - sprintf( Command, "&blut -a -K %d", nLutSize ); - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), Command ); - - // perform third round of mapping - Gia_ManPerformMap( nAnds, nLutSize, nCutNum, fVerbose ); -} -void Gia_ManPerformFlow( int fIsMapped, int nAnds, int nLevels, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) -{ - // remove comb equivs - if ( fIsMapped ) - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st" ); - if ( Abc_FrameReadGia(Abc_FrameGetGlobalFrame())->pManTime ) - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&sweep" ); - else - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&fraig -c" ); - - // perform first round - Gia_ManPerformRound( fIsMapped, nAnds, nLevels, nLutSize, nCutNum, nRelaxRatio, fVerbose ); - - // perform synthesis - Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "&st; &sopb" ); - - // perform first round - Gia_ManPerformRound( fIsMapped, nAnds, nLevels, nLutSize, nCutNum, nRelaxRatio, fVerbose ); -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index 5004199b..2f6c5512 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -2,8 +2,9 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaAgi.c \ src/aig/gia/giaAiger.c \ src/aig/gia/giaAigerExt.c \ - src/aig/gia/giaBalance.c \ - src/aig/gia/giaBalance2.c \ + src/aig/gia/giaBalAig.c \ + src/aig/gia/giaBalLut.c \ + src/aig/gia/giaBalMap.c \ src/aig/gia/giaBidec.c \ src/aig/gia/giaCCof.c \ src/aig/gia/giaCex.c \ @@ -48,12 +49,12 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaResub.c \ src/aig/gia/giaRetime.c \ src/aig/gia/giaScl.c \ + src/aig/gia/giaScript.c \ src/aig/gia/giaShrink.c \ src/aig/gia/giaShrink6.c \ src/aig/gia/giaShrink7.c \ src/aig/gia/giaSim.c \ src/aig/gia/giaSim2.c \ - src/aig/gia/giaSopb.c \ src/aig/gia/giaSort.c \ src/aig/gia/giaSpeedup.c \ src/aig/gia/giaStg.c \ -- cgit v1.2.3