amapMatch.c File Reference

#include "amapInt.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Amap_Cut_t *	Amap_ManDupCut (Amap_Man_t *p, Amap_Cut_t *pCut)
	DECLARATIONS ///. More...
static void	Amap_ManMatchStart (Amap_Mat_t *p, Amap_Cut_t *pCut, Amap_Set_t *pSet)
void	Amap_ManCleanRefs (Amap_Man_t *p)
float	Amap_ManMaxDelay (Amap_Man_t *p)
void	Amap_ManCleanData (Amap_Man_t *p)
float	Amap_ManComputeMapping_rec (Amap_Man_t *p, Amap_Obj_t *pObj, int fCompl)
float	Amap_ManComputeMapping (Amap_Man_t *p)
int	Amap_ManCountInverters (Amap_Man_t *p)
static int	Amap_CutCompareDelay (Amap_Man_t *p, Amap_Mat_t *pM0, Amap_Mat_t *pM1)
static int	Amap_CutCompareArea (Amap_Man_t *p, Amap_Mat_t *pM0, Amap_Mat_t *pM1)
static float	Amap_CutAreaDeref (Amap_Man_t *p, Amap_Mat_t *pM)
static float	Amap_CutAreaRef (Amap_Man_t *p, Amap_Mat_t *pM)
static float	Amap_CutAreaDerefed (Amap_Man_t *p, Amap_Obj_t *pNode, Amap_Mat_t *pM)
static void	Amap_CutAreaTest (Amap_Man_t *p, Amap_Obj_t *pNode)
static void	Amap_ManMatchGetFlows (Amap_Man_t *p, Amap_Mat_t *pM)
static void	Amap_ManMatchGetExacts (Amap_Man_t *p, Amap_Obj_t *pNode, Amap_Mat_t *pM)
void	Amap_ManMatchNode (Amap_Man_t *p, Amap_Obj_t *pNode, int fFlow, int fRefs)
void	Amap_ManMatch (Amap_Man_t *p, int fFlow, int fRefs)
void	Amap_ManMap (Amap_Man_t *p)

Function Documentation

static float Amap_CutAreaDeref ( Amap_Man_t *  p, Amap_Mat_t *  pM  )

inlinestatic

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

Synopsis [Counts area while dereferencing the match.]

Description []

SideEffects []

SeeAlso []

Definition at line 275 of file amapMatch.c.

{
    Amap_Obj_t * pFanin;
    int i, fCompl;
    float Area = Amap_LibGate( p->pLib, pM->pSet->iGate )->dArea;
    Amap_MatchForEachFaninCompl( p, pM, pFanin, fCompl, i )
    {
        assert( Amap_ObjRefsTotal(pFanin) > 0 );
        if ( (int)pFanin->fPolar != fCompl && pFanin->nFouts[fCompl] == 1 )
            Area += p->fAreaInv;
        if ( --pFanin->nFouts[fCompl] + pFanin->nFouts[!fCompl] == 0 && Amap_ObjIsNode(pFanin) )
            Area += Amap_CutAreaDeref( p, &pFanin->Best );
    }
    return Area;
}

static float Amap_CutAreaDerefed ( Amap_Man_t *  p, Amap_Obj_t *  pNode, Amap_Mat_t *  pM  )

inlinestatic

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

Synopsis [Derives area of the match for a non-referenced node.]

Description []

SideEffects []

SeeAlso []

Definition at line 329 of file amapMatch.c.

{
    float aResult, aResult2;
    int fComplNew;
    aResult2 = Amap_CutAreaRef( p, pM );
    aResult  = Amap_CutAreaDeref( p, pM );
    assert( aResult > aResult2 - p->fEpsilonInternal );
    assert( aResult < aResult2 + p->fEpsilonInternal );
    // if node is needed in another polarity, add inverter
    fComplNew = pM->pCut->fInv ^ pM->pSet->fInv;
    if ( pNode->nFouts[fComplNew] == 0 && pNode->nFouts[!fComplNew] > 0 )
        aResult += p->fAreaInv;
    return aResult;
}

static float Amap_CutAreaRef ( Amap_Man_t *  p, Amap_Mat_t *  pM  )

inlinestatic

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

Synopsis [Counts area while referencing the match.]

Description []

SideEffects []

SeeAlso []

Definition at line 302 of file amapMatch.c.

{
    Amap_Obj_t * pFanin;
    int i, fCompl;
    float Area = Amap_LibGate( p->pLib, pM->pSet->iGate )->dArea;
    Amap_MatchForEachFaninCompl( p, pM, pFanin, fCompl, i )
    {
        assert( Amap_ObjRefsTotal(pFanin) >= 0 );
        if ( (int)pFanin->fPolar != fCompl && pFanin->nFouts[fCompl] == 0 )
            Area += p->fAreaInv;
        if ( pFanin->nFouts[fCompl]++ + pFanin->nFouts[!fCompl] == 0 && Amap_ObjIsNode(pFanin) )
            Area += Amap_CutAreaRef( p, &pFanin->Best );
    }
    return Area;
}

static void Amap_CutAreaTest ( Amap_Man_t *  p, Amap_Obj_t *  pNode  )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 355 of file amapMatch.c.

{
    float aResult, aResult2;
    if ( Amap_ObjRefsTotal(pNode) == 0 )
    {
        aResult2 = Amap_CutAreaRef( p, &pNode->Best );
        aResult  = Amap_CutAreaDeref( p, &pNode->Best );
        assert( aResult > aResult2 - p->fEpsilonInternal );
        assert( aResult < aResult2 + p->fEpsilonInternal );
    }
    else
    {
        aResult  = Amap_CutAreaDeref( p, &pNode->Best );
        aResult2 = Amap_CutAreaRef( p, &pNode->Best );
        assert( aResult > aResult2 - p->fEpsilonInternal );
        assert( aResult < aResult2 + p->fEpsilonInternal );
    }
}

static int Amap_CutCompareArea ( Amap_Man_t *  p, Amap_Mat_t *  pM0, Amap_Mat_t *  pM1  )

inlinestatic

Definition at line 242 of file amapMatch.c.

{
    // compare area flows
    if ( pM0->Area < pM1->Area - p->pPars->fEpsilon )
        return -1;
    if ( pM0->Area > pM1->Area + p->pPars->fEpsilon )
        return 1;

    // compare average fanouts
    if ( pM0->AveFan > pM1->AveFan - p->pPars->fEpsilon )
        return -1;
    if ( pM0->AveFan < pM1->AveFan + p->pPars->fEpsilon )
        return 1;

    // compare delay
    if ( pM0->Delay < pM1->Delay - p->pPars->fEpsilon )
        return -1;
    if ( pM0->Delay > pM1->Delay + p->pPars->fEpsilon )
        return 1;
    return 1;
}

static int Amap_CutCompareDelay ( Amap_Man_t *  p, Amap_Mat_t *  pM0, Amap_Mat_t *  pM1  )

inlinestatic

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

Synopsis [Compare two matches.]

Description []

SideEffects []

SeeAlso []

Definition at line 221 of file amapMatch.c.

{
    // compare delay
    if ( pM0->Delay < pM1->Delay - p->pPars->fEpsilon )
        return -1;
    if ( pM0->Delay > pM1->Delay + p->pPars->fEpsilon )
        return 1;

    // compare area flows
    if ( pM0->Area < pM1->Area - p->pPars->fEpsilon )
        return -1;
    if ( pM0->Area > pM1->Area + p->pPars->fEpsilon )
        return 1;

    // compare average fanouts
    if ( pM0->AveFan > pM1->AveFan - p->pPars->fEpsilon )
        return -1;
    if ( pM0->AveFan < pM1->AveFan + p->pPars->fEpsilon )
        return 1;
    return 1;
}

void Amap_ManCleanData

(

Amap_Man_t *

p

)

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

Synopsis [Cleans reference counters.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file amapMatch.c.

{
    Amap_Obj_t * pObj;
    int i;
//    Amap_ManForEachNode( p, pObj, i )
//        ABC_FREE( pObj->pData );
    Amap_ManForEachObj( p, pObj, i )
        pObj->pData = NULL;
}

void Amap_ManCleanRefs

(

Amap_Man_t *

p

)

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

Synopsis [Cleans reference counters.]

Description []

SideEffects []

SeeAlso []

Definition at line 83 of file amapMatch.c.

{
    Amap_Obj_t * pObj;
    int i;
    Amap_ManForEachObj( p, pObj, i )
        pObj->nFouts[0] = pObj->nFouts[1] = 0;
}

float Amap_ManComputeMapping

(

Amap_Man_t *

p

)

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

Synopsis [Compute nodes used in the mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 179 of file amapMatch.c.

{
    Amap_Obj_t * pObj;
    float Area = 0.0;
    int i;
    Amap_ManCleanRefs( p );
    Amap_ManForEachPo( p, pObj, i )
        Area += Amap_ManComputeMapping_rec( p, Amap_ObjFanin0(p, pObj), Amap_ObjFaninC0(pObj) );
    return Area;
}

float Amap_ManComputeMapping_rec	(	Amap_Man_t *	p,
		Amap_Obj_t *	pObj,
		int	fCompl
	)

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

Synopsis [Compute nodes used in the mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 144 of file amapMatch.c.

{
    Amap_Mat_t * pM = &pObj->Best;
    Amap_Obj_t * pFanin;
    Amap_Gat_t * pGate;
    int i, iFanin, fComplFanin;
    float Area;
    if ( pObj->nFouts[fCompl]++ + pObj->nFouts[!fCompl] > 0 )
        return 0.0;
    if ( Amap_ObjIsPi(pObj) || Amap_ObjIsConst1(pObj) )
        return 0.0;
    pGate = Amap_LibGate( p->pLib, pM->pSet->iGate );
    assert( pGate->nPins == pM->pCut->nFans );
    Area = pGate->dArea;
    for ( i = 0; i < (int)pGate->nPins; i++ )
    {
        iFanin = Abc_Lit2Var( pM->pSet->Ins[i] );
        pFanin = Amap_ManObj( p, Abc_Lit2Var(pM->pCut->Fans[iFanin]) );
        fComplFanin = Abc_LitIsCompl( pM->pSet->Ins[i] ) ^ Abc_LitIsCompl( pM->pCut->Fans[iFanin] );
        Area += Amap_ManComputeMapping_rec( p, pFanin, fComplFanin );
    }
    return Area;
}

int Amap_ManCountInverters

(

Amap_Man_t *

p

)

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

Synopsis [Counts the number of inverters to be added.]

Description [Should be called after mapping has been set.]

SideEffects []

SeeAlso []

Definition at line 201 of file amapMatch.c.

{
    Amap_Obj_t * pObj;
    int i, Counter = 0;
    Amap_ManForEachObj( p, pObj, i )
        Counter += (int)(pObj->nFouts[!pObj->fPolar] > 0);
    return Counter;
}

ABC_NAMESPACE_IMPL_START Amap_Cut_t* Amap_ManDupCut	(	Amap_Man_t *	p,
		Amap_Cut_t *	pCut
	)

DECLARATIONS ///.

CFile****************************************************************

FileName [amapMatch.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Technology mapper for standard cells.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

amapMatch.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Duplicates the cut using new memory manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file amapMatch.c.

{
    Amap_Cut_t * pNew;
    int nBytes = sizeof(Amap_Cut_t) + sizeof(int) * pCut->nFans;
    pNew = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemCutBest, nBytes );
    memcpy( pNew, pCut, nBytes );
    return pNew;
}

void Amap_ManMap

(

Amap_Man_t *

p

)

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

Synopsis [Performs mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 593 of file amapMatch.c.

{
    int i;
    Amap_ManMerge( p );
    for ( i = 0; i < p->pPars->nIterFlow; i++ )
        Amap_ManMatch( p, 1, i>0 );
    for ( i = 0; i < p->pPars->nIterArea; i++ )
        Amap_ManMatch( p, 0, p->pPars->nIterFlow>0||i>0 );
/*
    for ( i = 0; i < p->pPars->nIterFlow; i++ )
        Amap_ManMatch( p, 1, 1 );
    for ( i = 0; i < p->pPars->nIterArea; i++ )
        Amap_ManMatch( p, 0, 1 );
*/
    Amap_ManCleanData( p );
}

void Amap_ManMatch	(	Amap_Man_t *	p,
		int	fFlow,
		int	fRefs
	)

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

Synopsis [Performs one round of mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 554 of file amapMatch.c.

{
    Aig_MmFlex_t * pMemOld;
    Amap_Obj_t * pObj;
    float Area;
    int i, nInvs;
    abctime clk = Abc_Clock();
    pMemOld = p->pMemCutBest;
    p->pMemCutBest = Aig_MmFlexStart();
    Amap_ManForEachNode( p, pObj, i )
        if ( pObj->pData )
            Amap_ManMatchNode( p, pObj, fFlow, fRefs );
    Aig_MmFlexStop( pMemOld, 0 );
    Area = Amap_ManComputeMapping( p );
    nInvs = Amap_ManCountInverters( p );
if ( p->pPars->fVerbose )
{
    printf( "Area =%9.2f. Gate =%9.2f. Inv =%9.2f. (%6d.) Delay =%6.2f. ", 
        Area + nInvs * p->fAreaInv, 
        Area, nInvs * p->fAreaInv, nInvs,
        Amap_ManMaxDelay(p) );
ABC_PRT( "Time ", Abc_Clock() - clk );
}
    // test procedures
//    Amap_ManForEachNode( p, pObj, i )
//        Amap_CutAreaTest( p, pObj );
}

static void Amap_ManMatchGetExacts ( Amap_Man_t *  p, Amap_Obj_t *  pNode, Amap_Mat_t *  pM  )

inlinestatic

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

Synopsis [Derives parameters for the match.]

Description []

SideEffects []

SeeAlso []

Definition at line 422 of file amapMatch.c.

{
    Amap_Mat_t * pMFanin;
    Amap_Obj_t * pFanin;
    Amap_Gat_t * pGate;
    int i;
    pGate = Amap_LibGate( p->pLib, pM->pSet->iGate );
    assert( pGate->nPins == pM->pCut->nFans );
    assert( pM->Area == 0.0 );
    pM->AveFan = 0.0;
    pM->Delay = 0.0;
    Amap_MatchForEachFanin( p, pM, pFanin, i )
    {
        pMFanin = &pFanin->Best;
        pM->Delay = Abc_MaxInt( pM->Delay, pMFanin->Delay );
        pM->AveFan += Amap_ObjRefsTotal(pFanin);
    }
    pM->AveFan /= pGate->nPins;
    pM->Delay += 1.0;
    pM->Area = Amap_CutAreaDerefed( p, pNode, pM );
}

static void Amap_ManMatchGetFlows ( Amap_Man_t *  p, Amap_Mat_t *  pM  )

inlinestatic

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

Synopsis [Derives parameters for the match.]

Description []

SideEffects []

SeeAlso []

Definition at line 385 of file amapMatch.c.

{
    Amap_Mat_t * pMFanin;
    Amap_Obj_t * pFanin;
    Amap_Gat_t * pGate;
    int i;
    pGate = Amap_LibGate( p->pLib, pM->pSet->iGate );
    assert( pGate->nPins == pM->pCut->nFans );
    assert( pM->Area == 0.0 );
    pM->Area = pGate->dArea;
    pM->AveFan = 0.0;
    pM->Delay = 0.0;
    Amap_MatchForEachFanin( p, pM, pFanin, i )
    {
        pMFanin = &pFanin->Best;
        pM->Delay = Abc_MaxInt( pM->Delay, pMFanin->Delay );
        pM->AveFan += Amap_ObjRefsTotal(pFanin);
        if ( Amap_ObjRefsTotal(pFanin) == 0 )
            pM->Area += pMFanin->Area;
        else
            pM->Area += pMFanin->Area / pFanin->EstRefs;
    }
    pM->AveFan /= pGate->nPins;
    pM->Delay += 1.0;
}

void Amap_ManMatchNode	(	Amap_Man_t *	p,
		Amap_Obj_t *	pNode,
		int	fFlow,
		int	fRefs
	)

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

Synopsis [Computes the best match at each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 455 of file amapMatch.c.

{
    int fVerbose = 0; //(pNode->Level == 2 || pNode->Level == 4);
    int fVeryVerbose = fVerbose;

    Amap_Mat_t MA = {0}, MD = {0}, M = {0};
    Amap_Mat_t * pMBestA = &MA, * pMBestD = &MD, * pMThis = &M, * pMBest;
    Amap_Cut_t * pCut;
    Amap_Set_t * pSet;
    Amap_Nod_t * pNod;
    int i;

    if ( fRefs )
        pNode->EstRefs = (float)((2.0 * pNode->EstRefs + Amap_ObjRefsTotal(pNode)) / 3.0);
    else
        pNode->EstRefs = (float)pNode->nRefs;
    if ( fRefs && Amap_ObjRefsTotal(pNode) > 0 )
        Amap_CutAreaDeref( p, &pNode->Best );

    if ( fVerbose )
        printf( "\nNode %d (%d)\n", pNode->Id, pNode->Level );

    pMBestA->pCut = pMBestD->pCut = NULL;
    Amap_NodeForEachCut( pNode, pCut, i )
    {
        if ( pCut->iMat == 0 )
            continue;
        pNod = Amap_LibNod( p->pLib, pCut->iMat );
        Amap_LibNodeForEachSet( pNod, pSet )
        {
            Amap_ManMatchStart( pMThis, pCut, pSet );
            if ( fFlow )
                Amap_ManMatchGetFlows( p, pMThis );
            else
                Amap_ManMatchGetExacts( p, pNode, pMThis );
            if ( pMBestD->pCut == NULL || Amap_CutCompareDelay(p, pMBestD, pMThis) == 1 )
                *pMBestD = *pMThis;
            if ( pMBestA->pCut == NULL || Amap_CutCompareArea(p, pMBestA, pMThis) == 1 )
                *pMBestA = *pMThis;

            if ( fVeryVerbose ) 
            {
                printf( "Cut %2d (%d) :  ", i, pCut->nFans );
                printf( "Gate %10s  ",      Amap_LibGate(p->pLib, pMThis->pSet->iGate)->pName );
                printf( "%s  ",             pMThis->pSet->fInv ? "inv" : "   " );
                printf( "Delay %5.2f  ",    pMThis->Delay );
                printf( "Area %5.2f  ",     pMThis->Area );
                printf( "\n" );
            }
        }
    }

    if ( Abc_AbsFloat(pMBestA->Area - pMBestD->Area) / pMBestD->Area >= p->pPars->fADratio * Abc_AbsFloat(pMBestA->Delay - pMBestD->Delay) / pMBestA->Delay )
        pMBest = pMBestA;
    else
        pMBest = pMBestD;

    if ( fVerbose )
    {
        printf( "BEST MATCHA:  " );
        printf( "Gate %10s  ",    Amap_LibGate(p->pLib, pMBestA->pSet->iGate)->pName );
        printf( "%s  ",           pMBestA->pSet->fInv ? "inv" : "   " );
        printf( "Delay %5.2f  ",  pMBestA->Delay );
        printf( "Area %5.2f  ",   pMBestA->Area );
        printf( "\n" ); 

        printf( "BEST MATCHD:  " );
        printf( "Gate %10s  ",    Amap_LibGate(p->pLib, pMBestD->pSet->iGate)->pName );
        printf( "%s  ",           pMBestD->pSet->fInv ? "inv" : "   " );
        printf( "Delay %5.2f  ",  pMBestD->Delay );
        printf( "Area %5.2f  ",   pMBestD->Area );
        printf( "\n" ); 

        printf( "BEST MATCH :  " );
        printf( "Gate %10s  ",    Amap_LibGate(p->pLib, pMBest->pSet->iGate)->pName );
        printf( "%s  ",           pMBest->pSet->fInv ? "inv" : "   " );
        printf( "Delay %5.2f  ",  pMBest->Delay );
        printf( "Area %5.2f  ",   pMBest->Area );
        printf( "\n" ); 
    }

    pNode->fPolar = pMBest->pCut->fInv ^ pMBest->pSet->fInv;
    pNode->Best = *pMBest;
    pNode->Best.pCut = Amap_ManDupCut( p, pNode->Best.pCut );
    if ( fRefs && Amap_ObjRefsTotal(pNode) > 0 )
        Amap_CutAreaRef( p, &pNode->Best );
}

static void Amap_ManMatchStart ( Amap_Mat_t *  p, Amap_Cut_t *  pCut, Amap_Set_t *  pSet  )

inlinestatic

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

Synopsis [Starts the match with cut and set.]

Description []

SideEffects []

SeeAlso []

Definition at line 65 of file amapMatch.c.

{
    memset( p, 0, sizeof(Amap_Mat_t) );
    p->pCut = pCut;
    p->pSet = pSet;
}

float Amap_ManMaxDelay

(

Amap_Man_t *

p

)

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

Synopsis [Computes delay.]

Description []

SideEffects []

SeeAlso []

Definition at line 102 of file amapMatch.c.

{
    Amap_Obj_t * pObj;
    float Delay = 0.0;
    int i;
    Amap_ManForEachPo( p, pObj, i )
        Delay = Abc_MaxInt( Delay, Amap_ObjFanin0(p,pObj)->Best.Delay );
    return Delay;
}