mpmMap.c File Reference

#include "mpmInt.h"

Include dependency graph for mpmMap.c:

Go to the source code of this file.

Functions
void	Mpm_CutPrint (Mpm_Cut_t *pCut)
int	Mpm_ObjAddCutToStore (Mpm_Man_t *p, Mpm_Cut_t *pCut, int ArrTime)
void	Mpm_ObjAddChoiceCutsToStore (Mpm_Man_t *p, Mig_Obj_t *pRoot, Mig_Obj_t *pObj, int ReqTime)
void	Mpm_ObjTranslateCutsFromStore (Mpm_Man_t *p, Mig_Obj_t *pObj)
int	Mpm_ManDeriveCuts (Mpm_Man_t *p, Mig_Obj_t *pObj)
int	Mpm_CutCompareDelay (Mpm_Uni_t *pOld, Mpm_Uni_t *pNew)
int	Mpm_CutCompareDelay2 (Mpm_Uni_t *pOld, Mpm_Uni_t *pNew)
int	Mpm_CutCompareArea (Mpm_Uni_t *pOld, Mpm_Uni_t *pNew)
int	Mpm_CutCompareArea2 (Mpm_Uni_t *pOld, Mpm_Uni_t *pNew)
void	Mpm_ManPrepare (Mpm_Man_t *p)
void	Mpm_ManPerformRound (Mpm_Man_t *p)
void	Mpm_ManPerform (Mpm_Man_t *p)

Function Documentation

Mpm_CutCompareArea()

int Mpm_CutCompareArea	(	Mpm_Uni_t *	pOld,
		Mpm_Uni_t *	pNew )

Definition at line 764 of file mpmMap.c.

{
    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;
}

Here is the caller graph for this function:

Mpm_CutCompareArea2()

int Mpm_CutCompareArea2	(	Mpm_Uni_t *	pOld,
		Mpm_Uni_t *	pNew )

Definition at line 773 of file mpmMap.c.

{
    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;
}

Here is the caller graph for this function:

Mpm_CutCompareDelay()

int Mpm_CutCompareDelay	(	Mpm_Uni_t *	pOld,
		Mpm_Uni_t *	pNew )

Function*************************************************************

Synopsis [Cut comparison.]

Description [Returns positive number if new one is better than old one.]

SideEffects []

SeeAlso []

Definition at line 748 of file mpmMap.c.

{
    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;
}

Here is the caller graph for this function:

Mpm_CutCompareDelay2()

int Mpm_CutCompareDelay2	(	Mpm_Uni_t *	pOld,
		Mpm_Uni_t *	pNew )

Definition at line 756 of file mpmMap.c.

{
    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;
}

Here is the caller graph for this function:

Mpm_CutPrint()

void Mpm_CutPrint

(

Mpm_Cut_t *

pCut

)

Definition at line 103 of file mpmMap.c.

{ 
    int i;
    printf( "%d : { ", pCut->nLeaves );
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        printf( "%d ", pCut->pLeaves[i] );
    printf( "}\n" );
}

Here is the caller graph for this function:

Mpm_ManDeriveCuts()

int Mpm_ManDeriveCuts	(	Mpm_Man_t *	p,
		Mig_Obj_t *	pObj )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 580 of file mpmMap.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Mpm_ManPerform()

void Mpm_ManPerform

(

Mpm_Man_t *

p

)

Definition at line 833 of file mpmMap.c.

{
    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 );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Mpm_ManPerformRound()

void Mpm_ManPerformRound

(

Mpm_Man_t *

p

)

Definition at line 807 of file mpmMap.c.

{
    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 );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Mpm_ManPrepare()

void Mpm_ManPrepare

(

Mpm_Man_t *

p

)

Function*************************************************************

Synopsis [Technology mapping experiment.]

Description []

SideEffects []

SeeAlso []

Definition at line 794 of file mpmMap.c.

{
    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) );
}

Here is the caller graph for this function:

Mpm_ObjAddChoiceCutsToStore()

void Mpm_ObjAddChoiceCutsToStore	(	Mpm_Man_t *	p,
		Mig_Obj_t *	pRoot,
		Mig_Obj_t *	pObj,
		int	ReqTime )

Definition at line 529 of file mpmMap.c.

{
    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 );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Mpm_ObjAddCutToStore()

int Mpm_ObjAddCutToStore	(	Mpm_Man_t *	p,
		Mpm_Cut_t *	pCut,
		int	ArrTime )

Function*************************************************************

Synopsis [Compares cut against those present in the store.]

Description []

SideEffects []

SeeAlso []

Definition at line 225 of file mpmMap.c.

{
    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;
}

Here is the caller graph for this function:

Mpm_ObjTranslateCutsFromStore()

void Mpm_ObjTranslateCutsFromStore	(	Mpm_Man_t *	p,
		Mig_Obj_t *	pObj )

Definition at line 547 of file mpmMap.c.

{
    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) );
}

Here is the caller graph for this function: