From f936cc0680c98ffe51b3a1716c996072d5dbf76c Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 18 Jan 2009 08:01:00 -0800 Subject: Version abc90118 --- src/map/amap/amapMatch.c | 538 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 538 insertions(+) create mode 100644 src/map/amap/amapMatch.c (limited to 'src/map/amap/amapMatch.c') diff --git a/src/map/amap/amapMatch.c b/src/map/amap/amapMatch.c new file mode 100644 index 00000000..0b15a931 --- /dev/null +++ b/src/map/amap/amapMatch.c @@ -0,0 +1,538 @@ +/**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 $] + +***********************************************************************/ + +#include "amapInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Duplicates the cut using new memory manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Cut_t * Amap_ManDupCut( Amap_Man_t * p, Amap_Cut_t * pCut ) +{ + 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; +} + +/**Function************************************************************* + + Synopsis [Starts the match with cut and set.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Amap_ManMatchStart( Amap_Mat_t * p, Amap_Cut_t * pCut, Amap_Set_t * pSet ) +{ + memset( p, 0, sizeof(Amap_Mat_t) ); + p->pCut = pCut; + p->pSet = pSet; +} + +/**Function************************************************************* + + Synopsis [Cleans reference counters.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCleanRefs( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + int i; + Amap_ManForEachObj( p, pObj, i ) + pObj->nFouts[0] = pObj->nFouts[1] = 0; +} + +/**Function************************************************************* + + Synopsis [Computes delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Amap_ManMaxDelay( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + float Delay = 0.0; + int i; + Amap_ManForEachPo( p, pObj, i ) + Delay = AIG_MAX( Delay, Amap_ObjFanin0(p,pObj)->Best.Delay ); + return Delay; +} + +/**Function************************************************************* + + Synopsis [Cleans reference counters.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCleanData( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + int i; +// Amap_ManForEachNode( p, pObj, i ) +// FREE( pObj->pData ); + Amap_ManForEachObj( p, pObj, i ) + pObj->pData = NULL; +} + +/**Function************************************************************* + + Synopsis [Compute nodes used in the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Amap_ManComputeMapping_rec( Amap_Man_t * p, Amap_Obj_t * pObj, int fCompl ) +{ + 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 = Amap_Lit2Var( pM->pSet->Ins[i] ); + pFanin = Amap_ManObj( p, Amap_Lit2Var(pM->pCut->Fans[iFanin]) ); + fComplFanin = Amap_LitIsCompl( pM->pSet->Ins[i] ) ^ Amap_LitIsCompl( pM->pCut->Fans[iFanin] ); + Area += Amap_ManComputeMapping_rec( p, pFanin, fComplFanin ); + } + return Area; +} + +/**Function************************************************************* + + Synopsis [Compute nodes used in the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Amap_ManComputeMapping( Amap_Man_t * p ) +{ + 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; +} + +/**Function************************************************************* + + Synopsis [Counts the number of inverters to be added.] + + Description [Should be called after mapping has been set.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Amap_ManCountInverters( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + int i, Counter = 0; + Amap_ManForEachObj( p, pObj, i ) + Counter += (int)(pObj->nFouts[!pObj->fPolar] > 0); + return Counter; +} + +/**Function************************************************************* + + Synopsis [Compare two matches.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Amap_CutCompare( Amap_Man_t * p, Amap_Mat_t * pM0, Amap_Mat_t * pM1 ) +{ + // 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; +} + +/**Function************************************************************* + + Synopsis [Counts area while dereferencing the match.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float Amap_CutAreaDeref( Amap_Man_t * p, Amap_Mat_t * pM ) +{ + 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; +} + +/**Function************************************************************* + + Synopsis [Counts area while referencing the match.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float Amap_CutAreaRef( Amap_Man_t * p, Amap_Mat_t * pM ) +{ + 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; +} + +/**Function************************************************************* + + Synopsis [Derives area of the match for a non-referenced node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float Amap_CutAreaDerefed( Amap_Man_t * p, Amap_Obj_t * pNode, Amap_Mat_t * pM ) +{ + 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; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Amap_CutAreaTest( Amap_Man_t * p, Amap_Obj_t * pNode ) +{ + 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 ); + } +} + +/**Function************************************************************* + + Synopsis [Derives parameters for the match.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Amap_ManMatchGetFlows( Amap_Man_t * p, Amap_Mat_t * pM ) +{ + 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 = AIG_MAX( 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; +} + +/**Function************************************************************* + + Synopsis [Derives parameters for the match.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Amap_ManMatchGetExacts( Amap_Man_t * p, Amap_Obj_t * pNode, Amap_Mat_t * pM ) +{ + 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 = AIG_MAX( pM->Delay, pMFanin->Delay ); + pM->AveFan += Amap_ObjRefsTotal(pFanin); + } + pM->AveFan /= pGate->nPins; + pM->Delay += 1.0; + pM->Area = Amap_CutAreaDerefed( p, pNode, pM ); +} + +/**Function************************************************************* + + Synopsis [Computes the best match at each node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMatchNode( Amap_Man_t * p, Amap_Obj_t * pNode, int fFlow, int fRefs ) +{ + Amap_Mat_t M1, M2, * pMBest = &M1, * pMThis = &M2; + 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 ); + pMBest->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 ( pMBest->pCut == NULL || Amap_CutCompare(p, pMBest, pMThis) == 1 ) + *pMBest = *pMThis; + } + } + 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 ); +} + +/**Function************************************************************* + + Synopsis [Performs one round of mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMatch( Amap_Man_t * p, int fFlow, int fRefs ) +{ + Aig_MmFlex_t * pMemOld; + Amap_Obj_t * pObj; + float Area; + int i, nInvs, clk = 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) ); +PRT( "Time ", clock() - clk ); +} + // test procedures +// Amap_ManForEachNode( p, pObj, i ) +// Amap_CutAreaTest( p, pObj ); +} + +/**Function************************************************************* + + Synopsis [Performs mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMap( Amap_Man_t * p ) +{ + 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 ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3