From 4a50b09c6719fe548f584aa5a22637ab7ddf8a6a Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 13 Jul 2013 11:12:36 -0700 Subject: New technology mapper. --- src/base/abci/abc.c | 2 +- src/map/mpm/mpmInt.h | 3 +- src/map/mpm/mpmMan.c | 2 ++ src/map/mpm/mpmMap.c | 93 ++++++++++++++++++++++++++------------------------ src/map/mpm/mpmTruth.c | 39 ++++++++++----------- 5 files changed, 72 insertions(+), 67 deletions(-) diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 53f5483a..b2aeac46 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -29589,7 +29589,7 @@ usage: sprintf(Buffer, "%d", pPars->DelayTarget ); Abc_Print( -2, "usage: &if2 [-KD num] [-mzvh]\n" ); Abc_Print( -2, "\t performs technology mapping of the network\n" ); - Abc_Print( -2, "\t-K num : sets the LUT size for the mapping [default = %s]\n", nLutSize ); + Abc_Print( -2, "\t-K num : sets the LUT size for the mapping [default = %d]\n", nLutSize ); Abc_Print( -2, "\t-D num : sets the delay constraint for the mapping [default = %s]\n", Buffer ); Abc_Print( -2, "\t-m : enables cut minimization by removing vacuous variables [default = %s]\n", pPars->fCutMin? "yes": "no" ); Abc_Print( -2, "\t-z : toggles deriving LUTs when mapping into LUT structures [default = %s]\n", pPars->fDeriveLuts? "yes": "no" ); diff --git a/src/map/mpm/mpmInt.h b/src/map/mpm/mpmInt.h index df534e1e..e64aa43b 100644 --- a/src/map/mpm/mpmInt.h +++ b/src/map/mpm/mpmInt.h @@ -103,8 +103,7 @@ struct Mpm_Man_t_ Vec_Ptr_t * vTemp; // storage for cuts // object presence unsigned char * pObjPres; // object presence - int pObjPresUsed[MPM_VAR_MAX]; - int nObjPresUsed; + Vec_Int_t vObjPresUsed; // used objects Vec_Str_t vObjShared; // object presence // cut comparison int (* pCutCmp) (Mpm_Uni_t *, Mpm_Uni_t *);// procedure to compare cuts diff --git a/src/map/mpm/mpmMan.c b/src/map/mpm/mpmMan.c index d665e783..659372f9 100644 --- a/src/map/mpm/mpmMan.c +++ b/src/map/mpm/mpmMan.c @@ -65,6 +65,7 @@ Mpm_Man_t * Mpm_ManStart( Mig_Man_t * pMig, Mpm_Par_t * pPars ) for ( i = p->nNumCuts; i >= 0; i-- ) Vec_PtrPush( &p->vFreeUnits, p->pCutUnits + i ); p->pObjPres = ABC_FALLOC( unsigned char, Mig_ManObjNum(pMig) ); + Vec_IntGrow( &p->vObjPresUsed, p->nLutSize ); Vec_StrGrow( &p->vObjShared, 32 ); p->vTemp = Vec_PtrAlloc( 1000 ); // mapping attributes @@ -114,6 +115,7 @@ void Mpm_ManStop( Mpm_Man_t * p ) } Vec_PtrFree( p->vTemp ); Mmr_StepStop( p->pManCuts ); + ABC_FREE( p->vObjPresUsed.pArray ); ABC_FREE( p->vFreeUnits.pArray ); ABC_FREE( p->vObjShared.pArray ); ABC_FREE( p->pObjPres ); diff --git a/src/map/mpm/mpmMap.c b/src/map/mpm/mpmMap.c index 539638e9..e613d9ba 100644 --- a/src/map/mpm/mpmMap.c +++ b/src/map/mpm/mpmMap.c @@ -170,12 +170,12 @@ static inline void Mpm_CutDeref( Mpm_Man_t * p, int * pLeaves, int nLeaves ) Mig_ManObj( p->pMig, Abc_Lit2Var(pLeaves[i]) )->nMapRefs--; } */ -static inline void Mpm_CutPrint( int * pLeaves, int nLeaves ) +static inline void Mpm_CutPrint( Mpm_Cut_t * pCut ) { int i; - printf( "%d : { ", nLeaves ); - for ( i = 0; i < nLeaves; i++ ) - printf( "%d ", pLeaves[i] ); + printf( "%d : { ", pCut->nLeaves ); + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + printf( "%d ", pCut->pLeaves[i] ); printf( "}\n" ); } static inline void Mpm_CutPrintAll( Mpm_Man_t * p ) @@ -184,46 +184,33 @@ static inline void Mpm_CutPrintAll( Mpm_Man_t * p ) for ( i = 0; i < p->nCutStore; i++ ) { printf( "%2d : ", i ); - Mpm_CutPrint( p->pCutStore[i]->pCut.pLeaves, p->pCutStore[i]->pCut.nLeaves ); + Mpm_CutPrint( &p->pCutStore[i]->pCut ); } } - -/**Function************************************************************* - - Synopsis [Cut merging.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int Mpm_ManSetIsSmaller( Mpm_Man_t * p, int * pLits, int nLits, int nTotal ) // check if pCut is contained in the current one (p->pCutTemp) +static inline int Mpm_ManSetIsSmaller( Mpm_Man_t * p, Mpm_Cut_t * pCut, int nTotal ) // check if pCut is contained in the current one (p->pCutTemp) { int i, Index; - for ( i = 0; i < nLits; i++ ) + for ( i = 0; i < (int)pCut->nLeaves; i++ ) { - Index = (int)p->pObjPres[Abc_Lit2Var(pLits[i])]; + Index = (int)p->pObjPres[Abc_Lit2Var(pCut->pLeaves[i])]; if ( Index == 0xFF ) return 0; - assert( Index < nTotal ); +// assert( Index < nTotal ); } return 1; } -static inline int Mpm_ManSetIsBigger( Mpm_Man_t * p, int * pLits, int nLits, int nTotal ) // check if pCut contains the current one (p->pCutTemp) +static inline int Mpm_ManSetIsBigger( Mpm_Man_t * p, Mpm_Cut_t * pCut, int nTotal ) // check if pCut contains the current one (p->pCutTemp) { - int i, Index; - unsigned uMask = 0; - for ( i = 0; i < nLits; i++ ) + int i, Index, Counter = 0; + for ( i = 0; i < (int)pCut->nLeaves; i++ ) { - Index = (int)p->pObjPres[Abc_Lit2Var(pLits[i])]; + Index = (int)p->pObjPres[Abc_Lit2Var(pCut->pLeaves[i])]; if ( Index == 0xFF ) continue; - assert( Index < nTotal ); - uMask |= (1 << Index); +// assert( Index < nTotal ); + Counter++; } - return uMask == ~(~(unsigned)0 << nTotal); + return (int)(Counter == nTotal); } /**Function************************************************************* @@ -278,6 +265,7 @@ static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int pUnit->mEdge = MPM_UNIT_EDGE * pCut->nLeaves; pUnit->mAveRefs = 0; pUnit->Cost = 0; + pUnit->uSign = 0; Mpm_CutForEachLeafId( pCut, iLeaf, i ) { if ( p->fMainRun && pMapRefs[iLeaf] == 0 ) // not used in the mapping @@ -294,7 +282,7 @@ static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int } pUnit->uSign |= ((word)1 << (iLeaf & 0x3F)); } - pUnit->mAveRefs = pUnit->mAveRefs * MPM_UNIT_EDGE / pCut->nLeaves; + pUnit->mAveRefs = pUnit->mAveRefs * MPM_UNIT_EDGE / Abc_MaxInt(pCut->nLeaves, 1); return pUnit; } @@ -352,7 +340,7 @@ clk = Abc_Clock(); pUnit = p->pCutStore[k]; if ( pUnitNew->pCut.nLeaves >= pUnit->pCut.nLeaves && (pUnitNew->uSign & pUnit->uSign) == pUnit->uSign && - Mpm_ManSetIsSmaller(p, pUnit->pCut.pLeaves, pUnit->pCut.nLeaves, pUnitNew->pCut.nLeaves) ) + Mpm_ManSetIsSmaller(p, &pUnit->pCut, pUnitNew->pCut.nLeaves) ) { #ifdef MIG_RUNTIME p->timeCompare += Abc_Clock() - clk; @@ -384,7 +372,7 @@ p->timeCompare += Abc_Clock() - clk; pUnit = p->pCutStore[k]; if ( pUnitNew->pCut.nLeaves <= pUnit->pCut.nLeaves && (pUnitNew->uSign & pUnit->uSign) == pUnitNew->uSign && - Mpm_ManSetIsBigger(p, pUnit->pCut.pLeaves, pUnit->pCut.nLeaves, pUnitNew->pCut.nLeaves) ) + Mpm_ManSetIsBigger(p, &pUnit->pCut, pUnitNew->pCut.nLeaves) ) { Vec_PtrPush( &p->vFreeUnits, pUnit ); continue; @@ -422,7 +410,7 @@ void Mpm_ObjAddChoiceCutsToStore( Mpm_Man_t * p, Mig_Obj_t * pObj, int ReqTime ) // create cuts at the node from storage void Mpm_ObjTranslateCutsFromStore( Mpm_Man_t * p, Mig_Obj_t * pObj, int fAddUnit ) { - Mpm_Cut_t * pCut; + Mpm_Cut_t * pCut = NULL; Mpm_Uni_t * pUnit; int i, *pList = Mpm_ObjCutListP( p, pObj ); assert( p->nCutStore > 0 && p->nCutStore <= p->nNumCuts ); @@ -435,6 +423,8 @@ void Mpm_ObjTranslateCutsFromStore( Mpm_Man_t * p, Mig_Obj_t * pObj, int fAddUni pList = &pCut->hNext; Vec_PtrPush( &p->vFreeUnits, pUnit ); } + if ( p->nCutStore == 1 && pCut->nLeaves < 2 ) + fAddUnit = 0; *pList = fAddUnit ? Mpm_CutCreateUnit( p, Mig_ObjId(pObj) ) : 0; assert( Vec_PtrSize(&p->vFreeUnits) == p->nNumCuts + 1 ); } @@ -513,16 +503,26 @@ static inline int Mpm_ObjDeriveCut( Mpm_Man_t * p, Mpm_Cut_t ** pCuts, Mpm_Cut_t { int i, c, iObj; // clean present objects - for ( i = 0; i < p->nObjPresUsed; i++ ) - p->pObjPres[p->pObjPresUsed[i]] = (unsigned char)0xFF; - p->nObjPresUsed = 0; +// Vec_IntForEachEntry( &p->vObjPresUsed, iObj, i ) +// p->pObjPres[iObj] = (unsigned char)0xFF; + for ( i = 0; i < p->vObjPresUsed.nSize; i++ ) + p->pObjPres[p->vObjPresUsed.pArray[i]] = (unsigned char)0xFF; + Vec_IntClear(&p->vObjPresUsed); Vec_StrClear(&p->vObjShared); // check present objects // for ( i = 0; i < Mig_ManObjNum(p->pMig); i++ ) // assert( p->pObjPres[i] == (unsigned char)0xFF ); - // collect cuts + // base cut pCut->nLeaves = 0; - for ( c = 0; pCuts[c] && c < 3; c++ ) + for ( i = 0; i < (int)pCuts[0]->nLeaves; i++ ) + { + iObj = Abc_Lit2Var(pCuts[0]->pLeaves[i]); + Vec_IntPush( &p->vObjPresUsed, iObj ); + p->pObjPres[iObj] = pCut->nLeaves; + pCut->pLeaves[pCut->nLeaves++] = pCuts[0]->pLeaves[i]; + } + // remaining cuts + for ( c = 1; pCuts[c] && c < 3; c++ ) { for ( i = 0; i < (int)pCuts[c]->nLeaves; i++ ) { @@ -531,7 +531,7 @@ static inline int Mpm_ObjDeriveCut( Mpm_Man_t * p, Mpm_Cut_t ** pCuts, Mpm_Cut_t continue; if ( (int)pCut->nLeaves == p->nLutSize ) return 0; - p->pObjPresUsed[p->nObjPresUsed++] = iObj; + Vec_IntPush( &p->vObjPresUsed, iObj ); p->pObjPres[iObj] = pCut->nLeaves; pCut->pLeaves[pCut->nLeaves++] = pCuts[c]->pLeaves[i]; } @@ -564,6 +564,10 @@ p->timeMerge += clock() - clk; return 1; } + // derive truth table + if ( p->pPars->fUseTruth ) + Mpm_CutComputeTruth6( p, pCut, pCuts[0], pCuts[1], pCuts[2], Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ); + #ifdef MIG_RUNTIME p->timeMerge += clock() - clk; clk = clock(); @@ -576,10 +580,6 @@ p->timeEval += clock() - clk; if ( p->fMainRun && ArrTime > Required ) return 1; - // derive truth table - if ( p->pPars->fUseTruth ) - Mpm_CutComputeTruth6( p, pCut, pCuts[0], pCuts[1], pCuts[2], Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ); - #ifdef MIG_RUNTIME clk = Abc_Clock(); #endif @@ -673,6 +673,8 @@ finish: Mpm_ObjSetTime( p, pObj, p->pCutStore[0]->mTime ); Mpm_ObjSetArea( p, pObj, p->pCutStore[0]->mArea ); Mpm_ObjSetEdge( p, pObj, p->pCutStore[0]->mEdge ); +// if ( pCut->nLeaves < 1 ) +// printf( "%d ", pCut->nLeaves ); } else assert( !p->fMainRun ); assert( hCutBest > 0 ); @@ -837,9 +839,10 @@ void Mpm_ManPerformRound( Mpm_Man_t * p ) Mig_ManForEachNode( p->pMig, pObj ) Mpm_ManDeriveCuts( p, pObj ); Mpm_ManFinalizeRound( p ); - printf( "Del =%5d. Ar =%8d. Edge =%8d. Cut =%10d. Max =%10d. Rem =%6d. ", + printf( "Del =%5d. Ar =%8d. Edge =%8d. Cut =%10d. Max =%10d. Tru =%6d. Small =%5d. ", p->GloRequired, p->GloArea, p->GloEdge, - p->nCutsMerged, p->pManCuts->nEntriesMax, p->pManCuts->nEntries ); + p->nCutsMerged, p->pManCuts->nEntriesMax, + p->vTtMem ? p->vTtMem->nEntries : 0, p->nSmallSupp ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); } void Mpm_ManPerform( Mpm_Man_t * p ) diff --git a/src/map/mpm/mpmTruth.c b/src/map/mpm/mpmTruth.c index 480ce930..136b655c 100644 --- a/src/map/mpm/mpmTruth.c +++ b/src/map/mpm/mpmTruth.c @@ -47,36 +47,37 @@ static inline int Mpm_CutTruthMinimize6( Mpm_Man_t * p, Mpm_Cut_t * pCut ) { unsigned uSupport; int i, k, nSuppSize; - word t = *Mpm_CutTruth( p, Abc_Lit2Var(pCut->iFunc) ); // compute the support of the cut's function + word t = *Mpm_CutTruth( p, Abc_Lit2Var(pCut->iFunc) ); uSupport = Abc_Tt6SupportAndSize( t, Mpm_CutLeafNum(pCut), &nSuppSize ); if ( nSuppSize == Mpm_CutLeafNum(pCut) ) return 0; - if ( nSuppSize < 2 ) - p->nSmallSupp++; + p->nSmallSupp += (int)(nSuppSize < 2); // update leaves and signature for ( i = k = 0; i < Mpm_CutLeafNum(pCut); i++ ) { - if ( !(uSupport & (1 << i)) ) - continue; - if ( k < i ) + if ( ((uSupport >> i) & 1) ) { - pCut->pLeaves[k] = pCut->pLeaves[i]; - Abc_TtSwapVars( &t, p->nLutSize, k, i ); + if ( k < i ) + { + pCut->pLeaves[k] = pCut->pLeaves[i]; + Abc_TtSwapVars( &t, p->nLutSize, k, i ); + } + k++; + } + else + { + int iObj = Abc_Lit2Var( pCut->pLeaves[i] ); + int Res = Vec_IntRemove( &p->vObjPresUsed, iObj ); + assert( Res == 1 ); + p->pObjPres[iObj] = (unsigned char)0xFF; } - k++; } assert( k == nSuppSize ); pCut->nLeaves = nSuppSize; - assert( nSuppSize == Abc_TtSupportSize(&t, Mpm_CutLeafNum(pCut)) ); + assert( nSuppSize == Abc_TtSupportSize(&t, 6) ); // save the result - if ( t & 1 ) - { - t = ~t; - pCut->iFunc = Abc_Var2Lit( Vec_MemHashInsert( p->vTtMem, &t ), 1 ); - } - else - pCut->iFunc = Abc_Var2Lit( Vec_MemHashInsert( p->vTtMem, &t ), 0 ); + pCut->iFunc = Abc_Var2Lit( Vec_MemHashInsert(p->vTtMem, &t), Abc_LitIsCompl(pCut->iFunc) ); return 1; } static inline word Mpm_TruthStretch6( word Truth, Mpm_Cut_t * pCut, Mpm_Cut_t * pCut0, int nLimit ) @@ -134,8 +135,8 @@ int Mpm_CutComputeTruth6( Mpm_Man_t * p, Mpm_Cut_t * pCut, Mpm_Cut_t * pCut0, Mp } #endif -// if ( p->pPars->fCutMin ) -// return Mpm_CutTruthMinimize6( p, pCut ); + if ( p->pPars->fCutMin ) + return Mpm_CutTruthMinimize6( p, pCut ); return 0; } -- cgit v1.2.3