From 8b160138f129387fba66e60009cbeef3b9559eb7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 11 Oct 2014 17:19:41 -0700 Subject: MUX decomposition during mapping. --- src/aig/gia/giaIf.c | 146 +++++++++++++++++++++++++++++++++++++++++++--------- src/map/if/ifMap.c | 1 - 2 files changed, 121 insertions(+), 26 deletions(-) (limited to 'src') diff --git a/src/aig/gia/giaIf.c b/src/aig/gia/giaIf.c index 6f93e0f9..3afb07b7 100644 --- a/src/aig/gia/giaIf.c +++ b/src/aig/gia/giaIf.c @@ -368,28 +368,50 @@ void Gia_ManPrintGetMuxFanins( Gia_Man_t * p, Gia_Obj_t * pObj, int * pFanins ) } int Gia_ManCountDupLut( Gia_Man_t * p ) { - int i, nCountDup = 0, nCountPis = 0, nCountMux = 0; + Gia_Obj_t * pObj, * pFanin; + int i, pFanins[3], nCountDup = 0, nCountPis = 0, nCountMux = 0; Gia_ManCleanMark01( p ); Gia_ManForEachLut( p, i ) if ( Gia_ObjLutIsMux(p, i) ) { - Gia_Obj_t * pFanin; - int pFanins[3]; - assert( Gia_ObjLutSize(p, i) == 2 || Gia_ObjLutSize(p, i) == 3 ); - Gia_ManPrintGetMuxFanins( p, Gia_ManObj(p, i), pFanins ); - Gia_ManObj(p, i)->fMark1 = 1; - - pFanin = Gia_ManObj(p, pFanins[1]); - nCountPis += Gia_ObjIsCi(pFanin); - nCountDup += pFanin->fMark0; - nCountMux += pFanin->fMark1; - pFanin->fMark0 = 1; - - pFanin = Gia_ManObj(p, pFanins[2]); - nCountPis += Gia_ObjIsCi(pFanin); - nCountDup += pFanin->fMark0; - nCountMux += pFanin->fMark1; - pFanin->fMark0 = 1; + pObj = Gia_ManObj( p, i ); + pObj->fMark1 = 1; + if ( Gia_ObjLutSize(p, i) == 3 ) + { + Gia_ManPrintGetMuxFanins( p, pObj, pFanins ); + + pFanin = Gia_ManObj(p, pFanins[1]); + nCountPis += Gia_ObjIsCi(pFanin); + nCountDup += pFanin->fMark0; + nCountMux += pFanin->fMark1; + pFanin->fMark0 = 1; + + pFanin = Gia_ManObj(p, pFanins[2]); + nCountPis += Gia_ObjIsCi(pFanin); + nCountDup += pFanin->fMark0; + nCountMux += pFanin->fMark1; + pFanin->fMark0 = 1; + } + else if ( Gia_ObjLutSize(p, i) == 2 ) + { + pFanin = Gia_ObjFanin0(pObj); + if ( pFanin->fMark0 || pFanin->fMark1 ) + { + pFanin = Gia_ObjFanin1(pObj); + nCountPis += Gia_ObjIsCi(pFanin); + nCountDup += pFanin->fMark0; + nCountMux += pFanin->fMark1; + pFanin->fMark0 = 1; + } + else + { + nCountPis += Gia_ObjIsCi(pFanin); + nCountDup += pFanin->fMark0; + nCountMux += pFanin->fMark1; + pFanin->fMark0 = 1; + } + } + else assert( 0 ); } Gia_ManCleanMark01( p ); if ( nCountDup + nCountPis + nCountMux ) @@ -411,14 +433,22 @@ void Gia_ManPrintMappingStats( Gia_Man_t * p, char * pDumpFile ) if ( Gia_ObjLutIsMux(p, i) ) { int pFanins[3]; - assert( Gia_ObjLutSize(p, i) == 2 || Gia_ObjLutSize(p, i) == 3 ); - Gia_ManPrintGetMuxFanins( p, Gia_ManObj(p, i), pFanins ); - pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[pFanins[0]]+1 ); - pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[pFanins[1]] ); - pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[pFanins[2]] ); + if ( Gia_ObjLutSize(p, i) == 3 ) + { + Gia_ManPrintGetMuxFanins( p, Gia_ManObj(p, i), pFanins ); + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[pFanins[0]]+1 ); + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[pFanins[1]] ); + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[pFanins[2]] ); + } + else if ( Gia_ObjLutSize(p, i) == 2 ) + { + pObj = Gia_ManObj( p, i ); + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[Gia_ObjFaninId0(pObj, i)] ); + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[Gia_ObjFaninId1(pObj, i)] ); + } LevelMax = Abc_MaxInt( LevelMax, pLevels[i] ); - nMuxF++; nFanins++; + nMuxF++; continue; } nLuts++; @@ -1530,7 +1560,9 @@ Gia_Man_t * Gia_ManFromIfLogic( If_Man_t * pIfMan ) { pCutBest = If_ObjCutBest( pIfObj ); // perform sorting of cut leaves by delay, so that the slowest pin drives the fastest input of the LUT - if ( !pIfMan->pPars->fUseTtPerm && !pIfMan->pPars->fDelayOpt && !pIfMan->pPars->fDelayOptLut && !pIfMan->pPars->fDsdBalance && !pIfMan->pPars->pLutStruct && !pIfMan->pPars->fUserRecLib && !pIfMan->pPars->nGateSize && !pIfMan->pPars->fEnableCheck75 && !pIfMan->pPars->fEnableCheck75u && !pIfMan->pPars->fEnableCheck07 ) + if ( !pIfMan->pPars->fUseTtPerm && !pIfMan->pPars->fDelayOpt && !pIfMan->pPars->fDelayOptLut && !pIfMan->pPars->fDsdBalance && + !pIfMan->pPars->pLutStruct && !pIfMan->pPars->fUserRecLib && !pIfMan->pPars->nGateSize && !pIfMan->pPars->fEnableCheck75 && + !pIfMan->pPars->fEnableCheck75u && !pIfMan->pPars->fEnableCheck07 && !pIfMan->pPars->fUseDsdTune && !pIfMan->pPars->fUseCofVars ) If_CutRotatePins( pIfMan, pCutBest ); // collect leaves of the best cut Vec_IntClear( vLeaves ); @@ -1562,6 +1594,70 @@ Gia_Man_t * Gia_ManFromIfLogic( If_Man_t * pIfMan ) pIfObj->iCopy = Gia_ManFromIfLogicFindCell( pIfMan, pNew, pHashed, pCutBest, pSat, vPiVars, vPoVars, pNtkCell, nLutMax, vLeaves, vLits, vCover, vMapping, vMapping2, vPacking ); pIfObj->iCopy = Abc_LitNotCond( pIfObj->iCopy, pCutBest->fCompl ); } + else if ( pIfMan->pPars->fUseCofVars && pIfMan->pPars->fDeriveLuts && (int)pCutBest->nLeaves > pIfMan->pPars->nLutSize/2 ) + { + word pTruthCof[128], * pTruth = If_CutTruthW(pIfMan, pCutBest); + int pVarsNew[16], nVarsNew, iLitCofs[3]; + int LutSize = pIfMan->pPars->nLutSize; + int nWords = Abc_Truth6WordNum(LutSize); + int truthId = Abc_Lit2Var(pCutBest->iCutFunc); + int nLeaves = pCutBest->nLeaves; + int c, iVar = Vec_StrEntry(pIfMan->vTtVars[nLeaves], truthId), iTemp; + assert( iVar >= 0 && iVar < nLeaves && LutSize <= 13 ); + for ( c = 0; c < 2; c++ ) + { + for ( k = 0; k < nLeaves; k++ ) + pVarsNew[k] = k; + if ( c ) + Abc_TtCofactor1p( pTruthCof, pTruth, nWords, iVar ); + else + Abc_TtCofactor0p( pTruthCof, pTruth, nWords, iVar ); + nVarsNew = Abc_TtMinBase( pTruthCof, pVarsNew, pCutBest->nLeaves, LutSize ); + // derive LUT + Vec_IntClear( vLeaves2 ); + for ( k = 0; k < nVarsNew; k++ ) + Vec_IntPush( vLeaves2, Vec_IntEntry(vLeaves, pVarsNew[k]) ); + iLitCofs[c] = Kit_TruthToGia( pNew, (unsigned *)pTruthCof, nVarsNew, vCover, vLeaves2, 0 ); + if ( nVarsNew < 2 ) + continue; + // create mapping + Vec_IntSetEntry( vMapping, Abc_Lit2Var(iLitCofs[c]), Vec_IntSize(vMapping2) ); + Vec_IntPush( vMapping2, Vec_IntSize(vLeaves2) ); + Vec_IntForEachEntry( vLeaves2, iTemp, k ) + Vec_IntPush( vMapping2, Abc_Lit2Var(iTemp) ); + Vec_IntPush( vMapping2, Abc_Lit2Var(iLitCofs[c]) ); + } + iLitCofs[2] = Vec_IntEntry(vLeaves, iVar); + // derive MUX + if ( iLitCofs[0] > 1 || iLitCofs[1] > 1 ) + { + pTruthCof[0] = ABC_CONST(0xCACACACACACACACA); + Vec_IntClear( vLeaves2 ); + Vec_IntPush( vLeaves2, iLitCofs[0] ); + Vec_IntPush( vLeaves2, iLitCofs[1] ); + Vec_IntPush( vLeaves2, iLitCofs[2] ); + pIfObj->iCopy = Kit_TruthToGia( pNew, (unsigned *)pTruthCof, Vec_IntSize(vLeaves2), vCover, vLeaves2, 0 ); + } + else + { + iLitCofs[0] = Abc_LitNot( Gia_ManAppendAnd2( pNew, iLitCofs[0], Abc_LitNot(iLitCofs[2]) ) ); + iLitCofs[1] = Abc_LitNot( Gia_ManAppendAnd2( pNew, iLitCofs[1], iLitCofs[2] ) ); + pIfObj->iCopy = Abc_LitNot( Gia_ManAppendAnd2( pNew, iLitCofs[0], iLitCofs[1] ) ); + // collect leaves + Vec_IntClear( vLeaves2 ); + for ( k = 0; k < 3; k++ ) + if ( iLitCofs[k] > 1 ) + Vec_IntPush( vLeaves2, iLitCofs[k] ); + assert( Vec_IntSize(vLeaves2) > 1 ); + } + // create mapping + Vec_IntSetEntry( vMapping, Abc_Lit2Var(pIfObj->iCopy), Vec_IntSize(vMapping2) ); + Vec_IntPush( vMapping2, Vec_IntSize(vLeaves2) ); + Vec_IntForEachEntry( vLeaves2, iTemp, k ) + Vec_IntPush( vMapping2, Abc_Lit2Var(iTemp) ); + Vec_IntPush( vMapping2, -Abc_Lit2Var(pIfObj->iCopy) ); + pIfObj->iCopy = Abc_LitNotCond( pIfObj->iCopy, pCutBest->fCompl ); + } else if ( (pIfMan->pPars->fDeriveLuts && pIfMan->pPars->fTruth) || pIfMan->pPars->fUseDsd || pIfMan->pPars->fUseTtPerm ) { word * pTruth = If_CutTruthW(pIfMan, pCutBest); diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 035ce966..e192c90e 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -272,7 +272,6 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep } else if ( p->pPars->fUseCofVars ) { - extern int Abc_TtCheckCondDepTest( word * pTruth, int nVars, int nSuppLim ); int iCofVar = -1, truthId = Abc_Lit2Var(pCut->iCutFunc); if ( truthId >= Vec_StrSize(p->vTtVars[pCut->nLeaves]) || Vec_StrEntry(p->vTtVars[pCut->nLeaves], truthId) == (char)-1 ) { -- cgit v1.2.3