diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2009-01-18 08:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2009-01-18 08:01:00 -0800 |
commit | f936cc0680c98ffe51b3a1716c996072d5dbf76c (patch) | |
tree | 784a2a809fb6b972ec6a8e2758ab758ca590d01a /src/map/amap/amapMerge.c | |
parent | c9ad5880cc61787dec6d018111b63023407ce0e6 (diff) | |
download | abc-f936cc0680c98ffe51b3a1716c996072d5dbf76c.tar.gz abc-f936cc0680c98ffe51b3a1716c996072d5dbf76c.tar.bz2 abc-f936cc0680c98ffe51b3a1716c996072d5dbf76c.zip |
Version abc90118
Diffstat (limited to 'src/map/amap/amapMerge.c')
-rw-r--r-- | src/map/amap/amapMerge.c | 521 |
1 files changed, 521 insertions, 0 deletions
diff --git a/src/map/amap/amapMerge.c b/src/map/amap/amapMerge.c new file mode 100644 index 00000000..b024616e --- /dev/null +++ b/src/map/amap/amapMerge.c @@ -0,0 +1,521 @@ +/**CFile**************************************************************** + + FileName [amapMerge.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Technology mapper for standard cells.] + + Synopsis [Computing cuts for the node.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: amapMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "amapInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Creates new cut and adds it to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Cut_t * Amap_ManSetupPis( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + Amap_Cut_t * pCut; + int i, nBytes = sizeof(Amap_Cut_t) + sizeof(int); + char * pBuffer = ALLOC( char, Amap_ManPiNum(p) * nBytes ); + Amap_ManForEachPi( p, pObj, i ) + { + pCut = (Amap_Cut_t *)( pBuffer + i*nBytes ); + pCut->iMat = 0; + pCut->fInv = 0; + pCut->nFans = 1; + pCut->Fans[0] = Amap_Var2Lit( pObj->Id, 0 ); + pObj->pData = pCut; + pObj->nCuts = 1; + pObj->EstRefs = (float)1.0; + } + return (Amap_Cut_t *)pBuffer; +} + +/**Function************************************************************* + + Synopsis [Creates new cut and adds it to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Cut_t * Amap_ManCutStore( Amap_Man_t * p, Amap_Cut_t * pCut, int fCompl ) +{ + Amap_Cut_t * pNew; + int iFan, nBytes = sizeof(Amap_Cut_t) + sizeof(int) * pCut->nFans + sizeof(Amap_Cut_t *); + pNew = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemTemp, nBytes ); + pNew->iMat = pCut->iMat; + pNew->fInv = pCut->fInv ^ fCompl; + pNew->nFans = pCut->nFans; + memcpy( pNew->Fans, pCut->Fans, sizeof(int) * pCut->nFans ); + // add it to storage + iFan = Amap_Var2Lit( pNew->iMat, pNew->fInv ); + if ( p->ppCutsTemp[ iFan ] == NULL ) + Vec_IntPushOrder( p->vTemp, iFan ); + *Amap_ManCutNextP( pNew ) = p->ppCutsTemp[ iFan ]; + p->ppCutsTemp[ iFan ] = pNew; + return pNew; +} + +/**Function************************************************************* + + Synopsis [Creates new cut and adds it to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Cut_t * Amap_ManCutCreate( Amap_Man_t * p, + Amap_Cut_t * pCut0, Amap_Cut_t * pCut1, int iMat ) +{ + Amap_Cut_t * pCut; + int i, nSize = pCut0->nFans + pCut1->nFans; + int nBytes = sizeof(Amap_Cut_t) + sizeof(int) * nSize + sizeof(Amap_Cut_t *); + assert( pCut0->iMat >= pCut1->iMat ); + pCut = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemTemp, nBytes ); + pCut->iMat = iMat; + pCut->fInv = 0; + pCut->nFans = nSize; + for ( i = 0; i < (int)pCut0->nFans; i++ ) + pCut->Fans[i] = pCut0->Fans[i]; + for ( i = 0; i < (int)pCut1->nFans; i++ ) + pCut->Fans[pCut0->nFans+i] = pCut1->Fans[i]; + // add it to storage + if ( p->ppCutsTemp[ pCut->iMat ] == NULL ) + Vec_IntPushOrder( p->vTemp, pCut->iMat ); + *Amap_ManCutNextP( pCut ) = p->ppCutsTemp[ pCut->iMat ]; + p->ppCutsTemp[ pCut->iMat ] = pCut; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Creates new cut and adds it to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Cut_t * Amap_ManCutCreate3( Amap_Man_t * p, + Amap_Cut_t * pCut0, Amap_Cut_t * pCut1, Amap_Cut_t * pCut2, int iMat ) +{ + Amap_Cut_t * pCut; + int i, nSize = pCut0->nFans + pCut1->nFans + pCut2->nFans; + int nBytes = sizeof(Amap_Cut_t) + sizeof(int) * nSize + sizeof(Amap_Cut_t *); + pCut = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemTemp, nBytes ); + pCut->iMat = iMat; + pCut->fInv = 0; + pCut->nFans = nSize; + for ( i = 0; i < (int)pCut0->nFans; i++ ) + pCut->Fans[i] = pCut0->Fans[i]; + for ( i = 0; i < (int)pCut1->nFans; i++ ) + pCut->Fans[pCut0->nFans+i] = pCut1->Fans[i]; + for ( i = 0; i < (int)pCut2->nFans; i++ ) + pCut->Fans[pCut0->nFans+pCut1->nFans+i] = pCut2->Fans[i]; + // add it to storage + if ( p->ppCutsTemp[ pCut->iMat ] == NULL ) + Vec_IntPushOrder( p->vTemp, pCut->iMat ); + *Amap_ManCutNextP( pCut ) = p->ppCutsTemp[ pCut->iMat ]; + p->ppCutsTemp[ pCut->iMat ] = pCut; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Removes cuts from the temporary storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCutSaveStored( Amap_Man_t * p, Amap_Obj_t * pNode ) +{ + int * pBuffer; + Amap_Cut_t * pNext, * pCut; + int i, nWords, Entry, nCuts; + assert( pNode->pData == NULL ); + // count memory needed + nCuts = 1; + nWords = 2; + Vec_IntForEachEntry( p->vTemp, Entry, i ) + { + for ( pCut = p->ppCutsTemp[Entry]; pCut; pCut = *Amap_ManCutNextP(pCut) ) + { + nCuts++; + nWords += pCut->nFans + 1; + } + } + p->nBytesUsed += 4*nWords; + // allocate memory + pBuffer = (int *)Aig_MmFlexEntryFetch( p->pMemCuts, 4*nWords ); + pNext = (Amap_Cut_t *)pBuffer; + // add the first cut + pNext->iMat = 0; + pNext->fInv = 0; + pNext->nFans = 1; + pNext->Fans[0] = Amap_Var2Lit(pNode->Id, 0); + pNext = (Amap_Cut_t *)(pBuffer + 2); + // add other cuts + Vec_IntForEachEntry( p->vTemp, Entry, i ) + { + for ( pCut = p->ppCutsTemp[Entry]; pCut; pCut = *Amap_ManCutNextP(pCut) ) + { + memcpy( pNext, pCut, sizeof(int) * (pCut->nFans + 1) ); + pNext = (Amap_Cut_t *)((int *)pNext + pCut->nFans + 1); + } + p->ppCutsTemp[Entry] = NULL; + } + assert( (int *)pNext - pBuffer == nWords ); + // restore the storage + Vec_IntClear( p->vTemp ); + Aig_MmFlexRestart( p->pMemTemp ); + for ( i = 0; i < 2*p->pLib->nNodes; i++ ) + if ( p->ppCutsTemp[i] != NULL ) + printf( "Amap_ManCutSaveStored(): Error!\n" ); + pNode->pData = (Amap_Cut_t *)pBuffer; + pNode->nCuts = nCuts; +// printf("%d ", nCuts ); + // verify cuts + pCut = NULL; + Amap_NodeForEachCut( pNode, pNext, i ) +// for ( i = 0, pNext = (Amap_Cut_t *)pNode->pData; i < (int)pNode->nCuts; +// i++, pNext = Amap_ManCutNext(pNext) ) + { + assert( pCut == NULL || pCut->iMat <= pNext->iMat ); + pCut = pNext; + } +} + +/**Function************************************************************* + + Synopsis [Returns the number of possible new cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Amap_ManMergeCountCuts( Amap_Man_t * p, Amap_Obj_t * pNode ) +{ + Amap_Obj_t * pFanin0 = Amap_ObjFanin0( p, pNode ); + Amap_Obj_t * pFanin1 = Amap_ObjFanin1( p, pNode ); + Amap_Cut_t * pCut0, * pCut1; + int Entry, c0, c1, iCompl0, iCompl1, iFan0, iFan1; + int Counter = 1; + Amap_NodeForEachCut( pFanin0, pCut0, c0 ) + Amap_NodeForEachCut( pFanin1, pCut1, c1 ) + { + iCompl0 = pCut0->fInv ^ Amap_ObjFaninC0(pNode); + iCompl1 = pCut1->fInv ^ Amap_ObjFaninC1(pNode); + iFan0 = !pCut0->iMat? 0: Amap_Var2Lit( pCut0->iMat, iCompl0 ); + iFan1 = !pCut1->iMat? 0: Amap_Var2Lit( pCut1->iMat, iCompl1 ); + Entry = Amap_LibFindNode( p->pLib, iFan0, iFan1, pNode->Type == AMAP_OBJ_XOR ); + Counter += ( Entry >=0 ); +// if ( Entry >=0 ) +// printf( "Full: %d + %d = %d\n", iFan0, iFan1, Entry ); + } + return Counter; +} + +/**Function************************************************************* + + Synopsis [Print cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManPrintCuts( Amap_Obj_t * pNode ) +{ + Amap_Cut_t * pCut; + int c, i; + printf( "NODE %5d : Type = ", pNode->Id ); + if ( pNode->Type == AMAP_OBJ_AND ) + printf( "AND" ); + else if ( pNode->Type == AMAP_OBJ_XOR ) + printf( "XOR" ); + else if ( pNode->Type == AMAP_OBJ_MUX ) + printf( "MUX" ); + printf( " Cuts = %d\n", pNode->nCuts ); + Amap_NodeForEachCut( pNode, pCut, c ) + { + printf( "%3d : Mat= %3d Inv=%d ", c, pCut->iMat, pCut->fInv ); + for ( i = 0; i < (int)pCut->nFans; i++ ) + printf( "%d%c ", Amap_Lit2Var(pCut->Fans[i]), Amap_LitIsCompl(pCut->Fans[i])?'-':'+' ); + printf( "\n" ); + } +} + +/**Function************************************************************* + + Synopsis [Derives cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMergeNodeChoice( Amap_Man_t * p, Amap_Obj_t * pNode ) +{ + Amap_Obj_t * pTemp; + Amap_Cut_t * pCut; + int c; + // go through the nodes of the choice node + for ( pTemp = pNode; pTemp; pTemp = Amap_ObjChoice(p, pTemp) ) + { + Amap_NodeForEachCut( pTemp, pCut, c ) + if ( pCut->iMat ) + Amap_ManCutStore( p, pCut, pNode->fPhase ^ pTemp->fPhase ); + pTemp->pData = NULL; + } + Amap_ManCutSaveStored( p, pNode ); + +// Amap_ManPrintCuts( pNode ); +} + +/**Function************************************************************* + + Synopsis [Derives cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Amap_ManFindCut( Amap_Obj_t * pNode, Amap_Obj_t * pFanin, int fComplFanin, int Val, Vec_Ptr_t * vCuts ) +{ + Amap_Cut_t * pCut; + int c, iCompl, iFan; + Vec_PtrClear( vCuts ); + Amap_NodeForEachCut( pFanin, pCut, c ) + { + iCompl = pCut->fInv ^ fComplFanin; + iFan = !pCut->iMat? 0: Amap_Var2Lit( pCut->iMat, iCompl ); + if ( iFan == Val ) + Vec_PtrPush( vCuts, pCut ); + } + return Vec_PtrSize(vCuts) == 0; +} + +/**Function************************************************************* + + Synopsis [Derives cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMergeNodeCutsMux( Amap_Man_t * p, Amap_Obj_t * pNode ) +{ + Vec_Int_t * vRules = p->pLib->vRules3; + Amap_Obj_t * pFanin0 = Amap_ObjFanin0( p, pNode ); + Amap_Obj_t * pFanin1 = Amap_ObjFanin1( p, pNode ); + Amap_Obj_t * pFanin2 = Amap_ObjFanin2( p, pNode ); + int fComplFanin0 = Amap_ObjFaninC0( pNode ); + int fComplFanin1 = Amap_ObjFaninC1( pNode ); + int fComplFanin2 = Amap_ObjFaninC2( pNode ); + Amap_Cut_t * pCut0, * pCut1, * pCut2; + int x, c0, c1, c2; + assert( pNode->pData == NULL ); + assert( pNode->Type == AMAP_OBJ_MUX ); + assert( pNode->fRepr == 0 ); + // go through the rules + for ( x = 0; x < Vec_IntSize(vRules); x += 4 ) + { + if ( Amap_ManFindCut( pNode, pFanin0, fComplFanin0, Vec_IntEntry(vRules, x), p->vCuts0 ) ) + continue; + if ( Amap_ManFindCut( pNode, pFanin1, fComplFanin1, Vec_IntEntry(vRules, x+1), p->vCuts1 ) ) + continue; + if ( Amap_ManFindCut( pNode, pFanin2, fComplFanin2, Vec_IntEntry(vRules, x+2), p->vCuts2 ) ) + continue; + Vec_PtrForEachEntry( p->vCuts0, pCut0, c0 ) + Vec_PtrForEachEntry( p->vCuts1, pCut1, c1 ) + Vec_PtrForEachEntry( p->vCuts2, pCut2, c2 ) + { + Amap_Nod_t * pNod = Amap_LibNod( p->pLib, Vec_IntEntry(vRules, x+3) ); + if ( pNod->pSets == NULL ) + continue; + // complement literals + if ( pCut0->nFans == 1 && (pCut0->fInv ^ fComplFanin0) ) + pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]); + if ( pCut1->nFans == 1 && (pCut1->fInv ^ fComplFanin1) ) + pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]); + if ( pCut2->nFans == 1 && (pCut2->fInv ^ fComplFanin2) ) + pCut2->Fans[0] = Amap_LitNot(pCut2->Fans[0]); + // create new cut + Amap_ManCutCreate3( p, pCut0, pCut1, pCut2, Vec_IntEntry(vRules, x+3) ); + // uncomplement literals + if ( pCut0->nFans == 1 && (pCut0->fInv ^ fComplFanin0) ) + pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]); + if ( pCut1->nFans == 1 && (pCut1->fInv ^ fComplFanin1) ) + pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]); + if ( pCut2->nFans == 1 && (pCut2->fInv ^ fComplFanin2) ) + pCut2->Fans[0] = Amap_LitNot(pCut2->Fans[0]); + } + } + Amap_ManCutSaveStored( p, pNode ); + p->nCutsUsed += pNode->nCuts; + p->nCutsTried3 += pFanin0->nCuts * pFanin1->nCuts * pFanin2->nCuts; + +// Amap_ManPrintCuts( pNode ); +} + +/**Function************************************************************* + + Synopsis [Derives cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMergeNodeCuts( Amap_Man_t * p, Amap_Obj_t * pNode ) +{ + Amap_Obj_t * pFanin0 = Amap_ObjFanin0( p, pNode ); + Amap_Obj_t * pFanin1 = Amap_ObjFanin1( p, pNode ); + Amap_Cut_t * pCut0, * pCut1; + int ** pRules, Entry, i, k, c, iCompl0, iCompl1, iFan0, iFan1; + assert( pNode->pData == NULL ); + if ( pNode->Type == AMAP_OBJ_MUX ) + { + Amap_ManMergeNodeCutsMux( p, pNode ); + return; + } + assert( pNode->Type != AMAP_OBJ_MUX ); + pRules = (pNode->Type == AMAP_OBJ_AND)? p->pLib->pRules: p->pLib->pRulesX; + Amap_NodeForEachCut( pFanin0, pCut0, c ) + { + iCompl0 = pCut0->fInv ^ Amap_ObjFaninC0(pNode); + iFan0 = !pCut0->iMat? 0: Amap_Var2Lit( pCut0->iMat, iCompl0 ); + // complement literals + if ( pCut0->nFans == 1 && iCompl0 ) + pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]); + // label resulting sets + for ( i = 0; (Entry = pRules[iFan0][i]); i++ ) + p->pMatsTemp[Entry & 0xffff] = (Entry >> 16); + // iterate through the cuts + Amap_NodeForEachCut( pFanin1, pCut1, k ) + { + iCompl1 = pCut1->fInv ^ Amap_ObjFaninC1(pNode); + iFan1 = !pCut1->iMat? 0: Amap_Var2Lit( pCut1->iMat, iCompl1 ); + if ( p->pMatsTemp[iFan1] == 0 ) + continue; + // complement literals + if ( pCut1->nFans == 1 && iCompl1 ) + pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]); + // create new cut + if ( iFan0 >= iFan1 ) + Amap_ManCutCreate( p, pCut0, pCut1, p->pMatsTemp[iFan1] ); + else + Amap_ManCutCreate( p, pCut1, pCut0, p->pMatsTemp[iFan1] ); + // uncomplement literals + if ( pCut1->nFans == 1 && iCompl1 ) + pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]); + } + // uncomplement literals + if ( pCut0->nFans == 1 && iCompl0 ) + pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]); + // label resulting sets + for ( i = 0; (Entry = pRules[iFan0][i]); i++ ) + p->pMatsTemp[Entry & 0xffff] = 0; + } + Amap_ManCutSaveStored( p, pNode ); + p->nCutsUsed += pNode->nCuts; + p->nCutsTried += pFanin0->nCuts * pFanin1->nCuts; +// assert( (int)pNode->nCuts == Amap_ManMergeCountCuts(p, pNode) ); + if ( pNode->fRepr ) + Amap_ManMergeNodeChoice( p, pNode ); + +// Amap_ManPrintCuts( pNode ); +} + +/**Function************************************************************* + + Synopsis [Derives cuts for all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManMerge( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + int i, clk = clock(); + p->pCutsPi = Amap_ManSetupPis( p ); + Amap_ManForEachNode( p, pObj, i ) + Amap_ManMergeNodeCuts( p, pObj ); + if ( p->pPars->fVerbose ) + { + printf( "AIG object is %d bytes. ", sizeof(Amap_Obj_t) ); + printf( "Internal AIG = %5.2f Mb. Cuts = %5.2f Mb.\n", + 1.0*Amap_ManObjNum(p)*sizeof(Amap_Obj_t)/(1<<20), 1.0*p->nBytesUsed/(1<<20) ); + printf( "Node =%6d. Try =%9d. Try3 =%10d. Used =%7d. R =%6.2f. ", + Amap_ManNodeNum(p), p->nCutsTried, p->nCutsTried3, p->nCutsUsed, + 1.0*p->nCutsUsed/Amap_ManNodeNum(p) ); +PRT( "Time ", clock() - clk ); + } +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |