From dd29ca30a6afe0ba384a8985957a5bbead031911 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 14 Jul 2013 23:12:05 -0700 Subject: New technology mapper. --- src/aig/gia/giaIf.c | 4 +- src/aig/gia/giaUtil.c | 5 +- src/base/abci/abc.c | 4 +- src/map/mpm/mpmAbc.c | 41 +++++- src/map/mpm/mpmInt.h | 2 - src/map/mpm/mpmMan.c | 12 +- src/map/mpm/mpmMap.c | 360 ++++++++++++++++++++++++-------------------------- src/map/mpm/mpmMig.c | 15 +-- src/map/mpm/mpmMig.h | 11 +- 9 files changed, 234 insertions(+), 220 deletions(-) diff --git a/src/aig/gia/giaIf.c b/src/aig/gia/giaIf.c index 72c65da0..f3820ab4 100644 --- a/src/aig/gia/giaIf.c +++ b/src/aig/gia/giaIf.c @@ -409,6 +409,7 @@ If_Man_t * Gia_ManToIf( Gia_Man_t * p, If_Par_t * pPars ) // create levels with choices Gia_ManChoiceLevel( p ); // mark representative nodes + if ( p->pSibls ) Gia_ManMarkFanoutDrivers( p ); // start the mapping manager and set its parameters pIfMan = If_ManStart( pPars ); @@ -445,12 +446,13 @@ If_Man_t * Gia_ManToIf( Gia_Man_t * p, If_Par_t * pPars ) { Gia_Obj_t * pSibl, * pPrev; for ( pPrev = pObj, pSibl = Gia_ObjSiblObj(p, i); pSibl; pPrev = pSibl, pSibl = Gia_ObjSiblObj(p, Gia_ObjId(p, pSibl)) ) - If_ObjSetChoice( If_ManObj(pIfMan, Gia_ObjValue(pObj)), If_ManObj(pIfMan, Gia_ObjValue(pSibl)) ); + If_ObjSetChoice( If_ManObj(pIfMan, Gia_ObjValue(pPrev)), If_ManObj(pIfMan, Gia_ObjValue(pSibl)) ); If_ManCreateChoice( pIfMan, If_ManObj(pIfMan, Gia_ObjValue(pObj)) ); pPars->fExpRed = 0; } // assert( If_ObjLevel(pIfObj) == Gia_ObjLevel(pNode) ); } + if ( p->pSibls ) Gia_ManCleanMark0( p ); return pIfMan; } diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c index 2faf424e..e5f6eb17 100644 --- a/src/aig/gia/giaUtil.c +++ b/src/aig/gia/giaUtil.c @@ -339,6 +339,7 @@ void Gia_ManFillValue( Gia_Man_t * p ) ***********************************************************************/ void Gia_ObjSetPhase( Gia_Obj_t * pObj ) { + assert( !Gia_ObjIsXor(pObj) ); if ( Gia_ObjIsAnd(pObj) ) pObj->fPhase = (Gia_ObjPhase(Gia_ObjFanin0(pObj)) ^ Gia_ObjFaninC0(pObj)) & (Gia_ObjPhase(Gia_ObjFanin1(pObj)) ^ Gia_ObjFaninC1(pObj)); @@ -1342,8 +1343,9 @@ void Gia_ManMarkFanoutDrivers( Gia_Man_t * p ) { Gia_Obj_t * pObj; int i; - Gia_ManCleanMark0( p ); Gia_ManForEachObj( p, pObj, i ) + { + pObj->fMark0 = 0; if ( Gia_ObjIsAnd(pObj) ) { Gia_ObjFanin0(pObj)->fMark0 = 1; @@ -1351,6 +1353,7 @@ void Gia_ManMarkFanoutDrivers( Gia_Man_t * p ) } else if ( Gia_ObjIsCo(pObj) ) Gia_ObjFanin0(pObj)->fMark0 = 1; + } } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 601e0910..d942e41b 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -29587,8 +29587,8 @@ int Abc_CommandAbc9If2( Abc_Frame_t * pAbc, int argc, char ** argv ) if ( pPars->fMap4Cnf ) pPars->fUseDsd = 1; if ( pPars->fCutMin ) -// pPars->fUseTruth = 1; - pPars->fUseDsd = 1; + pPars->fUseTruth = 1; +// pPars->fUseDsd = 1; // perform mapping pNew = Mpm_ManMappingTest( pAbc->pGia, pPars ); Mpm_LibLutFree( pPars->pLib ); diff --git a/src/map/mpm/mpmAbc.c b/src/map/mpm/mpmAbc.c index eaf5fd7c..0e3e27ff 100644 --- a/src/map/mpm/mpmAbc.c +++ b/src/map/mpm/mpmAbc.c @@ -32,6 +32,41 @@ ABC_NAMESPACE_IMPL_START /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Mig_ManCreateChoices( Mig_Man_t * pMig, Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + int i; + assert( Mig_ManObjNum(pMig) == Gia_ManObjNum(p) ); + assert( Vec_IntSize(&pMig->vSibls) == 0 ); + Vec_IntFill( &pMig->vSibls, Gia_ManObjNum(p), 0 ); + Gia_ManMarkFanoutDrivers( p ); + Gia_ManForEachObj( p, pObj, i ) + { + Gia_ObjSetPhase( pObj ); + assert( Abc_Lit2Var(pObj->Value) == i ); + Mig_ObjSetPhase( Mig_ManObj(pMig, i), pObj->fPhase ); + if ( Gia_ObjSibl(p, i) && pObj->fMark0 ) + { + Gia_Obj_t * pSibl, * pPrev; + for ( pPrev = pObj, pSibl = Gia_ObjSiblObj(p, i); pSibl; pPrev = pSibl, pSibl = Gia_ObjSiblObj(p, Gia_ObjId(p, pSibl)) ) + Mig_ObjSetSiblId( Mig_ManObj(pMig, Abc_Lit2Var(pPrev->Value)), Abc_Lit2Var(pSibl->Value) ); + pMig->nChoices++; + } + } + Gia_ManCleanMark0( p ); +} + /**Function************************************************************* Synopsis [] @@ -51,11 +86,9 @@ Mig_Man_t * Mig_ManCreate( void * pGia ) Mig_Man_t * pNew; Gia_Obj_t * pObj; int i; - // create the new manager pNew = Mig_ManStart(); pNew->pName = Abc_UtilStrsav( p->pName ); Gia_ManConst0(p)->Value = 0; - // create objects Gia_ManForEachObj1( p, pObj, i ) { if ( Gia_ObjIsMux(p, i) ) @@ -71,6 +104,8 @@ Mig_Man_t * Mig_ManCreate( void * pGia ) else assert( 0 ); } Mig_ManSetRegNum( pNew, Gia_ManRegNum(p) ); + if ( p->pSibls ) + Mig_ManCreateChoices( pNew, p ); return pNew; } @@ -86,7 +121,7 @@ Mig_Man_t * Mig_ManCreate( void * pGia ) ***********************************************************************/ static inline unsigned Mpm_CutDataInt( Mpm_Cut_t * pCut ) { return pCut->hNext; } -static inline void Mpm_CutSetDataInt( Mpm_Cut_t * pCut, unsigned Data ) { pCut->hNext = Data; } +static inline void Mpm_CutSetDataInt( Mpm_Cut_t * pCut, int Data ) { pCut->hNext = Data; } int Mpm_ManNodeIfToGia_rec( Gia_Man_t * pNew, Mpm_Man_t * pMan, Mig_Obj_t * pObj, Vec_Ptr_t * vVisited, int fHash ) { Mig_Obj_t * pTemp; diff --git a/src/map/mpm/mpmInt.h b/src/map/mpm/mpmInt.h index 307e7a8c..32854b72 100644 --- a/src/map/mpm/mpmInt.h +++ b/src/map/mpm/mpmInt.h @@ -156,7 +156,6 @@ struct Mpm_Man_t_ int nCutsMerged; int nCutsMergedAll; int nSmallSupp; - abctime timeFanin; abctime timeDerive; abctime timeMerge; abctime timeEval; @@ -184,7 +183,6 @@ static inline void Mpm_ObjSetCutList( Mpm_Man_t * p, Mig_Obj_t * pObj, in static inline int Mpm_CutLeafNum( Mpm_Cut_t * pCut ) { return pCut->nLeaves; } static inline word * Mpm_CutTruth( Mpm_Man_t * p, int iFunc ) { return Vec_MemReadEntry(p->vTtMem, iFunc); } -static inline void Mpm_ManSetMigRefs( Mpm_Man_t * p ) { assert( Vec_IntSize(&p->vMigRefs) == Vec_IntSize(&p->pMig->vRefs) ); memcpy( Vec_IntArray(&p->vMigRefs), Vec_IntArray(&p->pMig->vRefs), sizeof(int) * Mig_ManObjNum(p->pMig) ); } static inline int Mig_ObjMigRefNum( Mpm_Man_t * p, Mig_Obj_t * pObj ) { return Vec_IntEntry(&p->vMigRefs, Mig_ObjId(pObj)); } static inline int Mig_ObjMigRefDec( Mpm_Man_t * p, Mig_Obj_t * pObj ) { return Vec_IntAddToEntry(&p->vMigRefs, Mig_ObjId(pObj), -1); } diff --git a/src/map/mpm/mpmMan.c b/src/map/mpm/mpmMan.c index eb1a3d1e..224d837c 100644 --- a/src/map/mpm/mpmMan.c +++ b/src/map/mpm/mpmMan.c @@ -50,7 +50,7 @@ Mpm_Man_t * Mpm_ManStart( Mig_Man_t * pMig, Mpm_Par_t * pPars ) assert( pPars->nNumCuts <= MPM_CUT_MAX ); assert( !pPars->fUseTruth || pPars->pLib->LutMax <= 16 ); assert( !pPars->fUseDsd || pPars->pLib->LutMax <= 6 ); - Mig_ManSetRefs( pMig, 1 ); + Mig_ManSetRefs( pMig ); // alloc p = ABC_CALLOC( Mpm_Man_t, 1 ); p->pMig = pMig; @@ -119,7 +119,7 @@ void Mpm_ManStop( Mpm_Man_t * p ) FILE * pFile = fopen( pFileName, "wb" ); Vec_MemDump( pFile, p->vTtMem ); fclose( pFile ); - printf( "Dumpted %d %d-var truth tables into file \"%s\" (%.2f MB).\n", + printf( "Dumped %d %d-var truth tables into file \"%s\" (%.2f MB).\n", Vec_MemEntryNum(p->vTtMem), p->nLutSize, pFileName, (16.0 * p->nTruWords + 1.0) * Vec_MemEntryNum(p->vTtMem) / (1 << 20) ); } @@ -171,9 +171,8 @@ void Mpm_ManStop( Mpm_Man_t * p ) void Mpm_ManPrintStatsInit( Mpm_Man_t * p ) { printf( "K = %d. C = %d. Cand = %d. XOR = %d. MUX = %d. Choice = %d. CutMin = %d. Truth = %d. DSD = %d.\n", - p->nLutSize, p->nNumCuts, - Mig_ManCiNum(p->pMig) + Mig_ManNodeNum(p->pMig), - Mig_ManXorNum(p->pMig), Mig_ManMuxNum(p->pMig), 0, + p->nLutSize, p->nNumCuts, Mig_ManCandNum(p->pMig), + Mig_ManXorNum(p->pMig), Mig_ManMuxNum(p->pMig), p->pMig->nChoices, p->pPars->fCutMin, p->pPars->fUseTruth, p->pPars->fUseDsd ); } void Mpm_ManPrintStats( Mpm_Man_t * p ) @@ -189,10 +188,9 @@ void Mpm_ManPrintStats( Mpm_Man_t * p ) #ifdef MIG_RUNTIME printf( "\n" ); p->timeTotal = Abc_Clock() - p->timeTotal; - p->timeOther = p->timeTotal - (p->timeFanin + p->timeDerive); + p->timeOther = p->timeTotal - p->timeDerive; Abc_Print( 1, "Runtime breakdown:\n" ); - ABC_PRTP( "Precomputing fanin info ", p->timeFanin , p->timeTotal ); ABC_PRTP( "Complete cut computation ", p->timeDerive , p->timeTotal ); ABC_PRTP( "- Merging cuts ", p->timeMerge , p->timeTotal ); ABC_PRTP( "- Evaluting cut parameters ", p->timeEval , p->timeTotal ); diff --git a/src/map/mpm/mpmMap.c b/src/map/mpm/mpmMap.c index 86b4ab52..077cfaeb 100644 --- a/src/map/mpm/mpmMap.c +++ b/src/map/mpm/mpmMap.c @@ -98,20 +98,6 @@ static inline int Mpm_CutCopySet( Mpm_Man_t * p, Mig_Obj_t * pObj, int fCompl ) *pList = 0; return iList; } -/* -static inline void Mpm_CutRef( Mpm_Man_t * p, int * pLeaves, int nLeaves ) -{ - int i; - for ( i = 0; i < nLeaves; i++ ) - Mig_ManObj( p->pMig, Abc_Lit2Var(pLeaves[i]) )->nMapRefs++; -} -static inline void Mpm_CutDeref( Mpm_Man_t * p, int * pLeaves, int nLeaves ) -{ - int i; - for ( i = 0; i < nLeaves; i++ ) - Mig_ManObj( p->pMig, Abc_Lit2Var(pLeaves[i]) )->nMapRefs--; -} -*/ void Mpm_CutPrint( Mpm_Cut_t * pCut ) { int i; @@ -129,7 +115,7 @@ static inline void Mpm_CutPrintAll( Mpm_Man_t * p ) Mpm_CutPrint( &p->pCutStore[i]->pCut ); } } -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) +static inline int Mpm_ManSetIsSmaller( Mpm_Man_t * p, Mpm_Cut_t * pCut, int nTotal ) // check if pCut is contained in the current one { int i, Index; for ( i = 0; i < (int)pCut->nLeaves; i++ ) @@ -141,7 +127,7 @@ static inline int Mpm_ManSetIsSmaller( Mpm_Man_t * p, Mpm_Cut_t * pCut, int nTot } return 1; } -static inline int Mpm_ManSetIsBigger( Mpm_Man_t * p, Mpm_Cut_t * pCut, 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 { int i, Index, Counter = 0; for ( i = 0; i < (int)pCut->nLeaves; i++ ) @@ -199,17 +185,8 @@ static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int int * pmArea = Vec_IntArray( &p->vAreas ); int * pmEdge = Vec_IntArray( &p->vEdges ); int i, iLeaf; - Mpm_Uni_t * pUnit = (Mpm_Uni_t *)Vec_PtrEntryLast(&p->vFreeUnits); - if ( &pUnit->pCut != pCut ) - { - pUnit->pCut.iFunc = pCut->iFunc; - pUnit->pCut.fCompl = pCut->fCompl; - pUnit->pCut.fUseless= pCut->fUseless; - pUnit->pCut.nLeaves = pCut->nLeaves; - memcpy( pUnit->pCut.pLeaves, pCut->pLeaves, sizeof(int) * pCut->nLeaves ); - } - + assert( &pUnit->pCut == pCut ); pUnit->mTime = ArrTime; pUnit->mArea = Mpm_CutGetArea( p, pCut ); pUnit->mEdge = MPM_UNIT_EDGE * pCut->nLeaves; @@ -238,7 +215,7 @@ static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int /**Function************************************************************* - Synopsis [Cut translation.] + Synopsis [Compares cut against those present in the store.] Description [] @@ -247,7 +224,6 @@ static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int SeeAlso [] ***********************************************************************/ -// compares cut against those present in the store int Mpm_ObjAddCutToStore( Mpm_Man_t * p, Mpm_Cut_t * pCut, int ArrTime ) { int fEnableContainment = 1; @@ -341,102 +317,6 @@ p->timeCompare += Abc_Clock() - clk; assert( p->nCutStore < p->nNumCuts ); return 1; } -// create storage from cuts at the node -void Mpm_ObjAddChoiceCutsToStore( Mpm_Man_t * p, Mig_Obj_t * pObj, int ReqTime ) -{ - Mpm_Cut_t * pCut; - int hCut, hNext, ArrTime; - assert( p->nCutStore == 0 ); - assert( Vec_PtrSize(&p->vFreeUnits) == p->nNumCuts + 1 ); - Mpm_ObjForEachCutSafe( p, pObj, hCut, pCut, hNext ) - { - ArrTime = Mpm_CutGetArrTime( p, pCut ); - if ( ArrTime > ReqTime ) - continue; - Mpm_ObjAddCutToStore( p, pCut, ArrTime ); - Mmr_StepRecycle( p->pManCuts, hCut ); - } -} -// create cuts at the node from storage -void Mpm_ObjTranslateCutsFromStore( Mpm_Man_t * p, Mig_Obj_t * pObj, int fAddUnit ) -{ - Mpm_Cut_t * pCut = NULL; - Mpm_Uni_t * pUnit; - int i, *pList = Mpm_ObjCutListP( p, pObj ); - assert( p->nCutStore > 0 && p->nCutStore <= p->nNumCuts ); - assert( *pList == 0 ); - // translate cuts - for ( i = 0; i < p->nCutStore; i++ ) - { - pUnit = p->pCutStore[i]; - *pList = Mpm_CutCreate( p, &pUnit->pCut, &pCut ); - 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 ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void Mpm_ObjUpdateCut( Mpm_Cut_t * pCut, int * pPerm, int nLeaves ) -{ - int i; - assert( nLeaves <= (int)pCut->nLeaves ); - for ( i = 0; i < nLeaves; i++ ) - pPerm[i] = Abc_LitNotCond( pCut->pLeaves[Abc_Lit2Var(pPerm[i])], Abc_LitIsCompl(pPerm[i]) ); - memcpy( pCut->pLeaves, pPerm, sizeof(int) * nLeaves ); - pCut->nLeaves = nLeaves; -} -static inline void Mpm_ObjRecycleCuts( Mpm_Man_t * p, Mig_Obj_t * pObj ) -{ - Mpm_Cut_t * pCut; - int hCut, hNext; - Mpm_ObjForEachCutSafe( p, pObj, hCut, pCut, hNext ) - Mmr_StepRecycle( p->pManCuts, hCut ); - Mpm_ObjSetCutList( p, pObj, 0 ); -} -static inline void Mpm_ObjDerefFaninCuts( Mpm_Man_t * p, Mig_Obj_t * pObj ) -{ - Mig_Obj_t * pFanin; - int i; - Mig_ObjForEachFanin( pObj, pFanin, i ) - if ( Mig_ObjIsNode(pFanin) && Mig_ObjMigRefDec(p, pFanin) == 0 ) - Mpm_ObjRecycleCuts( p, pFanin ); - if ( Mig_ObjSiblId(pObj) ) - Mpm_ObjRecycleCuts( p, Mig_ObjSibl(pObj) ); - if ( Mig_ObjMigRefNum(p, pObj) == 0 ) - Mpm_ObjRecycleCuts( p, pObj ); -} -static inline void Mpm_ObjCollectFaninsAndSigns( Mpm_Man_t * p, Mig_Obj_t * pObj, int i ) -{ - Mpm_Cut_t * pCut; - int hCut, nCuts = 0; - Mpm_ObjForEachCut( p, pObj, hCut, pCut ) - { - p->pCuts[i][nCuts] = pCut; - p->pSigns[i][nCuts++] = Mpm_CutGetSign( pCut ); - } - p->nCuts[i] = nCuts; -} -static inline void Mpm_ObjPrepareFanins( Mpm_Man_t * p, Mig_Obj_t * pObj ) -{ - Mig_Obj_t * pFanin; - int i; - Mig_ObjForEachFanin( pObj, pFanin, i ) - Mpm_ObjCollectFaninsAndSigns( p, pFanin, i ); -} /**Function************************************************************* @@ -449,83 +329,86 @@ static inline void Mpm_ObjPrepareFanins( Mpm_Man_t * p, Mig_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -static inline int Mpm_ObjDeriveCut( Mpm_Man_t * p, Mpm_Cut_t ** pCuts, Mpm_Cut_t * pCut ) +static inline Mpm_Cut_t * Mpm_ManMergeCuts( Mpm_Man_t * p, Mpm_Cut_t * pCut0, Mpm_Cut_t * pCut1, Mpm_Cut_t * pCut2 ) { + Mpm_Cut_t * pTemp, * pCut = &((Mpm_Uni_t *)Vec_PtrEntryLast(&p->vFreeUnits))->pCut; int i, c, iObj, fDisj = 1; // clean present objects -// 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); -/* - if ( pCuts[0]->nLeaves == 5 && pCuts[1]->nLeaves == 5 ) - { - int s = 0; - Mpm_CutPrint( pCuts[0] ); - Mpm_CutPrint( pCuts[1] ); - } -*/ // check present objects // for ( i = 0; i < Mig_ManObjNum(p->pMig); i++ ) // assert( p->pObjPres[i] == (unsigned char)0xFF ); // base cut pCut->nLeaves = 0; - for ( i = 0; i < (int)pCuts[0]->nLeaves; i++ ) + for ( i = 0; i < (int)pCut0->nLeaves; i++ ) { - iObj = Abc_Lit2Var(pCuts[0]->pLeaves[i]); + iObj = Abc_Lit2Var(pCut0->pLeaves[i]); Vec_IntPush( &p->vObjPresUsed, iObj ); p->pObjPres[iObj] = pCut->nLeaves; - pCut->pLeaves[pCut->nLeaves++] = pCuts[0]->pLeaves[i]; + pCut->pLeaves[pCut->nLeaves++] = pCut0->pLeaves[i]; } // remaining cuts - for ( c = 1; pCuts[c] && c < 3; c++ ) + for ( c = 1; c < 3; c++ ) { + pTemp = (c == 1) ? pCut1 : pCut2; + if ( pTemp == NULL ) + break; p->uPermMask[c] = 0x3FFFF; // 18 bits p->uComplMask[c] = 0; - for ( i = 0; i < (int)pCuts[c]->nLeaves; i++ ) + for ( i = 0; i < (int)pTemp->nLeaves; i++ ) { - iObj = Abc_Lit2Var(pCuts[c]->pLeaves[i]); + iObj = Abc_Lit2Var(pTemp->pLeaves[i]); if ( p->pObjPres[iObj] == (unsigned char)0xFF ) { if ( (int)pCut->nLeaves == p->nLutSize ) - return 0; + return NULL; Vec_IntPush( &p->vObjPresUsed, iObj ); p->pObjPres[iObj] = pCut->nLeaves; - pCut->pLeaves[pCut->nLeaves++] = pCuts[c]->pLeaves[i]; + pCut->pLeaves[pCut->nLeaves++] = pTemp->pLeaves[i]; } else fDisj = 0; p->uPermMask[c] ^= (((i & 7) ^ 7) << (3*p->pObjPres[iObj])); - assert( Abc_Lit2Var(pCuts[c]->pLeaves[i]) == Abc_Lit2Var(pCut->pLeaves[p->pObjPres[iObj]]) ); - if ( pCuts[c]->pLeaves[i] != pCut->pLeaves[p->pObjPres[iObj]] ) + assert( Abc_Lit2Var(pTemp->pLeaves[i]) == Abc_Lit2Var(pCut->pLeaves[p->pObjPres[iObj]]) ); + if ( pTemp->pLeaves[i] != pCut->pLeaves[p->pObjPres[iObj]] ) p->uComplMask[c] |= (1 << p->pObjPres[iObj]); } // Mpm_ManPrintPerm( p->uPermMask[c] ); printf( "\n" ); } // printf( "%d", fDisj ); - pCut->hNext = 0; - pCut->iFunc = 0; pCut->iFunc = ~pCut->iFunc; - pCut->fUseless = 0; - pCut->fCompl = 0; + if ( pCut1 == NULL ) + { + pCut->hNext = 0; + pCut->iFunc = pCut0->iFunc; + pCut->fUseless = pCut0->fUseless; + pCut->fCompl = pCut0->fCompl; + } + else + { + pCut->hNext = 0; + pCut->iFunc = 0; pCut->iFunc = ~pCut->iFunc; + pCut->fUseless = 0; + pCut->fCompl = 0; + } p->nCutsMerged++; p->nCutsMergedAll++; if ( p->pPars->fUseTruth ) Vec_IntSelectSort( pCut->pLeaves, pCut->nLeaves ); - return 1; + return pCut; } - -static inline int Mpm_ManDeriveCutNew( Mpm_Man_t * p, Mig_Obj_t * pObj, Mpm_Cut_t ** pCuts, int Required ) +static inline int Mpm_ManExploreNewCut( Mpm_Man_t * p, Mig_Obj_t * pObj, Mpm_Cut_t * pCut0, Mpm_Cut_t * pCut1, Mpm_Cut_t * pCut2, int Required ) { - Mpm_Uni_t * pUnit = (Mpm_Uni_t *)Vec_PtrEntryLast( &p->vFreeUnits ); - Mpm_Cut_t * pCut = &pUnit->pCut; + Mpm_Cut_t * pCut; int ArrTime; + #ifdef MIG_RUNTIME abctime clk = clock(); #endif - - if ( !Mpm_ObjDeriveCut( p, pCuts, pCut ) ) + pCut = Mpm_ManMergeCuts( p, pCut0, pCut1, pCut2 ); + if ( pCut == NULL ) { #ifdef MIG_RUNTIME p->timeMerge += clock() - clk; @@ -535,10 +418,10 @@ p->timeMerge += clock() - clk; // derive truth table if ( p->pPars->fUseTruth ) - Mpm_CutComputeTruth( p, pCut, pCuts[0], pCuts[1], pCuts[2], Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ); + Mpm_CutComputeTruth( p, pCut, pCut0, pCut1, pCut2, Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ); else if ( p->pPars->fUseDsd ) { - if ( !Mpm_CutComputeDsd6( p, pCut, pCuts[0], pCuts[1], pCuts[2], Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ) ) + if ( !Mpm_CutComputeDsd6( p, pCut, pCut0, pCut1, pCut2, Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ) ) return 1; } @@ -578,20 +461,123 @@ p->timeStore += Abc_Clock() - clk; */ return 1; } + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Mpm_ObjRecycleCuts( Mpm_Man_t * p, Mig_Obj_t * pObj ) +{ + Mpm_Cut_t * pCut; + int hCut, hNext; + Mpm_ObjForEachCutSafe( p, pObj, hCut, pCut, hNext ) + Mmr_StepRecycle( p->pManCuts, hCut ); + Mpm_ObjSetCutList( p, pObj, 0 ); +} +static inline void Mpm_ObjDerefFaninCuts( Mpm_Man_t * p, Mig_Obj_t * pObj ) +{ + Mig_Obj_t * pFanin; + int i; + Mig_ObjForEachFanin( pObj, pFanin, i ) + if ( Mig_ObjIsNode(pFanin) && Mig_ObjMigRefDec(p, pFanin) == 0 ) + Mpm_ObjRecycleCuts( p, pFanin ); + pFanin = Mig_ObjSibl(pObj); + if ( pFanin && Mig_ObjMigRefDec(p, pFanin) == 0 ) + Mpm_ObjRecycleCuts( p, pFanin ); + if ( Mig_ObjMigRefNum(p, pObj) == 0 ) + Mpm_ObjRecycleCuts( p, pObj ); +} +static inline void Mpm_ObjCollectFaninsAndSigns( Mpm_Man_t * p, Mig_Obj_t * pObj, int i ) +{ + Mpm_Cut_t * pCut; + int hCut, nCuts = 0; + Mpm_ObjForEachCut( p, pObj, hCut, pCut ) + { + p->pCuts[i][nCuts] = pCut; + p->pSigns[i][nCuts++] = Mpm_CutGetSign( pCut ); + } + p->nCuts[i] = nCuts; +} +static inline void Mpm_ObjPrepareFanins( Mpm_Man_t * p, Mig_Obj_t * pObj ) +{ + Mig_Obj_t * pFanin; + int i; + Mig_ObjForEachFanin( pObj, pFanin, i ) + Mpm_ObjCollectFaninsAndSigns( p, pFanin, i ); +} +// create storage from cuts at the node +void Mpm_ObjAddChoiceCutsToStore( Mpm_Man_t * p, Mig_Obj_t * pRoot, Mig_Obj_t * pObj, int ReqTime ) +{ + Mpm_Cut_t * pCut; + int hCut, hNext, ArrTime; + int fCompl = Mig_ObjPhase(pRoot) ^ Mig_ObjPhase(pObj); + Mpm_ObjForEachCutSafe( p, pObj, hCut, pCut, hNext ) + { + if ( Abc_Lit2Var(pCut->pLeaves[0]) == Mig_ObjId(pObj) ) + continue; + ArrTime = Mpm_CutGetArrTime( p, pCut ); + if ( ArrTime > ReqTime ) + continue; + pCut->fCompl ^= fCompl; + pCut = Mpm_ManMergeCuts( p, pCut, NULL, NULL ); + Mpm_ObjAddCutToStore( p, pCut, ArrTime ); + } +} +// create cuts at the node from storage +void Mpm_ObjTranslateCutsFromStore( Mpm_Man_t * p, Mig_Obj_t * pObj ) +{ + Mpm_Cut_t * pCut = NULL; + Mpm_Uni_t * pUnit; + int i, *pList = Mpm_ObjCutListP( p, pObj ); + assert( p->nCutStore > 0 && p->nCutStore <= p->nNumCuts ); + assert( *pList == 0 ); + // translate cuts + for ( i = 0; i < p->nCutStore; i++ ) + { + pUnit = p->pCutStore[i]; + *pList = Mpm_CutCreate( p, &pUnit->pCut, &pCut ); + pList = &pCut->hNext; + Vec_PtrPush( &p->vFreeUnits, pUnit ); + } + assert( Vec_PtrSize(&p->vFreeUnits) == p->nNumCuts + 1 ); + if ( p->nCutStore == 1 && pCut->nLeaves < 2 ) + *pList = 0; + else + *pList = Mpm_CutCreateUnit( p, Mig_ObjId(pObj) ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ int Mpm_ManDeriveCuts( Mpm_Man_t * p, Mig_Obj_t * pObj ) { -// static int Flag = 0; - Mpm_Cut_t * pCuts[3]; + Mpm_Cut_t * pCut0, * pCut1, * pCut2; int Required = Mpm_ObjRequired( p, pObj ); int hCutBest = Mpm_ObjCutBest( p, pObj ); int c0, c1, c2; - p->nCutStore = 0; - #ifdef MIG_RUNTIME - abctime clk; +abctime clk; #endif + assert( Vec_PtrSize( &p->vFreeUnits ) == p->nNumCuts + 1 ); assert( Mpm_ObjCutList(p, pObj) == 0 ); + p->nCutStore = 0; if ( hCutBest > 0 ) // cut list is assigned { Mpm_Cut_t * pCut = Mpm_ObjCutBestP( p, pObj ); @@ -600,54 +586,43 @@ int Mpm_ManDeriveCuts( Mpm_Man_t * p, Mig_Obj_t * pObj ) if ( Times > Required ) printf( "Arrival time (%d) exceeds required time (%d) at object %d.\n", Times, Required, Mig_ObjId(pObj) ); if ( p->fMainRun ) - Mpm_ObjAddCutToStore( p, pCut, Times ); + Mpm_ObjAddCutToStore( p, Mpm_ManMergeCuts(p, pCut, NULL, NULL), Times ); else Mpm_ObjSetTime( p, pObj, Times ); } // start storage with choice cuts - if ( p->pMig->vSibls.nSize && Mig_ObjSiblId(pObj) ) - Mpm_ObjAddChoiceCutsToStore( p, Mig_ObjSibl(pObj), Required ); - // compute signatures for fanin cuts + if ( Mig_ManChoiceNum(p->pMig) && Mig_ObjSiblId(pObj) ) + Mpm_ObjAddChoiceCutsToStore( p, pObj, Mig_ObjSibl(pObj), Required ); + #ifdef MIG_RUNTIME clk = Abc_Clock(); #endif Mpm_ObjPrepareFanins( p, pObj ); -#ifdef MIG_RUNTIME -p->timeFanin += Abc_Clock() - clk; -#endif - // compute cuts in the internal storage -#ifdef MIG_RUNTIME -clk = Abc_Clock(); -#endif if ( Mig_ObjIsNode2(pObj) ) { // go through cut pairs - pCuts[2] = NULL; - for ( c0 = 0; c0 < p->nCuts[0] && (pCuts[0] = p->pCuts[0][c0]); c0++ ) - for ( c1 = 0; c1 < p->nCuts[1] && (pCuts[1] = p->pCuts[1][c1]); c1++ ) + for ( c0 = 0; c0 < p->nCuts[0] && (pCut0 = p->pCuts[0][c0]); c0++ ) + for ( c1 = 0; c1 < p->nCuts[1] && (pCut1 = p->pCuts[1][c1]); c1++ ) if ( Abc_TtCountOnes(p->pSigns[0][c0] | p->pSigns[1][c1]) <= p->nLutSize ) - if ( !Mpm_ManDeriveCutNew( p, pObj, pCuts, Required ) ) + if ( !Mpm_ManExploreNewCut( p, pObj, pCut0, pCut1, NULL, Required ) ) goto finish; } else if ( Mig_ObjIsNode3(pObj) ) { // go through cut triples - for ( c0 = 0; c0 < p->nCuts[0] && (pCuts[0] = p->pCuts[0][c0]); c0++ ) - for ( c1 = 0; c1 < p->nCuts[1] && (pCuts[1] = p->pCuts[1][c1]); c1++ ) - for ( c2 = 0; c2 < p->nCuts[2] && (pCuts[2] = p->pCuts[2][c2]); c2++ ) + for ( c0 = 0; c0 < p->nCuts[0] && (pCut0 = p->pCuts[0][c0]); c0++ ) + for ( c1 = 0; c1 < p->nCuts[1] && (pCut1 = p->pCuts[1][c1]); c1++ ) + for ( c2 = 0; c2 < p->nCuts[2] && (pCut2 = p->pCuts[2][c2]); c2++ ) if ( Abc_TtCountOnes(p->pSigns[0][c0] | p->pSigns[1][c1] | p->pSigns[2][c2]) <= p->nLutSize ) - if ( !Mpm_ManDeriveCutNew( p, pObj, pCuts, Required ) ) + if ( !Mpm_ManExploreNewCut( p, pObj, pCut0, pCut1, pCut2, Required ) ) goto finish; } else assert( 0 ); #ifdef MIG_RUNTIME p->timeDerive += Abc_Clock() - clk; #endif + finish: - // transform internal storage into regular cuts -// if ( Flag == 0 && p->nCutStore == p->nNumCuts - 1 ) -// Flag = 1, Mpm_CutPrintAll( p ); -// printf( "%d ", p->nCutStore ); // save best cut assert( p->nCutStore > 0 ); if ( p->pCutStore[0]->mTime <= Required ) @@ -660,13 +635,11 @@ 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 ); // transform internal storage into regular cuts - Mpm_ObjTranslateCutsFromStore( p, pObj, Mig_ObjRefNum(pObj) > 0 ); + Mpm_ObjTranslateCutsFromStore( p, pObj ); // dereference fanin cuts and reference node Mpm_ObjDerefFaninCuts( p, pObj ); return 1; @@ -823,10 +796,17 @@ void Mpm_ManPerformRound( Mpm_Man_t * p ) { Mig_Obj_t * pObj; abctime clk = Abc_Clock(); + int i; + // copy references + assert( Vec_IntSize(&p->vMigRefs) == Vec_IntSize(&p->pMig->vRefs) ); + memcpy( Vec_IntArray(&p->vMigRefs), Vec_IntArray(&p->pMig->vRefs), sizeof(int) * Mig_ManObjNum(p->pMig) ); + Mig_ManForEachCo( p->pMig, pObj, i ) + Mig_ObjMigRefDec( p, Mig_ObjFanin0(pObj) ); + // derive cuts p->nCutsMerged = 0; - Mpm_ManSetMigRefs( p ); Mig_ManForEachNode( p->pMig, pObj ) Mpm_ManDeriveCuts( p, pObj ); + assert( Mig_ManCandNum(p->pMig) == p->pManCuts->nEntries ); Mpm_ManFinalizeRound( p ); printf( "Del =%5d. Ar =%8d. Edge =%8d. Cut =%10d. Max =%8d. Tru =%8d. Small =%6d. ", p->GloRequired, p->GloArea, p->GloEdge, diff --git a/src/map/mpm/mpmMig.c b/src/map/mpm/mpmMig.c index 4c664733..e51883bd 100644 --- a/src/map/mpm/mpmMig.c +++ b/src/map/mpm/mpmMig.c @@ -120,23 +120,18 @@ int Mig_ManMuxNum( Mig_Man_t * p ) SeeAlso [] ***********************************************************************/ -void Mig_ManSetRefs( Mig_Man_t * p, int fSkipCos ) +void Mig_ManSetRefs( Mig_Man_t * p ) { Mig_Obj_t * pObj; int i, iFanin; // increment references Vec_IntFill( &p->vRefs, Mig_ManObjNum(p), 0 ); - Mig_ManForEachNode( p, pObj ) + Mig_ManForEachObj( p, pObj ) + { Mig_ObjForEachFaninId( pObj, iFanin, i ) Vec_IntAddToEntry( &p->vRefs, iFanin, 1 ); - if ( !fSkipCos ) - { - // and CO references - Mig_ManForEachCo( p, pObj, i ) - Vec_IntAddToEntry( &p->vRefs, Mig_ObjFaninId(pObj, 0), 1 ); - // check that internal nodes have fanins - Mig_ManForEachNode( p, pObj ) - assert( Vec_IntEntry(&p->vRefs, Mig_ObjId(pObj)) > 0 ); + if ( Mig_ObjSiblId(pObj) ) + Vec_IntAddToEntry( &p->vRefs, Mig_ObjSiblId(pObj), 1 ); } } diff --git a/src/map/mpm/mpmMig.h b/src/map/mpm/mpmMig.h index 1acbac8f..0f1cd263 100644 --- a/src/map/mpm/mpmMig.h +++ b/src/map/mpm/mpmMig.h @@ -64,6 +64,7 @@ struct Mig_Man_t_ char * pName; // name int nObjs; // number of objects int nRegs; // number of flops + int nChoices; // number of choices Vec_Ptr_t vPages; // memory pages Vec_Int_t vCis; // CI IDs Vec_Int_t vCos; // CO IDs @@ -109,6 +110,7 @@ static inline int Mig_ManRegNum( Mig_Man_t * p ) { return p->nRegs static inline int Mig_ManObjNum( Mig_Man_t * p ) { return p->nObjs; } static inline int Mig_ManNodeNum( Mig_Man_t * p ) { return p->nObjs - Vec_IntSize(&p->vCis) - Vec_IntSize(&p->vCos) - 1; } static inline int Mig_ManCandNum( Mig_Man_t * p ) { return Mig_ManCiNum(p) + Mig_ManNodeNum(p); } +static inline int Mig_ManChoiceNum( Mig_Man_t * p ) { return p->nChoices; } static inline void Mig_ManSetRegNum( Mig_Man_t * p, int v ) { p->nRegs = v; } static inline Mig_Obj_t * Mig_ManPage( Mig_Man_t * p, int v ) { return (Mig_Obj_t *)Vec_PtrEntry(&p->vPages, Mig_IdPage(v)); } @@ -147,7 +149,7 @@ static inline void Mig_ObjSetId( Mig_Obj_t * p, int v ) { static inline int Mig_ObjCioId( Mig_Obj_t * p ) { assert( Mig_ObjIsTerm(p) ); return Mig_FanId( p, 2 ); } static inline void Mig_ObjSetCioId( Mig_Obj_t * p, int v ) { assert( Mig_FanIsNone(p, 1) ); Mig_FanSetId( p, 2, v ); } static inline int Mig_ObjPhase( Mig_Obj_t * p ) { return Mig_FanCompl( p, 3 ); } -static inline void Mig_ObjSetPhase( Mig_Obj_t * p, int v ) { Mig_FanSetCompl( p, 3, 1 ); } +static inline void Mig_ObjSetPhase( Mig_Obj_t * p, int v ) { Mig_FanSetCompl( p, 3, v ); } static inline Mig_Man_t * Mig_ObjMan( Mig_Obj_t * p ) { return *((Mig_Man_t**)(p - Mig_IdCell(Mig_ObjId(p)) - 1)); } //static inline Mig_Obj_t ** Mig_ObjPageP( Mig_Obj_t * p ) { return *((Mig_Obj_t***)(p - Mig_IdCell(Mig_ObjId(p))) - 1);} @@ -185,8 +187,9 @@ static inline int Mig_ObjWhatFanin( Mig_Obj_t * p, int i ) { static inline void Mig_ObjSetFaninLit( Mig_Obj_t * p, int i, int l ) { assert( l >= 0 && (l >> 1) < Mig_ObjId(p) ); Mig_FanSetId(p, i, Abc_Lit2Var(l)); Mig_FanSetCompl(p, i, Abc_LitIsCompl(l)); } static inline int Mig_ObjSiblId( Mig_Obj_t * p ) { return Vec_IntSize(&Mig_ObjMan(p)->vSibls) == 0 ? 0: Vec_IntEntry(&Mig_ObjMan(p)->vSibls, Mig_ObjId(p)); } -static inline Mig_Obj_t * Mig_ObjSibl( Mig_Obj_t * p ) { return Mig_ObjSiblId(p) == 0 ? NULL: Mig_ObjObj(p, Mig_ObjSiblId(p)); } -static inline int Mig_ObjRefNum( Mig_Obj_t * p ) { return Vec_IntEntry(&Mig_ObjMan(p)->vRefs, Mig_ObjId(p)); } +static inline void Mig_ObjSetSiblId( Mig_Obj_t * p, int s ) { assert( s > 0 && Mig_ObjId(p) > s ); Vec_IntWriteEntry( &Mig_ObjMan(p)->vSibls, Mig_ObjId(p), s ); } +static inline Mig_Obj_t * Mig_ObjSibl( Mig_Obj_t * p ) { return Mig_ObjSiblId(p) == 0 ? NULL: Mig_ObjObj(p, Mig_ObjSiblId(p)); } +static inline int Mig_ObjRefNum( Mig_Obj_t * p ) { return Vec_IntEntry(&Mig_ObjMan(p)->vRefs, Mig_ObjId(p)); } static inline void Mig_ManCleanCopy( Mig_Man_t * p ) { if ( p->vCopies.pArray == NULL ) Vec_IntFill( &p->vCopies, Mig_ManObjNum(p), -1 ); } static inline int Mig_ObjCopy( Mig_Obj_t * p ) { return Vec_IntSize(&Mig_ObjMan(p)->vCopies) == 0 ? -1: Vec_IntEntry(&Mig_ObjMan(p)->vCopies, Mig_ObjId(p)); } @@ -341,7 +344,7 @@ static inline int Mig_ManAppendMaj( Mig_Man_t * p, int iLit0, int iLit1, int iLi /*=== mpmMig.c ===========================================================*/ extern Mig_Man_t * Mig_ManStart(); extern void Mig_ManStop( Mig_Man_t * p ); -extern void Mig_ManSetRefs( Mig_Man_t * p, int fSkipCos ); +extern void Mig_ManSetRefs( Mig_Man_t * p ); extern int Mig_ManAndNum( Mig_Man_t * p ); extern int Mig_ManXorNum( Mig_Man_t * p ); extern int Mig_ManMuxNum( Mig_Man_t * p ); -- cgit v1.2.3