/**CFile****************************************************************
FileName [mpmMap.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Configurable technology mapper.]
Synopsis [Mapping algorithm.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 1, 2013.]
Revision [$Id: mpmMap.c,v 1.00 2013/06/01 00:00:00 alanmi Exp $]
***********************************************************************/
#include "mpmInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
//#define MIG_RUNTIME
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Cut manipulation.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Mpm_CutAlloc( Mpm_Man_t * p, int nLeaves, Mpm_Cut_t ** ppCut )
{
int hHandle = Mmr_StepFetch( p->pManCuts, Mpm_CutWordNum(nLeaves) );
*ppCut = (Mpm_Cut_t *)Mmr_StepEntry( p->pManCuts, hHandle );
(*ppCut)->nLeaves = nLeaves;
(*ppCut)->hNext = 0;
(*ppCut)->fUseless = 0;
(*ppCut)->fCompl = 0;
return hHandle;
}
static inline int Mpm_CutCreateZero( Mpm_Man_t * p )
{
Mpm_Cut_t * pCut;
int hCut = Mpm_CutAlloc( p, 0, &pCut );
pCut->iFunc = 0; // const0
return hCut;
}
static inline int Mpm_CutCreateUnit( Mpm_Man_t * p, int Id )
{
Mpm_Cut_t * pCut;
int hCut = Mpm_CutAlloc( p, 1, &pCut );
pCut->iFunc = Abc_Var2Lit( p->funcVar0, 0 ); // var
pCut->pLeaves[0] = Abc_Var2Lit( Id, 0 );
return hCut;
}
static inline int Mpm_CutCreate( Mpm_Man_t * p, Mpm_Cut_t * pUni, Mpm_Cut_t ** ppCut )
{
int hCutNew = Mpm_CutAlloc( p, pUni->nLeaves, ppCut );
(*ppCut)->iFunc = pUni->iFunc;
(*ppCut)->fCompl = pUni->fCompl;
(*ppCut)->fUseless = pUni->fUseless;
(*ppCut)->nLeaves = pUni->nLeaves;
memcpy( (*ppCut)->pLeaves, pUni->pLeaves, sizeof(int) * pUni->nLeaves );
return hCutNew;
}
static inline int Mpm_CutDup( Mpm_Man_t * p, Mpm_Cut_t * pCut, int fCompl )
{
Mpm_Cut_t * pCutNew;
int hCutNew = Mpm_CutAlloc( p, pCut->nLeaves, &pCutNew );
pCutNew->iFunc = Abc_LitNotCond( pCut->iFunc, fCompl );
pCutNew->fUseless = pCut->fUseless;
pCutNew->nLeaves = pCut->nLeaves;
memcpy( pCutNew->pLeaves, pCut->pLeaves, sizeof(int) * pCut->nLeaves );
return hCutNew;
}
static inline int Mpm_CutCopySet( Mpm_Man_t * p, Mig_Obj_t * pObj, int fCompl )
{
Mpm_Cut_t * pCut;
int hCut, iList = 0, * pList = &iList;
Mpm_ObjForEachCut( p, pObj, hCut, pCut )
{
*pList = Mpm_CutDup( p, pCut, fCompl );
pList = &Mpm_CutFetch( p, *pList )->hNext;
}
*pList = 0;
return iList;
}
void Mpm_CutPrint( Mpm_Cut_t * pCut )
{
int 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 )
{
int i;
for ( i = 0; i < p->nCutStore; i++ )
{
printf( "%2d : ", i );
Mpm_CutPrint( &p->pCutStore[i]->pCut );
}
}
static inline int Mpm_CutFindLeaf( Mpm_Cut_t * pNew, int iObj )
{
int i;
for ( i = 0; i < (int)pNew->nLeaves; i++ )
if ( Abc_Lit2Var(pNew->pLeaves[i]) == iObj )
return i;
return i;
}
static inline int Mpm_CutIsContained( Mpm_Man_t * p, Mpm_Cut_t * pBase, Mpm_Cut_t * pCut ) // check if pCut is contained pBase
{
int i;
for ( i = 0; i < (int)pCut->nLeaves; i++ )
if ( Mpm_CutFindLeaf( pBase, Abc_Lit2Var(pCut->pLeaves[i]) ) == (int)pBase->nLeaves )
return 0;
return 1;
}
/**Function*************************************************************
Synopsis [Cut attibutes.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Mpm_CutGetArea( Mpm_Man_t * p, Mpm_Cut_t * pCut )
{
if ( p->pPars->fMap4Cnf )
return MPM_UNIT_AREA * p->pDsd6[Abc_Lit2Var(pCut->iFunc)].nClauses;
if ( p->pPars->fMap4Aig )
return MPM_UNIT_AREA * p->pDsd6[Abc_Lit2Var(pCut->iFunc)].nAnds;
if ( p->pPars->fMap4Gates )
return MPM_UNIT_AREA * 1;
return p->pLibLut->pLutAreas[pCut->nLeaves];
}
static inline word Mpm_CutGetSign( Mpm_Cut_t * pCut )
{
int i, iLeaf;
word uSign = 0;
Mpm_CutForEachLeafId( pCut, iLeaf, i )
uSign |= ((word)1 << (iLeaf & 0x3F));
return uSign;
}
static inline int Mpm_CutGetArrTime( Mpm_Man_t * p, Mpm_Cut_t * pCut )
{
int * pmTimes = Vec_IntArray( &p->vTimes );
int * pDelays = p->pLibLut->pLutDelays[pCut->nLeaves];
int i, iLeaf, ArrTime = 0;
Mpm_CutForEachLeafId( pCut, iLeaf, i )
ArrTime = Abc_MaxInt( ArrTime, pmTimes[iLeaf] + pDelays[i] );
return ArrTime;
}
static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int ArrTime )
{
int * pMigRefs = Vec_IntArray( &p->vMigRefs );
int * pMapRefs = Vec_IntArray( &p->vMapRefs );
int * pEstRefs = Vec_IntArray( &p->vEstRefs );
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);
assert( &pUnit->pCut == pCut );
pUnit->mTime = ArrTime;
pUnit->mArea = Mpm_CutGetArea( p, pCut );
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
{
pUnit->mArea += pmArea[iLeaf];
pUnit->mEdge += pmEdge[iLeaf];
}
else
{
assert( pEstRefs[iLeaf] > 0 );
pUnit->mArea += MPM_UNIT_REFS * pmArea[iLeaf] / pEstRefs[iLeaf];
pUnit->mEdge += MPM_UNIT_REFS * pmEdge[iLeaf] / pEstRefs[iLeaf];
pUnit->mAveRefs += p->fMainRun ? pMapRefs[iLeaf] : pMigRefs[iLeaf];
}
pUnit->uSign |= ((word)1 << (iLeaf & 0x3F));
}
pUnit->mAveRefs = pUnit->mAveRefs * MPM_UNIT_EDGE / Abc_MaxInt(pCut->nLeaves, 1);
assert( pUnit->mTime <= 0x3FFFFFFF );
assert( pUnit->mArea <= 0x3FFFFFFF );
assert( pUnit->mEdge <= 0x3FFFFFFF );
return pUnit;
}
/**Function*************************************************************
Synopsis [Compares cut against those present in the store.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Mpm_ObjAddCutToStore( Mpm_Man_t * p, Mpm_Cut_t * pCut, int ArrTime )
{
int fEnableContainment = 1;
Mpm_Uni_t * pUnit, * pUnitNew;
int k, iPivot, last;
// create new unit
#ifdef MIG_RUNTIME
abctime clk;
clk = Abc_Clock();
#endif
pUnitNew = Mpm_CutSetupInfo( p, pCut, ArrTime );
#ifdef MIG_RUNTIME
p->timeEval += Abc_Clock() - clk;
#endif
// special case when the cut store is empty
if ( p->nCutStore == 0 )
{
p->pCutStore[p->nCutStore++] = pUnitNew;
Vec_PtrPop( &p->vFreeUnits );
return 1;
}
// special case when the cut store is full and last cut is better than new cut
if ( p->nCutStore == p->nNumCuts-1 && p->pCutCmp(pUnitNew, p->pCutStore[p->nCutStore-1]) > 0 )
return 0;
// find place of the given cut in the store
assert( p->nCutStore <= p->nNumCuts );
for ( iPivot = p->nCutStore - 1; iPivot >= 0; iPivot-- )
if ( p->pCutCmp(pUnitNew, p->pCutStore[iPivot]) > 0 ) // iPivot-th cut is better than new cut
break;
if ( fEnableContainment )
{
#ifdef MIG_RUNTIME
clk = Abc_Clock();
#endif
// filter this cut using other cuts
for ( k = 0; k <= iPivot; k++ )
{
pUnit = p->pCutStore[k];
if ( pUnitNew->pCut.nLeaves >= pUnit->pCut.nLeaves &&
(pUnitNew->uSign & pUnit->uSign) == pUnit->uSign &&
Mpm_CutIsContained(p, &pUnitNew->pCut, &pUnit->pCut) )
{
#ifdef MIG_RUNTIME
p->timeCompare += Abc_Clock() - clk;
#endif
return 0;
}
}
}
// special case when the best cut is useless while the new cut is not
if ( p->pCutStore[0]->pCut.fUseless && !pUnitNew->pCut.fUseless )
iPivot = -1;
// add the cut to storage
assert( pUnitNew == (Mpm_Uni_t *)Vec_PtrEntryLast(&p->vFreeUnits) );
Vec_PtrPop( &p->vFreeUnits );
// insert this cut at location iPivot
iPivot++;
for ( k = p->nCutStore++; k > iPivot; k-- )
p->pCutStore[k] = p->pCutStore[k-1];
p->pCutStore[iPivot] = pUnitNew;
if ( fEnableContainment )
{
// filter other cuts using this cut
for ( k = last = iPivot+1; k < p->nCutStore; k++ )
{
pUnit = p->pCutStore[k];
if ( pUnitNew->pCut.nLeaves <= pUnit->pCut.nLeaves &&
(pUnitNew->uSign & pUnit->uSign) == pUnitNew->uSign &&
Mpm_CutIsContained(p, &pUnit->pCut, &pUnitNew->pCut) )
{
Vec_PtrPush( &p->vFreeUnits, pUnit );
continue;
}
p->pCutStore[last++] = p->pCutStore[k];
}
p->nCutStore = last;
#ifdef MIG_RUNTIME
p->timeCompare += Abc_Clock() - clk;
#endif
}
// remove the last cut if too many
if ( p->nCutStore == p->nNumCuts )
Vec_PtrPush( &p->vFreeUnits, p->pCutStore[--p->nCutStore] );
assert( p->nCutStore < p->nNumCuts );
return 1;
}
/**Function*************************************************************
Synopsis [Cut enumeration.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
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, iPlace;
// base cut
memcpy( pCut->pLeaves, pCut0->pLeaves, sizeof(int) * pCut0->nLeaves );
pCut->nLeaves = pCut0->nLeaves;
// remaining cuts
if ( p->pPars->fUseDsd )
{
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)pTemp->nLeaves; i++ )
{
iPlace = Mpm_CutFindLeaf( pCut, Abc_Lit2Var(pTemp->pLeaves[i]) );
if ( iPlace == (int)pCut->nLeaves )
{
if ( (int)pCut->nLeaves == p->nLutSize )
return NULL;
pCut->pLeaves[pCut->nLeaves++] = pTemp->pLeaves[i];
}
p->uPermMask[c] ^= (((i & 7) ^ 7) << (3*iPlace));
if ( pTemp->pLeaves[i] != pCut->pLeaves[iPlace] )
p->uComplMask[c] |= (1 << iPlace);
}
}
}
else
{
for ( c = 1; c < 3; c++ )
{
pTemp = (c == 1) ? pCut1 : pCut2;
if ( pTemp == NULL )
break;
for ( i = 0; i < (int)pTemp->nLeaves; i++ )
{
iPlace = Mpm_CutFindLeaf( pCut, Abc_Lit2Var(pTemp->pLeaves[i]) );
if ( iPlace == (int)pCut->nLeaves )
{
if ( (int)pCut->nLeaves == p->nLutSize )
return NULL;
pCut->pLeaves[pCut->nLeaves++] = pTemp->pLeaves[i];
}
}
}
}
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 pCut;
}
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_Cut_t * pCut;
int ArrTime;
#ifdef MIG_RUNTIME
abctime clk = clock();
#endif
if ( pCut0->nLeaves >= pCut1->nLeaves )
{
pCut = Mpm_ManMergeCuts( p, pCut0, pCut1, pCut2 );
#ifdef MIG_RUNTIME
p->timeMerge += clock() - clk;
#endif
if ( pCut == NULL )
return 1;
if ( p->pPars->fUseTruth )
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, pCut0, pCut1, pCut2, Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ) )
return 1;
}
}
else
{
pCut = Mpm_ManMergeCuts( p, pCut1, pCut0, pCut2 );
#ifdef MIG_RUNTIME
p->timeMerge += clock() - clk;
#endif
if ( pCut == NULL )
return 1;
if ( p->pPars->fUseTruth )
Mpm_CutComputeTruth( p, pCut, pCut1, pCut0, pCut2, Mig_ObjFaninC1(pObj), Mig_ObjFaninC0(pObj), 1 ^ Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) );
else if ( p->pPars->fUseDsd )
{
if ( !Mpm_CutComputeDsd6( p, pCut, pCut1, pCut0, pCut2, Mig_ObjFaninC1(pObj), Mig_ObjFaninC0(pObj), 1 ^ Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ) )
return 1;
}
}
#ifdef MIG_RUNTIME
clk = clock();
#endif
ArrTime = Mpm_CutGetArrTime( p, pCut );
#ifdef MIG_RUNTIME
p->timeEval += clock() - clk;
#endif
if ( p->fMainRun && ArrTime > Required )
return 1;
#ifdef MIG_RUNTIME
clk = Abc_Clock();
#endif
Mpm_ObjAddCutToStore( p, pCut, ArrTime );
#ifdef MIG_RUNTIME
p->timeStore += Abc_Clock() - clk;
#endif
/*
// return 0 if const or buffer cut is derived - reset all cuts to contain only one --- does not work
// if ( pCut->nLeaves < 2 && p->nCutStore == 1 )
// return 0;
if ( pCut->nLeaves < 2 )
{
int i;
assert( p->nCutStore >= 1 );
for ( i = 1; i < p->nCutStore; i++ )
Vec_PtrPush( &p->vFreeUnits, p->pCutStore[i] );
p->nCutStore = 1;
return 0;
}
*/
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 )
{
Mpm_Cut_t * pCut0, * pCut1, * pCut2;
int Required = Mpm_ObjRequired( p, pObj );
int hCutBest = Mpm_ObjCutBest( p, pObj );
int c0, c1, c2;
#ifdef MIG_RUNTIME
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 );
int Times = Mpm_CutGetArrTime( p, pCut );
assert( pCut->hNext == 0 );
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, Mpm_ManMergeCuts(p, pCut, NULL, NULL), Times );
else
Mpm_ObjSetTime( p, pObj, Times );
}
// start storage with choice 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 );
if ( Mig_ObjIsNode2(pObj) )
{
// go through cut pairs
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_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] && (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_ManExploreNewCut( p, pObj, pCut0, pCut1, pCut2, Required ) )
goto finish;
}
else assert( 0 );
#ifdef MIG_RUNTIME
p->timeDerive += Abc_Clock() - clk;
#endif
finish:
// save best cut
assert( p->nCutStore > 0 );
if ( p->pCutStore[0]->mTime <= Required )
{
Mpm_Cut_t * pCut;
if ( hCutBest )
Mmr_StepRecycle( p->pManCuts, hCutBest );
hCutBest = Mpm_CutCreate( p, &p->pCutStore[0]->pCut, &pCut );
Mpm_ObjSetCutBest( p, pObj, hCutBest );
Mpm_ObjSetTime( p, pObj, p->pCutStore[0]->mTime );
Mpm_ObjSetArea( p, pObj, p->pCutStore[0]->mArea );
Mpm_ObjSetEdge( p, pObj, p->pCutStore[0]->mEdge );
}
else assert( !p->fMainRun );
assert( hCutBest > 0 );
// transform internal storage into regular cuts
Mpm_ObjTranslateCutsFromStore( p, pObj );
// dereference fanin cuts and reference node
Mpm_ObjDerefFaninCuts( p, pObj );
return 1;
}
/**Function*************************************************************
Synopsis [Required times.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Mpm_ManFindArrivalMax( Mpm_Man_t * p )
{
int * pmTimes = Vec_IntArray( &p->vTimes );
Mig_Obj_t * pObj;
int i, ArrMax = 0;
Mig_ManForEachCo( p->pMig, pObj, i )
ArrMax = Abc_MaxInt( ArrMax, pmTimes[ Mig_ObjFaninId0(pObj) ] );
return ArrMax;
}
static inline void Mpm_ManFinalizeRound( Mpm_Man_t * p )
{
int * pMapRefs = Vec_IntArray( &p->vMapRefs );
int * pRequired = Vec_IntArray( &p->vRequireds );
Mig_Obj_t * pObj;
Mpm_Cut_t * pCut;
int * pDelays;
int i, iLeaf;
p->GloArea = 0;
p->GloEdge = 0;
p->GloRequired = Mpm_ManFindArrivalMax(p);
if ( p->pPars->DelayTarget != -1 )
p->GloRequired = Abc_MaxInt( p->GloRequired, p->pPars->DelayTarget );
Mpm_ManCleanMapRefs( p );
Mpm_ManCleanRequired( p );
Mig_ManForEachObjReverse( p->pMig, pObj )
{
if ( Mig_ObjIsCo(pObj) )
{
pRequired[Mig_ObjFaninId0(pObj)] = p->GloRequired;
pMapRefs [Mig_ObjFaninId0(pObj)]++;
}
else if ( Mig_ObjIsNode(pObj) )
{
int Required = pRequired[Mig_ObjId(pObj)];
assert( Required > 0 );
if ( pMapRefs[Mig_ObjId(pObj)] > 0 )
{
pCut = Mpm_ObjCutBestP( p, pObj );
pDelays = p->pLibLut->pLutDelays[pCut->nLeaves];
Mpm_CutForEachLeafId( pCut, iLeaf, i )
{
pRequired[iLeaf] = Abc_MinInt( pRequired[iLeaf], Required - pDelays[i] );
pMapRefs [iLeaf]++;
}
p->GloArea += Mpm_CutGetArea( p, pCut );
p->GloEdge += pCut->nLeaves;
}
}
else if ( Mig_ObjIsBuf(pObj) )
{
}
}
p->GloArea /= MPM_UNIT_AREA;
}
static inline void Mpm_ManComputeEstRefs( Mpm_Man_t * p )
{
int * pMapRefs = Vec_IntArray( &p->vMapRefs );
int * pEstRefs = Vec_IntArray( &p->vEstRefs );
int i;
assert( p->fMainRun );
// pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
for ( i = 0; i < Mig_ManObjNum(p->pMig); i++ )
pEstRefs[i] = (1 * pEstRefs[i] + MPM_UNIT_REFS * pMapRefs[i]) / 2;
}
/**Function*************************************************************
Synopsis [Cut comparison.]
Description [Returns positive number if new one is better than old one.]
SideEffects []
SeeAlso []
***********************************************************************/
int Mpm_CutCompareDelay( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
{
if ( pOld->mTime != pNew->mTime ) return pOld->mTime - pNew->mTime;
if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
if ( pOld->mArea != pNew->mArea ) return pOld->mArea - pNew->mArea;
if ( pOld->mEdge != pNew->mEdge ) return pOld->mEdge - pNew->mEdge;
return 0;
}
int Mpm_CutCompareDelay2( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
{
if ( pOld->mTime != pNew->mTime ) return pOld->mTime - pNew->mTime;
if ( pOld->mArea != pNew->mArea ) return pOld->mArea - pNew->mArea;
if ( pOld->mEdge != pNew->mEdge ) return pOld->mEdge - pNew->mEdge;
if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
return 0;
}
int Mpm_CutCompareArea( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
{
if ( pOld->mArea != pNew->mArea ) return pOld->mArea - pNew->mArea;
if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
if ( pOld->mEdge != pNew->mEdge ) return pOld->mEdge - pNew->mEdge;
if ( pOld->mAveRefs != pNew->mAveRefs ) return pOld->mAveRefs - pNew->mAveRefs;
if ( pOld->mTime != pNew->mTime ) return pOld->mTime - pNew->mTime;
return 0;
}
int Mpm_CutCompareArea2( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
{
if ( pOld->mArea != pNew->mArea ) return pOld->mArea - pNew->mArea;
if ( pOld->mEdge != pNew->mEdge ) return pOld->mEdge - pNew->mEdge;
if ( pOld->mAveRefs != pNew->mAveRefs ) return pOld->mAveRefs - pNew->mAveRefs;
if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
if ( pOld->mTime != pNew->mTime ) return pOld->mTime - pNew->mTime;
return 0;
}
/**Function*************************************************************
Synopsis [Technology mapping experiment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Mpm_ManPrepare( Mpm_Man_t * p )
{
Mig_Obj_t * pObj;
int i, hCut;
Mig_ManForEachCi( p->pMig, pObj, i )
{
hCut = Mpm_CutCreateUnit( p, Mig_ObjId(pObj) );
Mpm_ObjSetCutBest( p, pObj, hCut );
Mpm_ObjSetCutList( p, pObj, hCut );
}
Mig_ManForEachCand( p->pMig, pObj )
Mpm_ObjSetEstRef( p, pObj, MPM_UNIT_REFS * Mig_ObjRefNum(pObj) );
}
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;
Mig_ManForEachNode( p->pMig, pObj )
Mpm_ManDeriveCuts( p, pObj );
assert( Mig_ManCandNum(p->pMig) == p->pManCuts->nEntries );
Mpm_ManFinalizeRound( p );
// report results
if ( p->pPars->fVerbose )
{
printf( "Del =%5d. Ar =%8d. Edge =%8d. Cut =%10d. Max =%8d. Tru =%8d. Small =%6d. ",
p->GloRequired, (int)p->GloArea, (int)p->GloEdge,
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 )
{
if ( p->pPars->fMap4Cnf )
{
p->pCutCmp = Mpm_CutCompareArea;
Mpm_ManPerformRound( p );
}
else
{
p->pCutCmp = Mpm_CutCompareDelay;
Mpm_ManPerformRound( p );
if ( p->pPars->fOneRound )
return;
p->pCutCmp = Mpm_CutCompareDelay2;
Mpm_ManPerformRound( p );
p->pCutCmp = Mpm_CutCompareArea;
Mpm_ManPerformRound( p );
p->fMainRun = 1;
p->pCutCmp = Mpm_CutCompareArea;
Mpm_ManComputeEstRefs( p );
Mpm_ManPerformRound( p );
p->pCutCmp = Mpm_CutCompareArea2;
Mpm_ManComputeEstRefs( p );
Mpm_ManPerformRound( p );
}
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END