/**CFile**************************************************************** FileName [giaResub2.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Scalable AIG package.] Synopsis [] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: giaResub2.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "gia.h" #include "misc/util/utilTruth.h" #include "misc/vec/vecHsh.h" #include "opt/dau/dau.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// typedef struct Gia_Rsb2Man_t_ Gia_Rsb2Man_t; struct Gia_Rsb2Man_t_ { // hyper-parameters int nDivsMax; int nLevelIncrease; int fUseXor; int fUseZeroCost; int fDebug; int fVerbose; // input AIG int nObjs; int nPis; int nNodes; int nPos; int iFirstPo; int Level; int nMffc; // intermediate data Vec_Int_t vObjs; Vec_Wrd_t vSims; Vec_Ptr_t vpDivs; Vec_Int_t vDivs; Vec_Int_t vLevels; Vec_Int_t vRefs; Vec_Int_t vCopies; Vec_Int_t vTried; word Truth0; word Truth1; word CareSet; }; extern void Abc_ResubPrepareManager( int nWords ); extern int Abc_ResubComputeFunction( void ** ppDivs, int nDivs, int nWords, int nLimit, int nDivsMax, int iChoice, int fUseXor, int fDebug, int fVerbose, int ** ppArray ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Gia_Rsb2Man_t * Gia_Rsb2ManAlloc() { Gia_Rsb2Man_t * p = ABC_CALLOC( Gia_Rsb2Man_t, 1 ); return p; } void Gia_Rsb2ManFree( Gia_Rsb2Man_t * p ) { Vec_IntErase( &p->vObjs ); Vec_WrdErase( &p->vSims ); Vec_PtrErase( &p->vpDivs ); Vec_IntErase( &p->vDivs ); Vec_IntErase( &p->vLevels ); Vec_IntErase( &p->vRefs ); Vec_IntErase( &p->vCopies ); Vec_IntErase( &p->vTried ); ABC_FREE( p ); } void Gia_Rsb2ManStart( Gia_Rsb2Man_t * p, int * pObjs, int nObjs, int nDivsMax, int nLevelIncrease, int fUseXor, int fUseZeroCost, int fDebug, int fVerbose ) { int i; // hyper-parameters p->nDivsMax = nDivsMax; p->nLevelIncrease = nLevelIncrease; p->fUseXor = fUseXor; p->fUseZeroCost = fUseZeroCost; p->fDebug = fDebug; p->fVerbose = fVerbose; // user data Vec_IntClear( &p->vObjs ); Vec_IntPushArray( &p->vObjs, pObjs, 2*nObjs ); assert( pObjs[0] == 0 ); assert( pObjs[1] == 0 ); p->nObjs = nObjs; p->nPis = 0; p->nNodes = 0; p->nPos = 0; p->iFirstPo = 0; for ( i = 1; i < nObjs; i++ ) { if ( pObjs[2*i+0] == 0 && pObjs[2*i+1] == 0 ) p->nPis++; else if ( pObjs[2*i+0] == pObjs[2*i+1] ) p->nPos++; else p->nNodes++; } assert( nObjs == 1 + p->nPis + p->nNodes + p->nPos ); p->iFirstPo = nObjs - p->nPos; Vec_WrdClear( &p->vSims ); Vec_WrdGrow( &p->vSims, 2*nObjs ); Vec_WrdPush( &p->vSims, 0 ); Vec_WrdPush( &p->vSims, 0 ); for ( i = 0; i < p->nPis; i++ ) { Vec_WrdPush( &p->vSims, s_Truths6[i] ); Vec_WrdPush( &p->vSims, ~s_Truths6[i] ); } p->vSims.nSize = 2*p->nObjs; Vec_IntClear( &p->vDivs ); Vec_IntClear( &p->vLevels ); Vec_IntClear( &p->vRefs ); Vec_IntClear( &p->vCopies ); Vec_IntClear( &p->vTried ); Vec_PtrClear( &p->vpDivs ); Vec_IntGrow( &p->vDivs, nObjs ); Vec_IntGrow( &p->vLevels, nObjs ); Vec_IntGrow( &p->vRefs, nObjs ); Vec_IntGrow( &p->vCopies, nObjs ); Vec_IntGrow( &p->vTried, nObjs ); Vec_PtrGrow( &p->vpDivs, nObjs ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Gia_Rsb2ManPrint( Gia_Rsb2Man_t * p ) { int i, * pObjs = Vec_IntArray( &p->vObjs ); printf( "PI = %d. PO = %d. Obj = %d.\n", p->nPis, p->nPos, p->nObjs ); for ( i = p->nPis + 1; i < p->iFirstPo; i++ ) printf( "%2d = %c%2d & %c%2d;\n", i, Abc_LitIsCompl(pObjs[2*i+0]) ? '!' : ' ', Abc_Lit2Var(pObjs[2*i+0]), Abc_LitIsCompl(pObjs[2*i+1]) ? '!' : ' ', Abc_Lit2Var(pObjs[2*i+1]) ); for ( i = p->iFirstPo; i < p->nObjs; i++ ) printf( "%2d = %c%2d;\n", i, Abc_LitIsCompl(pObjs[2*i+0]) ? '!' : ' ', Abc_Lit2Var(pObjs[2*i+0]) ); } int Gia_Rsb2ManLevel( Gia_Rsb2Man_t * p ) { int i, * pLevs, Level = 0; Vec_IntClear( &p->vLevels ); Vec_IntGrow( &p->vLevels, p->nObjs ); pLevs = Vec_IntArray( &p->vLevels ); for ( i = p->nPis + 1; i < p->iFirstPo; i++ ) pLevs[i] = 1 + Abc_MaxInt( pLevs[2*i+0]/2, pLevs[2*i+1]/2 ); for ( i = p->iFirstPo; i < p->nObjs; i++ ) Level = Abc_MaxInt( Level, pLevs[i] = pLevs[2*i+0]/2 ); return Level; } word Gia_Rsb2ManOdcs( Gia_Rsb2Man_t * p, int iNode ) { int i; word Res = 0; int * pObjs = Vec_IntArray( &p->vObjs ); word * pSims = Vec_WrdArray( &p->vSims ); for ( i = p->nPis + 1; i < p->iFirstPo; i++ ) { if ( pObjs[2*i+0] < pObjs[2*i+1] ) pSims[2*i+0] = pSims[pObjs[2*i+0]] & pSims[pObjs[2*i+1]]; else if ( pObjs[2*i+0] > pObjs[2*i+1] ) pSims[2*i+0] = pSims[pObjs[2*i+0]] ^ pSims[pObjs[2*i+1]]; else assert( 0 ); pSims[2*i+1] = ~pSims[2*i+0]; } for ( i = p->iFirstPo; i < p->nObjs; i++ ) pSims[2*i+0] = pSims[pObjs[2*i+0]]; ABC_SWAP( word, pSims[2*iNode+0], pSims[2*iNode+1] ); for ( i = iNode + 1; i < p->iFirstPo; i++ ) { if ( pObjs[2*i+0] < pObjs[2*i+1] ) pSims[2*i+0] = pSims[pObjs[2*i+0]] & pSims[pObjs[2*i+1]]; else if ( pObjs[2*i+0] < pObjs[2*i+1] ) pSims[2*i+0] = pSims[pObjs[2*i+0]] ^ pSims[pObjs[2*i+1]]; else assert( 0 ); pSims[2*i+1] = ~pSims[2*i+0]; } for ( i = p->iFirstPo; i < p->nObjs; i++ ) Res |= pSims[2*i+0] ^ pSims[pObjs[2*i+0]]; ABC_SWAP( word, pSims[2*iNode+0], pSims[2*iNode+1] ); return Res; } // marks MFFC and returns its size int Gia_Rsb2ManDeref_rec( Gia_Rsb2Man_t * p, int * pObjs, int * pRefs, int iNode ) { int Counter = 1; if ( iNode <= p->nPis ) return 0; if ( --pRefs[Abc_Lit2Var(pObjs[2*iNode+0])] == 0 ) Counter += Gia_Rsb2ManDeref_rec( p, pObjs, pRefs, Abc_Lit2Var(pObjs[2*iNode+0]) ); if ( --pRefs[Abc_Lit2Var(pObjs[2*iNode+1])] == 0 ) Counter += Gia_Rsb2ManDeref_rec( p, pObjs, pRefs, Abc_Lit2Var(pObjs[2*iNode+1]) ); return Counter; } int Gia_Rsb2ManMffc( Gia_Rsb2Man_t * p, int iNode ) { int i, * pRefs, * pObjs; Vec_IntFill( &p->vRefs, p->nObjs, 0 ); pRefs = Vec_IntArray( &p->vRefs ); pObjs = Vec_IntArray( &p->vObjs ); assert( pObjs[2*iNode+0] != pObjs[2*iNode+1] ); for ( i = p->nPis + 1; i < p->iFirstPo; i++ ) pRefs[Abc_Lit2Var(pObjs[2*i+0])]++, pRefs[Abc_Lit2Var(pObjs[2*i+1])]++; for ( i = p->iFirstPo; i < p->nObjs; i++ ) pRefs[Abc_Lit2Var(pObjs[2*i+0])]++; for ( i = p->nPis + 1; i < p->iFirstPo; i++ ) assert( pRefs[i] ); pRefs[iNode] = 0; for ( i = iNode + 1; i < p->iFirstPo; i++ ) if ( !pRefs[Abc_Lit2Var(pObjs[2*i+0])] || !pRefs[Abc_Lit2Var(pObjs[2*i+1])] ) pRefs[i] = 0; return Gia_Rsb2ManDeref_rec( p, pObjs, pRefs, iNode ); } // collects divisors and maps them into nodes // assumes MFFC is already marked int Gia_Rsb2ManDivs( Gia_Rsb2Man_t * p, int iNode ) { int i, iNodeLevel = 0; int * pRefs = Vec_IntArray( &p->vRefs ); p->CareSet = Gia_Rsb2ManOdcs( p, iNode ); p->Truth1 = p->CareSet & Vec_WrdEntry(&p->vSims, 2*iNode); p->Truth0 = p->CareSet & ~p->Truth1; Vec_PtrClear( &p->vpDivs ); Vec_PtrPush( &p->vpDivs, &p->Truth0 ); Vec_PtrPush( &p->vpDivs, &p->Truth1 ); Vec_IntClear( &p->vDivs ); Vec_IntPushTwo( &p->vDivs, -1, -1 ); for ( i = 1; i <= p->nPis; i++ ) { Vec_PtrPush( &p->vpDivs, Vec_WrdEntryP(&p->vSims, 2*i) ); Vec_IntPush( &p->vDivs, i ); } p->nMffc = Gia_Rsb2ManMffc( p, iNode ); if ( p->nLevelIncrease >= 0 ) { p->Level = Gia_Rsb2ManLevel(p); iNodeLevel = Vec_IntEntry(&p->vLevels, iNode); } for ( i = p->nPis + 1; i < p->iFirstPo; i++ ) { if ( !pRefs[i] || (p->nLevelIncrease >= 0 && Vec_IntEntry(&p->vLevels, i) > iNodeLevel + p->nLevelIncrease) ) continue; Vec_PtrPush( &p->vpDivs, Vec_WrdEntryP(&p->vSims, 2*i) ); Vec_IntPush( &p->vDivs, i ); } assert( Vec_IntSize(&p->vDivs) == Vec_PtrSize(&p->vpDivs) ); return Vec_IntSize(&p->vDivs); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Gia_Rsb2AddNode( Vec_Int_t * vRes, int iLit0, int iLit1, int iRes0, int iRes1 ) { int iLitMin = iRes0 < iRes1 ? Abc_LitNotCond(iRes0, Abc_LitIsCompl(iLit0)) : Abc_LitNotCond(iRes1, Abc_LitIsCompl(iLit1)); int iLitMax = iRes0 < iRes1 ? Abc_LitNotCond(iRes1, Abc_LitIsCompl(iLit1)) : Abc_LitNotCond(iRes0, Abc_LitIsCompl(iLit0)); int iLitRes = Vec_IntSize(vRes); if ( iLit0 < iLit1 ) // and { if ( iLitMin == 0 ) return 0; if ( iLitMin == 1 ) return iLitMax; if ( iLitMin == Abc_LitNot(iLitMax) ) return 0; } else if ( iLit0 > iLit1 ) // xor { if ( iLitMin == 0 ) return iLitMax; if ( iLitMin == 1 ) return Abc_LitNot(iLitMax); if ( iLitMin == Abc_LitNot(iLitMax) ) return 1; } else assert( 0 ); assert( iLitMin >= 2 && iLitMax >= 2 ); if ( iLit0 < iLit1 ) // and Vec_IntPushTwo( vRes, iLitMin, iLitMax ); else if ( iLit0 > iLit1 ) // xor { assert( !Abc_LitIsCompl(iLit0) ); assert( !Abc_LitIsCompl(iLit1) ); Vec_IntPushTwo( vRes, iLitMax, iLitMin ); } else assert( 0 ); return iLitRes; } int Gia_Rsb2ManInsert_rec( Vec_Int_t * vRes, int nPis, Vec_Int_t * vObjs, int iNode, Vec_Int_t * vResub, Vec_Int_t * vDivs, Vec_Int_t * vCopies, int iObj ) { if ( Vec_IntEntry(vCopies, iObj) >= 0 ) return Vec_IntEntry(vCopies, iObj); assert( iObj > nPis ); if ( iObj == iNode ) { int nVars = Vec_IntSize(vDivs); int iLitRes = -1, iTopLit = Vec_IntEntryLast( vResub ); if ( Abc_Lit2Var(iTopLit) == 0 ) iLitRes = 0; else if ( Abc_Lit2Var(iTopLit) < nVars ) iLitRes = Gia_Rsb2ManInsert_rec( vRes, nPis, vObjs, -1, vResub, vDivs, vCopies, Vec_IntEntry(vDivs, Abc_Lit2Var(iTopLit)) ); else { Vec_Int_t * vCopy = Vec_IntAlloc( 10 ); int k, iLit, iLit0, iLit1; Vec_IntForEachEntryStop( vResub, iLit, k, Vec_IntSize(vResub)-1 ) if ( Abc_Lit2Var(iLit) < nVars ) Gia_Rsb2ManInsert_rec( vRes, nPis, vObjs, -1, vResub, vDivs, vCopies, Vec_IntEntry(vDivs, Abc_Lit2Var(iLit)) ); Vec_IntForEachEntryDouble( vResub, iLit0, iLit1, k ) { int iVar0 = Abc_Lit2Var(iLit0); int iVar1 = Abc_Lit2Var(iLit1); int iRes0 = iVar0 < nVars ? Vec_IntEntry(vCopies, Vec_IntEntry(vDivs, iVar0)) : Vec_IntEntry(vCopy, iVar0 - nVars); int iRes1 = iVar1 < nVars ? Vec_IntEntry(vCopies, Vec_IntEntry(vDivs, iVar1)) : Vec_IntEntry(vCopy, iVar1 - nVars); iLitRes = Gia_Rsb2AddNode( vRes, iLit0, iLit1, iRes0, iRes1 ); Vec_IntPush( vCopy, iLitRes ); } Vec_IntFree( vCopy ); } iLitRes = Abc_LitNotCond( iLitRes, Abc_LitIsCompl(iTopLit) ); Vec_IntWriteEntry( vCopies, iObj, iLitRes ); return iLitRes; } else { int iLit0 = Vec_IntEntry( vObjs, 2*iObj+0 ); int iLit1 = Vec_IntEntry( vObjs, 2*iObj+1 ); int iRes0 = Gia_Rsb2ManInsert_rec( vRes, nPis, vObjs, iNode, vResub, vDivs, vCopies, Abc_Lit2Var(iLit0) ); int iRes1 = Gia_Rsb2ManInsert_rec( vRes, nPis, vObjs, iNode, vResub, vDivs, vCopies, Abc_Lit2Var(iLit1) ); int iLitRes = Gia_Rsb2AddNode( vRes, iLit0, iLit1, iRes0, iRes1 ); Vec_IntWriteEntry( vCopies, iObj, iLitRes ); return iLitRes; } } Vec_Int_t * Gia_Rsb2ManInsert( int nPis, int nPos, Vec_Int_t * vObjs, int iNode, Vec_Int_t * vResub, Vec_Int_t * vDivs, Vec_Int_t * vCopies ) { int i, nObjs = Vec_IntSize(vObjs)/2, iFirstPo = nObjs - nPos; Vec_Int_t * vRes = Vec_IntAlloc( Vec_IntSize(vObjs) ); //Vec_IntPrint( vDivs ); //Vec_IntPrint( vResub ); Vec_IntFill( vCopies, Vec_IntSize(vObjs), -1 ); Vec_IntFill( vRes, 2*(nPis + 1), 0 ); for ( i = 0; i <= nPis; i++ ) Vec_IntWriteEntry( vCopies, i, 2*i ); for ( i = iFirstPo; i < nObjs; i++ ) Gia_Rsb2ManInsert_rec( vRes, nPis, vObjs, iNode, vResub, vDivs, vCopies, Abc_Lit2Var( Vec_IntEntry(vObjs, 2*i) ) ); for ( i = iFirstPo; i < nObjs; i++ ) { int iLitNew = Abc_Lit2LitL( Vec_IntArray(vCopies), Vec_IntEntry(vObjs, 2*i) ); Vec_IntPushTwo( vRes, iLitNew, iLitNew ); } return vRes; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_ResubPrintDivs( void ** ppDivs, int nDivs ) { word ** pDivs = (word **)ppDivs; int i; for ( i = 0; i < nDivs; i++ ) { printf( "Div %2d : ", i ); Dau_DsdPrintFromTruth( pDivs[i], 6 ); } } int Abc_ResubNodeToTry( Vec_Int_t * vTried, int iFirst, int iLast ) { int iNode; //for ( iNode = iFirst; iNode < iLast; iNode++ ) for ( iNode = iLast - 1; iNode >= iFirst; iNode-- ) if ( Vec_IntFind(vTried, iNode) == -1 ) return iNode; return -1; } int Abc_ResubComputeWindow( int * pObjs, int nObjs, int nDivsMax, int nLevelIncrease, int fUseXor, int fUseZeroCost, int fDebug, int fVerbose, int ** ppArray, int * pnResubs ) { int iNode, nChanges = 0, RetValue = 0; Gia_Rsb2Man_t * p = Gia_Rsb2ManAlloc(); Gia_Rsb2ManStart( p, pObjs, nObjs, nDivsMax, nLevelIncrease, fUseXor, fUseZeroCost, fDebug, fVerbose ); *ppArray = NULL; while ( (iNode = Abc_ResubNodeToTry(&p->vTried, p->nPis+1, p->iFirstPo)) > 0 ) { int nDivs = Gia_Rsb2ManDivs( p, iNode ); int * pResub, nResub = Abc_ResubComputeFunction( Vec_PtrArray(&p->vpDivs), nDivs, 1, p->nMffc-1, nDivsMax, 0, fUseXor, fDebug, fVerbose, &pResub ); if ( nResub == 0 ) Vec_IntPush( &p->vTried, iNode ); else { int i, k = 0, iTried; Vec_Int_t vResub = { nResub, nResub, pResub }; Vec_Int_t * vRes = Gia_Rsb2ManInsert( p->nPis, p->nPos, &p->vObjs, iNode, &vResub, &p->vDivs, &p->vCopies ); //printf( "\nResubing node %d:\n", iNode ); //Gia_Rsb2ManPrint( p ); p->nObjs = Vec_IntSize(vRes)/2; p->iFirstPo = p->nObjs - p->nPos; Vec_IntClear( &p->vObjs ); Vec_IntAppend( &p->vObjs, vRes ); Vec_IntFree( vRes ); Vec_IntForEachEntry( &p->vTried, iTried, i ) if ( Vec_IntEntry(&p->vCopies, iTried) > Abc_Var2Lit(p->nPis, 0) ) // internal node Vec_IntWriteEntry( &p->vTried, k++, Abc_Lit2Var(Vec_IntEntry(&p->vCopies, iTried)) ); Vec_IntShrink( &p->vTried, k ); nChanges++; //Gia_Rsb2ManPrint( p ); } } if ( nChanges ) { RetValue = p->nObjs; *ppArray = p->vObjs.pArray; Vec_IntZero( &p->vObjs ); } Gia_Rsb2ManFree( p ); if ( pnResubs ) *pnResubs = nChanges; return RetValue; } int Abc_ResubComputeWindow2( int * pObjs, int nObjs, int nDivsMax, int nLevelIncrease, int fUseXor, int fUseZeroCost, int fDebug, int fVerbose, int ** ppArray, int * pnResubs ) { *ppArray = ABC_ALLOC( int, 2*nObjs ); memmove( *ppArray, pObjs, 2*nObjs * sizeof(int) ); if ( pnResubs ) *pnResubs = 0; return nObjs; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int * Gia_ManToResub( Gia_Man_t * p ) { Gia_Obj_t * pObj; int i, * pObjs = ABC_CALLOC( int, 2*Gia_ManObjNum(p) ); assert( Gia_ManIsNormalized(p) ); Gia_ManForEachObj1( p, pObj, i ) { if ( Gia_ObjIsCi(pObj) ) continue; pObjs[2*i+0] = Gia_ObjFaninLit0(Gia_ManObj(p, i), i); if ( Gia_ObjIsCo(pObj) ) pObjs[2*i+1] = pObjs[2*i+0]; else if ( Gia_ObjIsAnd(pObj) ) pObjs[2*i+1] = Gia_ObjFaninLit1(Gia_ManObj(p, i), i); else assert( 0 ); } return pObjs; } Gia_Man_t * Gia_ManFromResub( int * pObjs, int nObjs, int nIns ) { Gia_Man_t * pNew = Gia_ManStart( nObjs ); int i; for ( i = 1; i < nObjs; i++ ) { if ( pObjs[2*i] == 0 && i <= nIns ) // pi Gia_ManAppendCi( pNew ); else if ( pObjs[2*i] == pObjs[2*i+1] ) // po Gia_ManAppendCo( pNew, pObjs[2*i] ); else if ( pObjs[2*i] < pObjs[2*i+1] ) Gia_ManAppendAnd( pNew, pObjs[2*i], pObjs[2*i+1] ); else if ( pObjs[2*i] > pObjs[2*i+1] ) Gia_ManAppendXor( pNew, pObjs[2*i], pObjs[2*i+1] ); else assert( 0 ); } return pNew; } Gia_Man_t * Gia_ManResub2Test( Gia_Man_t * p ) { Gia_Man_t * pNew; int nResubs, nObjsNew, * pObjsNew, * pObjs = Gia_ManToResub( p ); //Gia_ManPrint( p ); Abc_ResubPrepareManager( 1 ); nObjsNew = Abc_ResubComputeWindow( pObjs, Gia_ManObjNum(p), 1000, -1, 0, 0, 0, 0, &pObjsNew, &nResubs ); //printf( "Performed resub %d times. Reduced %d nodes.\n", nResubs, nObjsNew ? Gia_ManObjNum(p) - nObjsNew : 0 ); Abc_ResubPrepareManager( 0 ); if ( nObjsNew ) { pNew = Gia_ManFromResub( pObjsNew, nObjsNew, Gia_ManCiNum(p) ); pNew->pName = Abc_UtilStrsav( p->pName ); } else pNew = Gia_ManDup( p ); ABC_FREE( pObjs ); ABC_FREE( pObjsNew ); return pNew; } /**Function************************************************************* Synopsis [Creating a window with support composed of primary inputs.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ // returns the number of nodes added to the window when is iPivot is added // the window nodes in vNodes are labeled with the current traversal ID // the new node iPivot and its fanout are temporarily labeled and then unlabeled int Gia_WinTryAddingNode( Gia_Man_t * p, int iPivot, int iPivot2, Vec_Wec_t * vLevels, Vec_Int_t * vNodes ) { Vec_Int_t * vLevel; Gia_Obj_t * pObj, * pFanout; int k, i, f, Count = 0; // precondition: the levelized structure is empty assert( Vec_WecSizeSize(vLevels) == 0 ); // precondition: the new object to be added (iPivot) is not in the window assert( !Gia_ObjIsTravIdCurrentId(p, iPivot) ); // add the object to the window and to the levelized structure Gia_ObjSetTravIdCurrentId( p, iPivot ); Vec_WecPush( vLevels, Gia_ObjLevelId(p, iPivot), iPivot ); // the same about the second node if it is given if ( iPivot2 != -1 ) { // precondition: the new object to be added (iPivot2) is not in the window assert( !Gia_ObjIsTravIdCurrentId(p, iPivot2) ); // add the object to the window and to the levelized structure Gia_ObjSetTravIdCurrentId( p, iPivot2 ); Vec_WecPush( vLevels, Gia_ObjLevelId(p, iPivot2), iPivot2 ); } // iterate through all objects and explore their fanouts Vec_WecForEachLevel( vLevels, vLevel, k ) Gia_ManForEachObjVec( vLevel, p, pObj, i ) Gia_ObjForEachFanoutStatic( p, pObj, pFanout, f ) { if ( f == 5 ) // explore first 5 fanouts of the node break; if ( Gia_ObjIsAnd(pFanout) && // internal node !Gia_ObjIsTravIdCurrent(p, pFanout) && // not in the window Gia_ObjIsTravIdCurrent(p, Gia_ObjFanin0(pFanout)) && // but fanins are Gia_ObjIsTravIdCurrent(p, Gia_ObjFanin1(pFanout)) ) // in the window { // add fanout to the window and to the levelized structure Gia_ObjSetTravIdCurrent( p, pFanout ); Vec_WecPush( vLevels, Gia_ObjLevel(p, pFanout), Gia_ObjId(p, pFanout) ); // count the number of nodes in the structure Count++; } } // iterate through the nodes in the levelized structure Vec_WecForEachLevel( vLevels, vLevel, k ) { Gia_ManForEachObjVec( vLevel, p, pObj, i ) if ( vNodes == NULL ) // it was a test run - unmark the node Gia_ObjSetTravIdPrevious( p, pObj ); else // it was a real run - permanently add to the node to the window Vec_IntPush( vNodes, Gia_ObjId(p, pObj) ); // clean the levelized structure Vec_IntClear( vLevel ); } // return the number of nodes to be added return Count; } // find the first PI to add based on the fanout count int Gia_WinAddCiWithMaxFanouts( Gia_Man_t * p ) { int i, Id, nMaxFan = -1, iMaxFan = -1; Gia_ManForEachCiId( p, Id, i ) if ( nMaxFan < Gia_ObjFanoutNumId(p, Id) ) { nMaxFan = Gia_ObjFanoutNumId(p, Id); iMaxFan = Id; } assert( iMaxFan >= 0 ); return iMaxFan; } // find the next PI to add based on how many nodes will be added to the window int Gia_WinAddCiWithMaxDivisors( Gia_Man_t * p, Vec_Wec_t * vLevels ) { int i, Id, nCurFan, nMaxFan = -1, iMaxFan = -1; Gia_ManForEachCiId( p, Id, i ) { if ( Gia_ObjIsTravIdCurrentId( p, Id ) ) continue; nCurFan = Gia_WinTryAddingNode( p, Id, -1, vLevels, NULL ); if ( nMaxFan < nCurFan ) { nMaxFan = nCurFan; iMaxFan = Id; } } assert( iMaxFan >= 0 ); return iMaxFan; } // check if the node has unmarked fanouts int Gia_WinNodeHasUnmarkedFanouts( Gia_Man_t * p, int iPivot ) { int f, iFan; Gia_ObjForEachFanoutStaticId( p, iPivot, iFan, f ) if ( !Gia_ObjIsTravIdCurrentId(p, iFan) ) return 1; return 0; } // this is a translation procedure, which converts the array of node IDs (vObjs) // into the internal represnetation for the resub engine, which is returned // (this procedure is not needed when we simply construct a window) Vec_Int_t * Gia_RsbCiTranslate( Gia_Man_t * p, Vec_Int_t * vObjs, Vec_Int_t * vMap ) { int i, iObj, Lit0, Lit1, Fan0, Fan1; Vec_Int_t * vNodes = Vec_IntAlloc( 100 ); assert( Vec_IntSize(vMap) == Gia_ManObjNum(p) ); Vec_IntPushTwo( vNodes, 0, 0 ); // const0 node Vec_IntForEachEntry( vObjs, iObj, i ) { Gia_Obj_t * pObj = Gia_ManObj(p, iObj); assert( Gia_ObjIsTravIdCurrentId(p, iObj) ); Fan0 = Gia_ObjIsCi(pObj) ? 0 : Vec_IntEntry(vMap, Gia_ObjFaninId0(pObj, iObj)); Fan1 = Gia_ObjIsCi(pObj) ? 0 : Vec_IntEntry(vMap, Gia_ObjFaninId1(pObj, iObj)); Lit0 = Gia_ObjIsCi(pObj) ? 0 : Abc_LitNotCond( Fan0, Gia_ObjFaninC0(pObj) ); Lit1 = Gia_ObjIsCi(pObj) ? 0 : Abc_LitNotCond( Fan1, Gia_ObjFaninC1(pObj) ); Vec_IntWriteEntry( vMap, iObj, Vec_IntSize(vNodes) ); Vec_IntPushTwo( vNodes, Lit0, Lit1 ); } Vec_IntForEachEntry( vObjs, iObj, i ) if ( Gia_WinNodeHasUnmarkedFanouts( p, iObj ) ) Vec_IntPushTwo( vNodes, Vec_IntEntry(vMap, iObj), Vec_IntEntry(vMap, iObj) ); return vNodes; } // construct a high-volume window support by the given number (nPis) of primary inputs Vec_Int_t * Gia_RsbCiWindow( Gia_Man_t * p, int nPis ) { Vec_Int_t * vRes; int i, iMaxFan; Vec_Int_t * vNodes = Vec_IntAlloc( 100 ); Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) ); Vec_Wec_t * vLevels = Vec_WecStart( Gia_ManLevelNum(p)+1 ); Gia_ManStaticFanoutStart( p ); Gia_ManIncrementTravId(p); // add the first one iMaxFan = Gia_WinAddCiWithMaxFanouts( p ); Gia_ObjSetTravIdCurrentId( p, iMaxFan ); Vec_IntPush( vNodes, iMaxFan ); // add remaining ones for ( i = 1; i < nPis; i++ ) { iMaxFan = Gia_WinAddCiWithMaxDivisors( p, vLevels ); Gia_WinTryAddingNode( p, iMaxFan, -1, vLevels, vNodes ); } Vec_IntSort( vNodes, 0 ); vRes = Gia_RsbCiTranslate( p, vNodes, vMap ); Gia_ManStaticFanoutStop( p ); Vec_WecFree( vLevels ); Vec_IntFree( vMap ); //Vec_IntPrint( vNodes ); Vec_IntFree( vNodes ); return vRes; } void Gia_RsbCiWindowTest( Gia_Man_t * p ) { Vec_Int_t * vWin = Gia_RsbCiWindow( p, 6 ); //Vec_IntPrint( vWin ); Vec_IntFree( vWin ); } /**Function************************************************************* Synopsis [Return initial window for the given node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ //static inline int Gia_ObjFaninId( Gia_Obj_t * pObj, int iObj, int n ) { return n ? Gia_ObjFaninId1(pObj, iObj) : Gia_ObjFaninId0(pObj, iObj); } static inline int Gia_ObjTravIsTopTwo( Gia_Man_t * p, int iNodeA ) { return (p->pTravIds[iNodeA] >= p->nTravIds - 1); } static inline int Gia_ObjTravIsSame( Gia_Man_t * p, int iNodeA, int iNodeB ) { return (p->pTravIds[iNodeA] == p->pTravIds[iNodeB]); } static inline void Gia_ObjTravSetSame( Gia_Man_t * p, int iNodeA, int iNodeB ) { p->pTravIds[iNodeA] = p->pTravIds[iNodeB]; } // collect nodes on the path from the meeting point to the root node, excluding the meeting point void Gia_RsbWindowGather( Gia_Man_t * p, Vec_Int_t * vPaths, int iNode, Vec_Int_t * vVisited ) { int iPrev; if ( iNode == 0 ) return; Vec_IntPush( vVisited, iNode ); iPrev = Vec_IntEntry( vPaths, iNode ); if ( iPrev == 0 ) return; assert( Gia_ObjTravIsSame(p, iPrev, iNode) ); Gia_RsbWindowGather( p, vPaths, iPrev, vVisited ); } // explore the frontier of nodes in the breadth-first traversal int Gia_RsbWindowExplore( Gia_Man_t * p, Vec_Int_t * vVisited, int iStart, Vec_Int_t * vPaths, int * piMeet, int * piNode ) { int i, n, iObj, iLimit = Vec_IntSize( vVisited ); *piMeet = *piNode = 0; Vec_IntForEachEntryStartStop( vVisited, iObj, i, iStart, iLimit ) { Gia_Obj_t * pObj = Gia_ManObj( p, iObj ); if ( !Gia_ObjIsAnd(pObj) ) continue; for ( n = 0; n < 2; n++ ) { int iFan = Gia_ObjFaninId( pObj, iObj, n ); // if the node was visited on the paths to both fanins, collect it if ( Gia_ObjTravIsTopTwo(p, iObj) && Gia_ObjTravIsTopTwo(p, iFan) && !Gia_ObjTravIsSame(p, iObj, iFan) ) { *piMeet = iFan; *piNode = iObj; return 1; } // if the node was visited already on this path, skip it if ( Gia_ObjTravIsTopTwo(p, iFan) ) { assert( Gia_ObjTravIsSame(p, iObj, iFan) ); continue; } // label the node as visited Gia_ObjTravSetSame( p, iFan, iObj ); Vec_IntWriteEntry( vPaths, iFan, iObj ); Vec_IntPush( vVisited, iFan ); } } return 0; } Vec_Int_t * Gia_RsbWindowInit( Gia_Man_t * p, Vec_Int_t * vPaths, int iPivot, int nIter ) { Vec_Int_t * vVisited = Vec_IntAlloc( 100 ); Gia_Obj_t * pPivot = Gia_ManObj( p, iPivot ); int i, n, iStart = 0; assert( Gia_ObjIsAnd(pPivot) ); // start paths for both fanins of the pivot node for ( n = 0; n < 2; n++ ) { int iFan = Gia_ObjFaninId( pPivot, iPivot, n ); Gia_ManIncrementTravId(p); Vec_IntPush( vVisited, iFan ); Vec_IntWriteEntry( vPaths, iFan, 0 ); Gia_ObjSetTravIdCurrentId( p, iFan ); } // perform several iterations of breadth-first search for ( i = 0; i < nIter; i++ ) { int iMeet, iNode, iNext = Vec_IntSize(vVisited); if ( Gia_RsbWindowExplore( p, vVisited, iStart, vPaths, &iMeet, &iNode ) ) { // found the shared path if ( Gia_ObjIsTravIdCurrentId(p, iMeet) ) assert( Gia_ObjIsTravIdPreviousId(p, iNode) ); else if ( Gia_ObjIsTravIdPreviousId(p, iMeet) ) assert( Gia_ObjIsTravIdCurrentId(p, iNode) ); else assert( 0 ); // collect the initial window Vec_IntClear( vVisited ); Gia_RsbWindowGather( p, vPaths, Vec_IntEntry(vPaths, iMeet), vVisited ); Gia_RsbWindowGather( p, vPaths, iNode, vVisited ); Vec_IntPush( vVisited, iPivot ); break; } iStart = iNext; } // if no meeting point is found, make sure to return NULL if ( i == nIter ) Vec_IntFreeP( &vVisited ); return vVisited; } Vec_Int_t * Gia_RsbCreateWindowInputs( Gia_Man_t * p, Vec_Int_t * vWin ) { Vec_Int_t * vInputs = Vec_IntAlloc(10); Gia_Obj_t * pObj; int i, n, iObj; Gia_ManIncrementTravId(p); Gia_ManForEachObjVec( vWin, p, pObj, i ) Gia_ObjSetTravIdCurrent(p, pObj); Gia_ManForEachObjVec( vWin, p, pObj, i ) { assert( Gia_ObjIsAnd(pObj) ); for ( n = 0; n < 2; n++ ) { int iFan = n ? Gia_ObjFaninId1p(p, pObj) : Gia_ObjFaninId0p(p, pObj); if ( !Gia_ObjIsTravIdCurrentId(p, iFan) ) Vec_IntPushUnique( vInputs, iFan ); } } Vec_IntForEachEntry( vInputs, iObj, i ) { Gia_ObjSetTravIdCurrentId( p, iObj ); Vec_IntPush( vWin, iObj ); } return vInputs; } /**Function************************************************************* Synopsis [Grow window for the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Gia_RsbAddSideInputs( Gia_Man_t * p, Vec_Wec_t * vLevels, Vec_Int_t * vWin ) { Vec_Int_t * vLevel; Gia_Obj_t * pObj, * pFanout; int k, i, f, iObj; // precondition: the levelized structure is empty assert( Vec_WecSizeSize(vLevels) == 0 ); // precondition: window nodes are labeled with the current ID Vec_IntForEachEntry( vWin, iObj, i ) { assert( Gia_ObjIsTravIdCurrentId(p, iObj) ); Vec_WecPush( vLevels, Gia_ObjLevelId(p, iObj), iObj ); } // iterate through all objects and explore their fanouts Vec_WecForEachLevel( vLevels, vLevel, k ) Gia_ManForEachObjVec( vLevel, p, pObj, i ) Gia_ObjForEachFanoutStatic( p, pObj, pFanout, f ) { if ( f == 5 ) // explore first 5 fanouts of the node break; if ( Gia_ObjIsAnd(pFanout) && // internal node !Gia_ObjIsTravIdCurrent(p, pFanout) && // not in the window Gia_ObjIsTravIdCurrent(p, Gia_ObjFanin0(pFanout)) && // but fanins are Gia_ObjIsTravIdCurrent(p, Gia_ObjFanin1(pFanout)) ) // in the window { // add fanout to the window and to the levelized structure Gia_ObjSetTravIdCurrent( p, pFanout ); Vec_WecPush( vLevels, Gia_ObjLevel(p, pFanout), Gia_ObjId(p, pFanout) ); Vec_IntPush( vWin, Gia_ObjId(p, pFanout) ); } } // iterate through the nodes in the levelized structure Vec_WecForEachLevel( vLevels, vLevel, k ) Vec_IntClear( vLevel ); } // expland inputs until saturation while adding the side-fanouts void Gia_RsbExpandInputs( Gia_Man_t * p, Vec_Wec_t * vLevels, Vec_Int_t * vWin, Vec_Int_t * vInputs ) { Gia_Obj_t * pObj; int i, n, iFans[2], fChange = 1; while ( fChange ) { fChange = 0; Gia_ManForEachObjVec( vInputs, p, pObj, i ) { if ( !Gia_ObjIsAnd(pObj) ) continue; iFans[0] = Gia_ObjFaninId0p(p, pObj); iFans[1] = Gia_ObjFaninId1p(p, pObj); if ( !Gia_ObjIsTravIdCurrentId(p, iFans[0]) && !Gia_ObjIsTravIdCurrentId(p, iFans[1]) ) continue; Vec_IntRemove( vInputs, Gia_ObjId(p, pObj) ); assert( Vec_IntFind(vWin, Gia_ObjId(p, pObj)) >= 0 ); for ( n = 0; n < 2; n++ ) { if ( Gia_ObjIsTravIdCurrentId(p, iFans[n]) ) continue; assert( Vec_IntFind(vInputs, iFans[n]) == -1 ); Vec_IntPush( vInputs, iFans[n] ); Gia_WinTryAddingNode( p, iFans[n], -1, vLevels, vWin ); assert( Gia_ObjIsTravIdCurrentId(p, iFans[n]) ); } fChange = 1; } } } // select the best input to expand, based on its contribution to the window size int Gia_RsbSelectOneInput( Gia_Man_t * p, Vec_Wec_t * vLevels, Vec_Int_t * vIns ) { int i, iNode = 0, WeightThis, WeightBest = -1; Gia_Obj_t * pObj; Gia_ManForEachObjVec( vIns, p, pObj, i ) if ( Gia_ObjIsAnd(pObj) ) { int iFan0 = Gia_ObjFaninId0p(p, pObj); int iFan1 = Gia_ObjFaninId1p(p, pObj); assert( !Gia_ObjIsTravIdCurrentId(p, iFan0) && !Gia_ObjIsTravIdCurrentId(p, iFan1) ); WeightThis = Gia_WinTryAddingNode( p, iFan0, iFan1, vLevels, NULL ); if ( WeightBest < WeightThis ) { WeightBest = WeightThis; iNode = Gia_ObjId(p, pObj); } } return iNode; } // grow the initial window as long as it fits the input count limit void Gia_RsbWindowGrow( Gia_Man_t * p, Vec_Wec_t * vLevels, Vec_Int_t * vWin, Vec_Int_t * vIns, int nInputsMax ) { int iNode; Gia_RsbAddSideInputs( p, vLevels, vWin ); Gia_RsbExpandInputs( p, vLevels, vWin, vIns ); while ( Vec_IntSize(vIns) < nInputsMax && (iNode = Gia_RsbSelectOneInput(p, vLevels, vIns)) ) { int iFan0 = Gia_ObjFaninId0p(p, Gia_ManObj(p, iNode)); int iFan1 = Gia_ObjFaninId1p(p, Gia_ManObj(p, iNode)); assert( !Gia_ObjIsTravIdCurrentId(p, iFan0) && !Gia_ObjIsTravIdCurrentId(p, iFan1) ); Gia_WinTryAddingNode( p, iFan0, iFan1, vLevels, vWin ); assert( Gia_ObjIsTravIdCurrentId(p, iFan0) && Gia_ObjIsTravIdCurrentId(p, iFan1) ); Vec_IntRemove( vIns, iNode ); Vec_IntPushTwo( vIns, iFan0, iFan1 ); Gia_RsbExpandInputs( p, vLevels, vWin, vIns ); } } /**Function************************************************************* Synopsis [Grow window for the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Gia_WinCreateFromCut_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vWin ) { Gia_Obj_t * pObj; if ( Gia_ObjIsTravIdCurrentId(p, iObj) ) return; Gia_ObjSetTravIdCurrentId(p, iObj); pObj = Gia_ManObj( p, iObj ); assert( Gia_ObjIsAnd(pObj) ); Gia_WinCreateFromCut_rec( p, Gia_ObjFaninId0(pObj, iObj), vWin ); Gia_WinCreateFromCut_rec( p, Gia_ObjFaninId1(pObj, iObj), vWin ); Vec_IntPush( vWin, iObj ); } // uses levelized structure (vLevels) to collect in array vWin divisors supported by the cut (vIn) void Gia_WinCreateFromCut( Gia_Man_t * p, int iPivot, Vec_Int_t * vIn, Vec_Wec_t * vLevels, Vec_Int_t * vWin ) { Vec_Int_t * vLevel; Gia_Obj_t * pObj, * pFanout; int k, i, f, iObj, Level; Vec_Int_t * vUsed = Vec_IntAlloc( 100 ); // precondition: the levelized structure is empty assert( Vec_WecSizeSize(vLevels) == 0 ); // clean the resulting array Vec_IntClear( vWin ); // collect leaves Gia_ManIncrementTravId( p ); Vec_IntForEachEntry( vIn, iObj, i ) { Gia_ObjSetTravIdCurrentId( p, iObj ); Vec_IntPush( vWin, iObj ); } // collect internal cone Gia_WinCreateFromCut_rec( p, iPivot, vWin ); // add nodes to the levelized structure Vec_IntForEachEntry( vWin, iObj, i ) { Vec_WecPush( vLevels, Gia_ObjLevelId(p, iObj), iObj ); Vec_IntPushUniqueOrder( vUsed, Gia_ObjLevelId(p, iObj) ); } // iterate through all objects and explore their fanouts //Vec_WecForEachLevel( vLevels, vLevel, k ) Vec_IntForEachEntry( vUsed, Level, k ) { vLevel = Vec_WecEntry( vLevels, Level ); Gia_ManForEachObjVec( vLevel, p, pObj, i ) Gia_ObjForEachFanoutStatic( p, pObj, pFanout, f ) { if ( f == 5 ) // explore first 5 fanouts of the node break; if ( Gia_ObjIsAnd(pFanout) && // internal node !Gia_ObjIsTravIdCurrent(p, pFanout) && // not in the window Gia_ObjIsTravIdCurrent(p, Gia_ObjFanin0(pFanout)) && // but fanins are Gia_ObjIsTravIdCurrent(p, Gia_ObjFanin1(pFanout)) ) // in the window { // add fanout to the window and to the levelized structure Gia_ObjSetTravIdCurrent( p, pFanout ); Vec_WecPush( vLevels, Gia_ObjLevel(p, pFanout), Gia_ObjId(p, pFanout) ); Vec_IntPush( vWin, Gia_ObjId(p, pFanout) ); Vec_IntPushUniqueOrder( vUsed, Gia_ObjLevel(p, pFanout) ); } } Vec_IntClear( vLevel ); } Vec_IntSort( vWin, 0 ); Vec_IntFree( vUsed ); } // update the cut until both fanins of AND nodes are not in the cut int Gia_RsbExpandCut( Gia_Man_t * p, Vec_Int_t * vIns ) { int fOnlyPis = 0, fChange = 1, nSize = Vec_IntSize(vIns); while ( fChange ) { Gia_Obj_t * pObj; int i, iFan0, iFan1, fHave0, fHave1; fOnlyPis = 1; fChange = 0; // check if some nodes can be expanded without increasing cut size Gia_ManForEachObjVec( vIns, p, pObj, i ) { assert( Gia_ObjIsTravIdCurrent(p, pObj) ); if ( !Gia_ObjIsAnd(pObj) ) continue; fOnlyPis = 0; iFan0 = Gia_ObjFaninId0p(p, pObj); iFan1 = Gia_ObjFaninId1p(p, pObj); fHave0 = Gia_ObjIsTravIdCurrentId(p, iFan0); fHave1 = Gia_ObjIsTravIdCurrentId(p, iFan1); if ( !fHave0 && !fHave1 ) continue; // can expand because one of the fanins is already in the cut // remove current cut node Vec_IntDrop( vIns, i ); // add missing fanin if ( !fHave0 ) { Vec_IntPush( vIns, iFan0 ); Gia_ObjSetTravIdCurrentId( p, iFan0 ); } if ( !fHave1 ) { Vec_IntPush( vIns, iFan1 ); Gia_ObjSetTravIdCurrentId( p, iFan1 ); } fChange = 1; break; } } assert( Vec_IntSize(vIns) <= nSize ); return fOnlyPis; } int Gia_RsbFindFaninAdd( int iFan, int pFanins[32], int pFaninCounts[32], int nFanins ) { int i; for ( i = 0; i < nFanins; i++ ) if ( pFanins[i] == iFan ) break; pFanins[i] = iFan; pFaninCounts[i]++; return nFanins + (i == nFanins); } int Gia_RsbFindFaninToAddToCut( Gia_Man_t * p, Vec_Int_t * vIns ) { Gia_Obj_t * pObj; int nFanins = 0, pFanins[64] = {0}, pFaninCounts[64] = {0}; int i, iFan0, iFan1, iFanMax = -1, CountMax = 0; Gia_ManForEachObjVec( vIns, p, pObj, i ) { if ( !Gia_ObjIsAnd(pObj) ) continue; iFan0 = Gia_ObjFaninId0p(p, pObj); iFan1 = Gia_ObjFaninId1p(p, pObj); assert( !Gia_ObjIsTravIdCurrentId(p, iFan0) ); assert( !Gia_ObjIsTravIdCurrentId(p, iFan1) ); nFanins = Gia_RsbFindFaninAdd( iFan0, pFanins, pFaninCounts, nFanins ); nFanins = Gia_RsbFindFaninAdd( iFan1, pFanins, pFaninCounts, nFanins ); assert( nFanins < 64 ); } // find fanin with the highest count if ( p->vFanoutNums != NULL ) { for ( i = 0; i < nFanins; i++ ) if ( CountMax < pFaninCounts[i] || (CountMax == pFaninCounts[i] && (Gia_ObjFanoutNumId(p, iFanMax) < Gia_ObjFanoutNumId(p, pFanins[i]))) ) { CountMax = pFaninCounts[i]; iFanMax = pFanins[i]; } } else { for ( i = 0; i < nFanins; i++ ) if ( CountMax < pFaninCounts[i] || (CountMax == pFaninCounts[i] && (Gia_ObjRefNumId(p, iFanMax) < Gia_ObjRefNumId(p, pFanins[i]))) ) { CountMax = pFaninCounts[i]; iFanMax = pFanins[i]; } } return iFanMax; } // precondition: nodes in vWin and in vIns are marked with the current ID void Gia_RsbWindowGrow2( Gia_Man_t * p, int iObj, Vec_Wec_t * vLevels, Vec_Int_t * vWin, Vec_Int_t * vIns, int nInputsMax ) { // window will be recomputed later Vec_IntClear( vWin ); // expand the cut without increasing its cost if ( !Gia_RsbExpandCut( p, vIns ) ) { // save it as the best cut Vec_Int_t * vBest = Vec_IntSize(vIns) <= nInputsMax ? Vec_IntDup(vIns) : NULL; int fOnlyPis = 0, Iter = 0; // iterate expansion until // (1) the cut cannot be expanded because all leaves are PIs // (2) the cut size exceeded the limit for 5 consecutive iterations while ( !fOnlyPis && (Vec_IntSize(vIns) <= nInputsMax || Iter < 5) ) { int iFanBest = Gia_RsbFindFaninToAddToCut( p, vIns ); Vec_IntPush( vIns, iFanBest ); Gia_ObjSetTravIdCurrentId( p, iFanBest ); fOnlyPis = Gia_RsbExpandCut( p, vIns ); if ( Vec_IntSize(vIns) > nInputsMax ) Iter++; else Iter = 0; if ( Vec_IntSize(vIns) <= nInputsMax && (!vBest || Vec_IntSize(vBest) <= Vec_IntSize(vIns)) ) { if ( vBest ) Vec_IntClear(vBest); else vBest = Vec_IntAlloc( 10 ); Vec_IntAppend( vBest, vIns ); } } if ( vBest ) { Vec_IntClear( vIns ); Vec_IntAppend( vIns, vBest ); Vec_IntFree( vBest ); } else assert( Vec_IntSize(vIns) > nInputsMax ); } if ( vLevels && Vec_IntSize(vIns) <= nInputsMax ) { Vec_IntSort( vIns, 0 ); Gia_WinCreateFromCut( p, iObj, vIns, vLevels, vWin ); } } /**Function************************************************************* Synopsis [Create window for the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Gia_RsbWindowCompute( Gia_Man_t * p, int iObj, int nInputsMax, int nLevelsMax, Vec_Wec_t * vLevels, Vec_Int_t * vPaths, Vec_Int_t ** pvWin, Vec_Int_t ** pvIns ) { Vec_Int_t * vWin, * vIns; *pvWin = *pvIns = NULL; vWin = Gia_RsbWindowInit( p, vPaths, iObj, nLevelsMax ); if ( vWin == NULL ) return 0; vIns = Gia_RsbCreateWindowInputs( p, vWin ); // vWin and vIns are labeled with the current trav ID //Vec_IntPrint( vWin ); //Vec_IntPrint( vIns ); if ( Vec_IntSize(vIns) <= nInputsMax + 3 ) // consider windows, which initially has a larger input space Gia_RsbWindowGrow2( p, iObj, vLevels, vWin, vIns, nInputsMax ); if ( Vec_IntSize(vIns) <= nInputsMax ) { Vec_IntSort( vWin, 0 ); Vec_IntSort( vIns, 0 ); *pvWin = vWin; *pvIns = vIns; return 1; } else { Vec_IntFree( vWin ); Vec_IntFree( vIns ); return 0; } } /**Function************************************************************* Synopsis [Derive GIA from the window] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Int_t * Gia_RsbFindOutputs( Gia_Man_t * p, Vec_Int_t * vWin, Vec_Int_t * vIns, Vec_Int_t * vRefs ) { Vec_Int_t * vOuts = Vec_IntAlloc( 100 ); Gia_Obj_t * pObj; int i; Gia_ManIncrementTravId( p ); Gia_ManForEachObjVec( vIns, p, pObj, i ) Gia_ObjSetTravIdCurrent( p, pObj ); Gia_ManForEachObjVec( vWin, p, pObj, i ) if ( !Gia_ObjIsTravIdCurrent(p, pObj) && Gia_ObjIsAnd(pObj) ) { Vec_IntAddToEntry( vRefs, Gia_ObjFaninId0p(p, pObj), 1 ); Vec_IntAddToEntry( vRefs, Gia_ObjFaninId1p(p, pObj), 1 ); } Gia_ManForEachObjVec( vWin, p, pObj, i ) if ( !Gia_ObjIsTravIdCurrent(p, pObj) && Gia_ObjFanoutNum(p, pObj) != Vec_IntEntry(vRefs, Gia_ObjId(p, pObj)) ) Vec_IntPush( vOuts, Gia_ObjId(p, pObj) ); Gia_ManForEachObjVec( vWin, p, pObj, i ) if ( !Gia_ObjIsTravIdCurrent(p, pObj) && Gia_ObjIsAnd(pObj) ) { Vec_IntAddToEntry( vRefs, Gia_ObjFaninId0p(p, pObj), -1 ); Vec_IntAddToEntry( vRefs, Gia_ObjFaninId1p(p, pObj), -1 ); } return vOuts; } Gia_Man_t * Gia_RsbDeriveGiaFromWindows( Gia_Man_t * p, Vec_Int_t * vWin, Vec_Int_t * vIns, Vec_Int_t * vOuts ) { Gia_Man_t * pNew; Gia_Obj_t * pObj; int i; pNew = Gia_ManStart( Gia_ManObjNum(p) ); pNew->pName = Abc_UtilStrsav( p->pName ); pNew->pSpec = Abc_UtilStrsav( p->pSpec ); Gia_ManHashAlloc( pNew ); Gia_ManFillValue( p ); Gia_ManConst0(p)->Value = 0; Gia_ManForEachObjVec( vIns, p, pObj, i ) pObj->Value = Gia_ManAppendCi( pNew ); Gia_ManForEachObjVec( vWin, p, pObj, i ) if ( !~pObj->Value ) pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); Gia_ManForEachObjVec( vOuts, p, pObj, i ) Gia_ManAppendCo( pNew, pObj->Value ); Gia_ManHashStop( pNew ); return pNew; } /**Function************************************************************* Synopsis [Naive truth-table-based verification.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ word Gia_LutComputeTruth66_rec( Gia_Man_t * p, Gia_Obj_t * pObj ) { word Truth0, Truth1; if ( Gia_ObjIsCi(pObj) ) return s_Truths6[Gia_ObjCioId(pObj)]; if ( Gia_ObjIsConst0(pObj) ) return 0; assert( Gia_ObjIsAnd(pObj) ); Truth0 = Gia_LutComputeTruth66_rec( p, Gia_ObjFanin0(pObj) ); Truth1 = Gia_LutComputeTruth66_rec( p, Gia_ObjFanin1(pObj) ); if ( Gia_ObjFaninC0(pObj) ) Truth0 = ~Truth0; if ( Gia_ObjFaninC1(pObj) ) Truth1 = ~Truth1; return Truth0 & Truth1; } int Gia_ManVerifyTwoTruths( Gia_Man_t * p1, Gia_Man_t * p2 ) { int i, fFailed = 0; assert( Gia_ManCoNum(p1) == Gia_ManCoNum(p2) ); for ( i = 0; i < Gia_ManCoNum(p1); i++ ) { Gia_Obj_t * pPo1 = Gia_ManCo(p1, i); Gia_Obj_t * pPo2 = Gia_ManCo(p2, i); word word1 = Gia_LutComputeTruth66_rec( p1, Gia_ObjFanin0(pPo1) ); word word2 = Gia_LutComputeTruth66_rec( p2, Gia_ObjFanin0(pPo2) ); if ( Gia_ObjFaninC0(pPo1) ) word1 = ~word1; if ( Gia_ObjFaninC0(pPo2) ) word2 = ~word2; if ( word1 != word2 ) { //Dau_DsdPrintFromTruth( &word1, 6 ); //Dau_DsdPrintFromTruth( &word2, 6 ); printf( "Verification failed for output %d (out of %d).\n", i, Gia_ManCoNum(p1) ); fFailed = 1; } } // if ( !fFailed ) // printf( "Verification succeeded for %d outputs.\n", Gia_ManCoNum(p1) ); return !fFailed; } /**Function************************************************************* Synopsis [Enumerate windows of the nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Gia_RsbEnumerateWindows( Gia_Man_t * p, int nInputsMax, int nLevelsMax ) { int fVerbose = 0; int fUseHash = 0; int i, nWins = 0, nWinSize = 0, nInsSize = 0, nOutSize = 0, nNodeGain = 0; Vec_Wec_t * vLevels = Vec_WecStart( Gia_ManLevelNum(p)+1 ); Vec_Int_t * vPaths = Vec_IntStart( Gia_ManObjNum(p) ); Vec_Int_t * vRefs = Vec_IntStart( Gia_ManObjNum(p) ); Hsh_VecMan_t * pHash = Hsh_VecManStart( 1000 ); Gia_Obj_t * pObj; Gia_Man_t * pIn, * pOut; abctime clk = Abc_Clock(); Gia_ManStaticFanoutStart( p ); Gia_ManForEachAnd( p, pObj, i ) { Vec_Int_t * vWin, * vIns, * vOuts; if ( !Gia_RsbWindowCompute( p, i, nInputsMax, nLevelsMax, vLevels, vPaths, &vWin, &vIns ) ) continue; vOuts = Gia_RsbFindOutputs( p, vWin, vIns, vRefs ); nWins++; nWinSize += Vec_IntSize(vWin); nInsSize += Vec_IntSize(vIns); nOutSize += Vec_IntSize(vOuts); if ( fVerbose ) { printf( "\n\nObj %d\n", i ); Vec_IntPrint( vWin ); Vec_IntPrint( vIns ); Vec_IntPrint( vOuts ); printf( "\n" ); } else if ( Vec_IntSize(vWin) > 1000 ) printf( "Obj %d. Window: Ins = %d. Ands = %d. Outs = %d.\n", i, Vec_IntSize(vIns), Vec_IntSize(vWin)-Vec_IntSize(vIns), Vec_IntSize(vOuts) ); if ( fUseHash ) { int nEntries = Hsh_VecSize(pHash); Hsh_VecManAdd( pHash, vWin ); if ( nEntries == Hsh_VecSize(pHash) ) { Vec_IntFree( vWin ); Vec_IntFree( vIns ); Vec_IntFree( vOuts ); continue; } } pIn = Gia_RsbDeriveGiaFromWindows( p, vWin, vIns, vOuts ); pOut = Gia_ManResub2Test( pIn ); //pOut = Gia_ManDup( pIn ); if ( !Gia_ManVerifyTwoTruths( pIn, pOut ) ) { Gia_ManPrint( pIn ); Gia_ManPrint( pOut ); pOut = pOut; } nNodeGain += Gia_ManAndNum(pIn) - Gia_ManAndNum(pOut); Gia_ManStop( pIn ); Gia_ManStop( pOut ); Vec_IntFree( vWin ); Vec_IntFree( vIns ); Vec_IntFree( vOuts ); } Gia_ManStaticFanoutStop( p ); Vec_WecFree( vLevels ); Vec_IntFree( vPaths ); Vec_IntFree( vRefs ); printf( "Computed windows for %d nodes (out of %d). Unique = %d. Ave inputs = %.2f. Ave outputs = %.2f. Ave volume = %.2f. Gain = %d. ", nWins, Gia_ManAndNum(p), Hsh_VecSize(pHash), 1.0*nInsSize/Abc_MaxInt(1,nWins), 1.0*nOutSize/Abc_MaxInt(1,nWins), 1.0*nWinSize/Abc_MaxInt(1,nWins), nNodeGain ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); Hsh_VecManStop( pHash ); } /**Function************************************************************* Synopsis [Apply k-resub to one AIG.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Gia_Man_t * Gia_RsbTryOneWindow( Gia_Man_t * p ) { return Gia_ManResub2Test( p ); } /**Function************************************************************* Synopsis [Apply k-resub to one AIG.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Gia_RsbTestArray() { int Array[1000] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 3, 7, 15, 17, 8, 19, 5, 20, 5, 12, 8, 24, 4, 12, 9, 28, 27, 31, 23, 32, 4, 13, 8, 36, 5, 13, 18, 40, 9, 18, 5, 44, 19, 36, 9, 48, 47, 51, 10, 18, 40, 54, 8, 56, 25, 37, 44, 61, 59, 63, 8, 28, 8, 18, 25, 68, 66, 70, 64, 73, 11, 19, 8, 13, 76, 78, 10, 19, 40, 82, 9, 84, 81, 87, 20, 61, 19, 28, 30, 92, 91, 95, 88, 96, 74, 98, 9, 40, 49, 103, 27, 104, 10, 107, 8, 40, 9, 24, 111, 113, 11, 115, 109, 117, 11, 66, 51, 121, 118, 122, 18, 36, 18, 110, 93, 127, 10, 131, 129, 133, 11, 38, 32, 137, 103, 138, 19, 141, 134, 143, 28, 76, 9, 146, 11, 110, 19, 150, 149, 153, 87, 95, 9, 19, 10, 159, 61, 160, 18, 30, 61, 158, 9, 12, 25, 169, 19, 171, 111, 173, 10, 175, 167, 177, 18, 102, 4, 20, 18, 171, 183, 185, 11, 187, 181, 189, 178, 190, 24, 44, 11, 194, 8, 54, 4, 198, 197, 201, 45, 49, 10, 39, 9, 126, 73, 209, 11, 211, 54, 168, 213, 215, 43, 167, 67, 218, 10, 221, 26, 54, 18, 18, 34, 34, 38, 38, 40, 40, 42, 42, 52, 52, 100, 100, 124, 124, 126, 126, 144, 144, 148, 148, 154, 154, 156, 156, 162, 162, 164, 164, 192, 192, 70, 70, 202, 202, 204, 204, 206, 206, 216, 216, 222, 222, 224, 224 }; int i, iFan0, iFan1, nResubs; int * pRes; // create the internal array Vec_Int_t * vArray = Vec_IntAlloc( 100 ); for ( i = 0; i < 50 || Array[i] > 0; i++ ) Vec_IntPush( vArray, Array[i] ); Vec_IntPrint( vArray ); // check the nodes printf( "Constant0 and primary inputs:\n" ); Vec_IntForEachEntryDouble( vArray, iFan0, iFan1, i ) { if ( iFan0 != iFan1 ) break; printf( "%2d = %c%2d & %c%2d;\n", i, Abc_LitIsCompl(iFan0) ? '!' : ' ', Abc_Lit2Var(iFan0), Abc_LitIsCompl(iFan1) ? '!' : ' ', Abc_Lit2Var(iFan1) ); } printf( "Primary outputs:\n" ); Vec_IntForEachEntryDoubleStart( vArray, iFan0, iFan1, i, 14 ) { if ( iFan0 != iFan1 ) continue; printf( "%2d = %c%2d & %c%2d;\n", i, Abc_LitIsCompl(iFan0) ? '!' : ' ', Abc_Lit2Var(iFan0), Abc_LitIsCompl(iFan1) ? '!' : ' ', Abc_Lit2Var(iFan1) ); } // run the resub Abc_ResubPrepareManager( 1 ); Abc_ResubComputeWindow( Vec_IntArray(vArray), Vec_IntSize(vArray)/2, 10, -1, 0, 0, 1, 1, &pRes, &nResubs ); Abc_ResubPrepareManager( 0 ); Vec_IntFree( vArray ); } /**Function************************************************************* Synopsis [Computing cuts of the nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Wec_t * Gia_ManExtractCuts2( Gia_Man_t * p, int nCutSize, int nCuts, int fVerbose ) { int c, nLevelMax = 8; abctime clk = Abc_Clock(); Vec_Wec_t * vCuts = Vec_WecStart( nCuts ); Vec_Int_t * vPaths = Vec_IntStart( Gia_ManObjNum(p) ); srand( time(NULL) ); for ( c = 0; c < nCuts; ) { Vec_Int_t * vCut, * vWin = NULL; while ( vWin == NULL ) { int iPivot = 1 + Gia_ManCiNum(p) + rand() % Gia_ManAndNum(p); assert( Gia_ObjIsAnd(Gia_ManObj(p, iPivot)) ); vWin = Gia_RsbWindowInit( p, vPaths, iPivot, nLevelMax ); } vCut = Gia_RsbCreateWindowInputs( p, vWin ); if ( Vec_IntSize(vCut) >= nCutSize - 2 && Vec_IntSize(vCut) <= nCutSize ) { Vec_IntPush( Vec_WecEntry(vCuts, c), Vec_IntSize(vCut) ); Vec_IntAppend( Vec_WecEntry(vCuts, c++), vCut ); } Vec_IntFree( vCut ); Vec_IntFree( vWin ); } Vec_IntFree( vPaths ); Abc_PrintTime( 0, "Computing cuts ", Abc_Clock() - clk ); return vCuts; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END