From 80110cc3285ae29dc3d45a7647b58f6d721de073 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 11 Apr 2014 11:01:54 -0700 Subject: New feature to optimize delay during mapping. --- src/aig/gia/giaIf.c | 10 +++--- src/base/abci/abc.c | 4 +-- src/base/abci/abcIf.c | 2 +- src/map/if/if.h | 2 ++ src/map/if/ifDelay.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/map/if/ifDsd.c | 14 ++++---- src/map/if/ifMap.c | 8 +++-- src/map/if/ifTime.c | 5 +++ 8 files changed, 124 insertions(+), 15 deletions(-) diff --git a/src/aig/gia/giaIf.c b/src/aig/gia/giaIf.c index cb470e06..bdbffd23 100644 --- a/src/aig/gia/giaIf.c +++ b/src/aig/gia/giaIf.c @@ -1201,8 +1201,10 @@ int Gia_ManFromIfLogicFindLut( If_Man_t * pIfMan, Gia_Man_t * pNew, If_Cut_t * p } assert( If_DsdManSuppSize(pIfMan->pIfDsdMan, If_CutDsdLit(pIfMan, pCutBest)) == (int)pCutBest->nLeaves ); // find the bound set -// uSetOld = If_DsdManCheckXY( pIfMan->pIfDsdMan, If_CutDsdLit(pIfMan, pCutBest), nLutSize, 1, 0, 1, 0 ); - uSetOld = pCutBest->uMaskFunc; + if ( pIfMan->pPars->fDelayOptLut ) + uSetOld = pCutBest->uMaskFunc; + else + uSetOld = If_DsdManCheckXY( pIfMan->pIfDsdMan, If_CutDsdLit(pIfMan, pCutBest), nLutSize, 1, 0, 1, 0 ); // remap bound set uSetNew = 0; for ( k = 0; k < If_CutLeaveNum(pCutBest); k++ ) @@ -1300,7 +1302,7 @@ 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->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 ) If_CutRotatePins( pIfMan, pCutBest ); // collect leaves of the best cut Vec_IntClear( vLeaves ); @@ -1542,7 +1544,7 @@ Gia_Man_t * Gia_ManPerformMapping( Gia_Man_t * p, void * pp, int fNormalized ) If_Man_t * pIfMan; If_Par_t * pPars = (If_Par_t *)pp; // disable cut minimization when GIA strucure is needed - if ( !pPars->fDelayOpt && !pPars->fDsdBalance && !pPars->fUserRecLib && !pPars->fDeriveLuts && !pPars->fUseDsd && !pPars->fUseTtPerm ) + if ( !pPars->fDelayOpt && !pPars->fDelayOptLut && !pPars->fDsdBalance && !pPars->fUserRecLib && !pPars->fDeriveLuts && !pPars->fUseDsd && !pPars->fUseTtPerm ) pPars->fCutMin = 0; // reconstruct GIA according to the hierarchy manager diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 5031a185..862c5fbc 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -15102,7 +15102,7 @@ int Abc_CommandIf( Abc_Frame_t * pAbc, int argc, char ** argv ) Abc_Print( -1, "This feature only works for [6;16]-LUTs.\n" ); return 1; } - pPars->pFuncCell = If_CutPerformCheck16; + pPars->pFuncCell = pPars->fDelayOptLut ? NULL : If_CutPerformCheck16; pPars->fCutMin = 1; } @@ -29854,7 +29854,7 @@ int Abc_CommandAbc9If( Abc_Frame_t * pAbc, int argc, char ** argv ) Abc_Print( -1, "This feature only works for [6;16]-LUTs.\n" ); return 1; } - pPars->pFuncCell = If_CutPerformCheck16; + pPars->pFuncCell = pPars->fDelayOptLut ? NULL : If_CutPerformCheck16; pPars->fCutMin = 1; } diff --git a/src/base/abci/abcIf.c b/src/base/abci/abcIf.c index 3ddc9fe3..5bab925e 100644 --- a/src/base/abci/abcIf.c +++ b/src/base/abci/abcIf.c @@ -430,7 +430,7 @@ Abc_Obj_t * Abc_NodeFromIf_rec( Abc_Ntk_t * pNtkNew, If_Man_t * pIfMan, If_Obj_t pCutBest = If_ObjCutBest( pIfObj ); // printf( "%d 0x%02X %d\n", pCutBest->nLeaves, 0xff & *If_CutTruth(pCutBest), pIfMan->pPars->pFuncCost(pCutBest) ); // if ( pIfMan->pPars->pLutLib && pIfMan->pPars->pLutLib->fVarPinDelays ) - if ( !pIfMan->pPars->fUseTtPerm && !pIfMan->pPars->fDelayOpt && !pIfMan->pPars->fDsdBalance && !pIfMan->pPars->pLutStruct && !pIfMan->pPars->fUserRecLib && !pIfMan->pPars->nGateSize ) + if ( !pIfMan->pPars->fDelayOpt && !pIfMan->pPars->fDelayOptLut && !pIfMan->pPars->fDsdBalance && !pIfMan->pPars->fUseTtPerm && !pIfMan->pPars->pLutStruct && !pIfMan->pPars->fUserRecLib && !pIfMan->pPars->nGateSize ) If_CutRotatePins( pIfMan, pCutBest ); if ( pIfMan->pPars->fUseCnfs || pIfMan->pPars->fUseMv ) { diff --git a/src/map/if/if.h b/src/map/if/if.h index 7be9f145..8914b464 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -525,6 +525,8 @@ extern int If_CluCheckExt3( void * p, word * pTruth, int nVars, int extern int If_CutDelaySop( If_Man_t * p, If_Cut_t * pCut ); extern int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ); extern int If_CutSopBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm ); +extern int If_CutLutBalanceEval( If_Man_t * p, If_Cut_t * pCut ); +extern int If_CutLutBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm ); /*=== ifDsd.c =============================================================*/ extern If_DsdMan_t * If_DsdManAlloc( int nVars, int nLutSize ); extern void If_DsdManPrint( If_DsdMan_t * p, char * pFileName, int Number, int Support, int fOccurs, int fTtDump, int fVerbose ); diff --git a/src/map/if/ifDelay.c b/src/map/if/ifDelay.c index 9c5704b7..433b4e4d 100644 --- a/src/map/if/ifDelay.c +++ b/src/map/if/ifDelay.c @@ -238,6 +238,7 @@ int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ) assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 ); if ( vAig ) Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) ); + pCut->Cost = 0; return 0; } if ( pCut->nLeaves == 1 ) // variable @@ -247,6 +248,7 @@ int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ) Vec_IntPush( vAig, 0 ); if ( vAig ) Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) ); + pCut->Cost = 0; return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay; } else @@ -263,6 +265,98 @@ int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ) } } +/**Function************************************************************* + + Synopsis [Evaluate delay using SOP balancing.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutLutBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm ) +{ + if ( pCut->nLeaves == 0 ) // const + return 0; + if ( pCut->nLeaves == 1 ) // variable + { + pPerm[0] = 0; + return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay; + } + else + { + int LutSize = p->pPars->pLutStruct[0] - '0'; + int i, Delay, DelayMax; + assert( (If_CutLeaveNum(pCut) > LutSize) == (pCut->uMaskFunc > 0) ); + for ( i = 0; i < If_CutLeaveNum(pCut); i++ ) + { + if ( If_CutLeaveNum(pCut) > LutSize && ((pCut->uMaskFunc >> (i << 2)) & 1) ) + pPerm[i] = 2; + else + pPerm[i] = 1; + Delay = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay; + DelayMax = Abc_MaxInt( DelayMax, Delay + (int)pPerm[i] ); + } + return DelayMax; + } +} + +/**Function************************************************************* + + Synopsis [Evaluate delay using SOP balancing.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutLutBalanceEval( If_Man_t * p, If_Cut_t * pCut ) +{ + pCut->fUser = 1; + pCut->Cost = pCut->nLeaves > 1 ? 1 : 0; + if ( pCut->nLeaves == 0 ) // const + { + assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 ); + return 0; + } + if ( pCut->nLeaves == 1 ) // variable + { + assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 1 ); + return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay; + } + else + { + int LutSize = p->pPars->pLutStruct[0] - '0'; + int i, pTimes[IF_MAX_FUNC_LUTSIZE]; + int DelayMax = 0, nLeafMax = 0; + unsigned uLeafMask = 0; + for ( i = 0; i < If_CutLeaveNum(pCut); i++ ) + { + pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay; + assert( DelayMax <= pTimes[i] ); + if ( DelayMax < pTimes[i] ) + DelayMax = pTimes[i], nLeafMax = 1, uLeafMask = (1 << (i << 2)); + else + nLeafMax++, uLeafMask |= (1 << (i << 2)); + } + if ( If_CutLeaveNum(pCut) <= LutSize ) + return DelayMax + 1; + pCut->Cost = 2; + if ( nLeafMax <= LutSize - 1 ) + { + pCut->uMaskFunc = If_DsdManCheckXY( p->pIfDsdMan, If_CutDsdLit(p, pCut), LutSize, 1, uLeafMask, 0, 0 ); + if ( pCut->uMaskFunc > 0 ) + return DelayMax + 1; + } + pCut->uMaskFunc = If_DsdManCheckXY( p->pIfDsdMan, If_CutDsdLit(p, pCut), LutSize, 1, 0, 0, 0 ); + return DelayMax + 2; + } +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/if/ifDsd.c b/src/map/if/ifDsd.c index 317ceac5..3eeef4c8 100644 --- a/src/map/if/ifDsd.c +++ b/src/map/if/ifDsd.c @@ -1529,7 +1529,7 @@ unsigned If_DsdManCheckAndXor( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, I If_DsdManComputeFirst( p, pObj, pFirsts ); uRes = If_DsdSign(p, pObj, i[0], iFirst + pFirsts[i[0]], 0) | If_DsdSign(p, pObj, i[1], iFirst + pFirsts[i[1]], 0); - if ( uRes & ~(uRes >> 1) & uMaskNot ) + if ( uRes & uMaskNot ) continue; return uRes; } @@ -1549,7 +1549,7 @@ unsigned If_DsdManCheckAndXor( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, I uRes = If_DsdSign(p, pObj, i[0], iFirst + pFirsts[i[0]], 0) | If_DsdSign(p, pObj, i[1], iFirst + pFirsts[i[1]], 0) | If_DsdSign(p, pObj, i[2], iFirst + pFirsts[i[2]], 0); - if ( uRes & ~(uRes >> 1) & uMaskNot ) + if ( uRes & uMaskNot ) continue; return uRes; } @@ -1571,7 +1571,7 @@ unsigned If_DsdManCheckAndXor( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, I If_DsdSign(p, pObj, i[1], iFirst + pFirsts[i[1]], 0) | If_DsdSign(p, pObj, i[2], iFirst + pFirsts[i[2]], 0) | If_DsdSign(p, pObj, i[3], iFirst + pFirsts[i[3]], 0); - if ( uRes & ~(uRes >> 1) & uMaskNot ) + if ( uRes & uMaskNot ) continue; return uRes; } @@ -1596,7 +1596,7 @@ unsigned If_DsdManCheckMux( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, If_D return ~0; If_DsdManComputeFirst( p, pObj, pFirsts ); uRes = If_DsdSign(p, pObj, 0, iFirst + pFirsts[0], 1) | If_DsdSign(p, pObj, 1, iFirst + pFirsts[1], 0); - if ( (uRes & ~(uRes >> 1) & uMaskNot) == 0 ) + if ( (uRes & uMaskNot) == 0 ) return uRes; } // second input @@ -1608,7 +1608,7 @@ unsigned If_DsdManCheckMux( If_DsdMan_t * p, int iFirst, unsigned uMaskNot, If_D return ~0; If_DsdManComputeFirst( p, pObj, pFirsts ); uRes = If_DsdSign(p, pObj, 0, iFirst + pFirsts[0], 1) | If_DsdSign(p, pObj, 2, iFirst + pFirsts[2], 0); - if ( (uRes & ~(uRes >> 1) & uMaskNot) == 0 ) + if ( (uRes & uMaskNot) == 0 ) return uRes; } return 0; @@ -1665,7 +1665,7 @@ Dau_DecPrintSets( vSets, nFans ); uRes |= If_DsdSign(p, pObj, v, iFirst + pFirsts[v], 1); else assert( 0 ); } - if ( uRes & ~(uRes >> 1) & uMaskNot ) + if ( uRes & uMaskNot ) continue; return uRes; } @@ -2010,6 +2010,7 @@ int If_CutDsdBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ) assert( Abc_Lit2Var(If_CutDsdLit(p, pCut)) == 0 ); if ( vAig ) Vec_IntPush( vAig, Abc_LitIsCompl(If_CutDsdLit(p, pCut)) ); + pCut->Cost = 0; return 0; } if ( pCut->nLeaves == 1 ) // variable @@ -2019,6 +2020,7 @@ int If_CutDsdBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig ) Vec_IntPush( vAig, 0 ); if ( vAig ) Vec_IntPush( vAig, Abc_LitIsCompl(If_CutDsdLit(p, pCut)) ); + pCut->Cost = 0; return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay; } else diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 9452feb3..e1d69501 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -99,7 +99,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep If_Cut_t * pCut0R, * pCut1R; int fFunc0R, fFunc1R; int i, k, v, fChange; - int fSave0 = p->pPars->fDelayOpt || p->pPars->fDsdBalance || p->pPars->fUserRecLib; + int fSave0 = p->pPars->fDelayOpt || p->pPars->fDelayOptLut || p->pPars->fDsdBalance || p->pPars->fUserRecLib; assert( !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 0 ); assert( !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 0 ); @@ -122,6 +122,8 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep // recompute the parameters of the best cut if ( p->pPars->fDelayOpt ) pCut->Delay = If_CutSopBalanceEval( p, pCut, NULL ); + else if ( p->pPars->fDelayOptLut ) + pCut->Delay = If_CutLutBalanceEval( p, pCut ); else if ( p->pPars->fDsdBalance ) pCut->Delay = If_CutDsdBalanceEval( p, pCut, NULL ); else if ( p->pPars->fUserRecLib ) @@ -278,6 +280,8 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep // check if the cut satisfies the required times if ( p->pPars->fDelayOpt ) pCut->Delay = If_CutSopBalanceEval( p, pCut, NULL ); + else if ( p->pPars->fDelayOptLut ) + pCut->Delay = If_CutLutBalanceEval( p, pCut ); else if ( p->pPars->fDsdBalance ) pCut->Delay = If_CutDsdBalanceEval( p, pCut, NULL ); else if ( p->pPars->fUserRecLib ) @@ -351,7 +355,7 @@ void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fP If_Set_t * pCutSet; If_Obj_t * pTemp; If_Cut_t * pCutTemp, * pCut; - int i, fSave0 = p->pPars->fDelayOpt || p->pPars->fDsdBalance || p->pPars->fUserRecLib; + int i, fSave0 = p->pPars->fDelayOpt || p->pPars->fDelayOptLut || p->pPars->fDsdBalance || p->pPars->fUserRecLib; assert( pObj->pEquiv != NULL ); // prepare diff --git a/src/map/if/ifTime.c b/src/map/if/ifTime.c index 82468f75..e35ba0db 100644 --- a/src/map/if/ifTime.c +++ b/src/map/if/ifTime.c @@ -207,6 +207,11 @@ void If_CutPropagateRequired( If_Man_t * p, If_Obj_t * pObj, If_Cut_t * pCut, fl int Delay = If_CutSopBalancePinDelays( p, pCut, pPerm ); assert( Delay == pCut->Delay ); } + else if ( p->pPars->fDelayOptLut ) + { + int Delay = If_CutLutBalancePinDelays( p, pCut, pPerm ); + assert( Delay == pCut->Delay ); + } else if ( p->pPars->fDsdBalance ) { int Delay = If_CutDsdBalancePinDelays( p, pCut, pPerm ); -- cgit v1.2.3