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/amapGraph.c | 389 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 389 insertions(+) create mode 100644 src/map/amap/amapGraph.c (limited to 'src/map/amap/amapGraph.c') diff --git a/src/map/amap/amapGraph.c b/src/map/amap/amapGraph.c new file mode 100644 index 00000000..83cadc2c --- /dev/null +++ b/src/map/amap/amapGraph.c @@ -0,0 +1,389 @@ +/**CFile**************************************************************** + + FileName [amapGraph.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Technology mapper for standard cells.] + + Synopsis [Internal AIG manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: amapGraph.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "amapInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Creates object.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManSetupObj( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + pObj = (Amap_Obj_t *)Aig_MmFixedEntryFetch( p->pMemObj ); + memset( pObj, 0, sizeof(Amap_Obj_t) ); + pObj->nFouts[0] = 1; // needed for flow to work in the first pass + pObj->Id = Vec_PtrSize(p->vObjs); + Vec_PtrPush( p->vObjs, pObj ); + return pObj; +} + +/**Function************************************************************* + + Synopsis [Creates constant 1 node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManCreateConst1( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + pObj = Amap_ManSetupObj( p ); + pObj->Type = AMAP_OBJ_CONST1; + pObj->fPhase = 1; + p->nObjs[AMAP_OBJ_CONST1]++; + return pObj; +} + +/**Function************************************************************* + + Synopsis [Creates primary input.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManCreatePi( Amap_Man_t * p ) +{ + Amap_Obj_t * pObj; + pObj = Amap_ManSetupObj( p ); + pObj->Type = AMAP_OBJ_PI; + pObj->IdPio = Vec_PtrSize( p->vPis ); + Vec_PtrPush( p->vPis, pObj ); + p->nObjs[AMAP_OBJ_PI]++; + return pObj; +} + +/**Function************************************************************* + + Synopsis [Creates primary output with the given driver.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManCreatePo( Amap_Man_t * p, Amap_Obj_t * pFan0 ) +{ + Amap_Obj_t * pObj; + pObj = Amap_ManSetupObj( p ); + pObj->IdPio = Vec_PtrSize( p->vPos ); + Vec_PtrPush( p->vPos, pObj ); + pObj->Type = AMAP_OBJ_PO; + pObj->Fan[0] = Amap_ObjToLit(pFan0); Amap_Regular(pFan0)->nRefs++; + pObj->Level = Amap_Regular(pFan0)->Level; + if ( p->nLevelMax < (int)pObj->Level ) + p->nLevelMax = (int)pObj->Level; + p->nObjs[AMAP_OBJ_PO]++; + return pObj; +} + +/**Function************************************************************* + + Synopsis [Create the new node assuming it does not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManCreateAnd( Amap_Man_t * p, Amap_Obj_t * pFan0, Amap_Obj_t * pFan1 ) +{ + Amap_Obj_t * pObj; + pObj = Amap_ManSetupObj( p ); + pObj->Type = AMAP_OBJ_AND; + pObj->Fan[0] = Amap_ObjToLit(pFan0); Amap_Regular(pFan0)->nRefs++; + pObj->Fan[1] = Amap_ObjToLit(pFan1); Amap_Regular(pFan1)->nRefs++; + assert( Amap_Lit2Var(pObj->Fan[0]) != Amap_Lit2Var(pObj->Fan[1]) ); + pObj->fPhase = Amap_ObjPhaseReal(pFan0) & Amap_ObjPhaseReal(pFan1); + pObj->Level = 1 + AIG_MAX( Amap_Regular(pFan0)->Level, Amap_Regular(pFan1)->Level ); + if ( p->nLevelMax < (int)pObj->Level ) + p->nLevelMax = (int)pObj->Level; + p->nObjs[AMAP_OBJ_AND]++; + return pObj; +} + +/**Function************************************************************* + + Synopsis [Create the new node assuming it does not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManCreateXor( Amap_Man_t * p, Amap_Obj_t * pFan0, Amap_Obj_t * pFan1 ) +{ + Amap_Obj_t * pObj; + pObj = Amap_ManSetupObj( p ); + pObj->Type = AMAP_OBJ_XOR; + pObj->Fan[0] = Amap_ObjToLit(pFan0); Amap_Regular(pFan0)->nRefs++; + pObj->Fan[1] = Amap_ObjToLit(pFan1); Amap_Regular(pFan1)->nRefs++; + pObj->fPhase = Amap_ObjPhaseReal(pFan0) ^ Amap_ObjPhaseReal(pFan1); + pObj->Level = 2 + AIG_MAX( Amap_Regular(pFan0)->Level, Amap_Regular(pFan1)->Level ); + if ( p->nLevelMax < (int)pObj->Level ) + p->nLevelMax = (int)pObj->Level; + p->nObjs[AMAP_OBJ_XOR]++; + return pObj; +} + +/**Function************************************************************* + + Synopsis [Create the new node assuming it does not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManCreateMux( Amap_Man_t * p, Amap_Obj_t * pFan0, Amap_Obj_t * pFan1, Amap_Obj_t * pFanC ) +{ + Amap_Obj_t * pObj; + pObj = Amap_ManSetupObj( p ); + pObj->Type = AMAP_OBJ_MUX; + pObj->Fan[0] = Amap_ObjToLit(pFan0); Amap_Regular(pFan0)->nRefs++; + pObj->Fan[1] = Amap_ObjToLit(pFan1); Amap_Regular(pFan1)->nRefs++; + pObj->Fan[2] = Amap_ObjToLit(pFanC); Amap_Regular(pFanC)->nRefs++; + pObj->fPhase = (Amap_ObjPhaseReal(pFan1) & Amap_ObjPhaseReal(pFanC)) | + (Amap_ObjPhaseReal(pFan0) & ~Amap_ObjPhaseReal(pFanC)); + pObj->Level = AIG_MAX( Amap_Regular(pFan0)->Level, Amap_Regular(pFan1)->Level ); + pObj->Level = 2 + AIG_MAX( pObj->Level, Amap_Regular(pFanC)->Level ); + if ( p->nLevelMax < (int)pObj->Level ) + p->nLevelMax = (int)pObj->Level; + p->nObjs[AMAP_OBJ_MUX]++; + return pObj; +} + +/**Function************************************************************* + + Synopsis [Creates the choice node.] + + Description [Should be called after the equivalence class nodes are linked.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCreateChoice( Amap_Man_t * p, Amap_Obj_t * pObj ) +{ + Amap_Obj_t * pTemp; + // mark the node as a representative if its class +// assert( pObj->fRepr == 0 ); + pObj->fRepr = 1; + // update the level of this node (needed for correct required time computation) + for ( pTemp = pObj; pTemp; pTemp = Amap_ObjChoice(p, pTemp) ) + { + pObj->Level = AIG_MAX( pObj->Level, pTemp->Level ); +// pTemp->nVisits++; pTemp->nVisitsCopy++; + } + // mark the largest level + if ( p->nLevelMax < (int)pObj->Level ) + p->nLevelMax = (int)pObj->Level; +} + +/**Function************************************************************* + + Synopsis [Creates XOR/MUX choices for the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCreateXorChoices( Amap_Man_t * p, Amap_Obj_t * pFan0, Amap_Obj_t * pFan1, Amap_Obj_t * pChoices[] ) +{ + pChoices[0] = Amap_ManCreateXor( p, pFan0, pFan1 ); + pChoices[1] = Amap_ManCreateXor( p, Amap_Not(pFan0), pFan1 ); + pChoices[2] = Amap_ManCreateXor( p, pFan0, Amap_Not(pFan1) ); + pChoices[3] = Amap_ManCreateXor( p, Amap_Not(pFan0), Amap_Not(pFan1) ); +} + +/**Function************************************************************* + + Synopsis [Creates XOR/MUX choices for the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCreateMuxChoices( Amap_Man_t * p, Amap_Obj_t * pFan0, Amap_Obj_t * pFan1, Amap_Obj_t * pFanC, Amap_Obj_t * pChoices[] ) +{ + pChoices[0] = Amap_ManCreateMux( p, pFan0, pFan1, pFanC ); + pChoices[1] = Amap_ManCreateMux( p, Amap_Not(pFan0), Amap_Not(pFan1), pFanC ); + pChoices[2] = Amap_ManCreateMux( p, pFan1, pFan0, Amap_Not(pFanC) ); + pChoices[3] = Amap_ManCreateMux( p, Amap_Not(pFan1), Amap_Not(pFan0), Amap_Not(pFanC) ); +} + +/**Function************************************************************* + + Synopsis [Drags pointer out through the copy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Amap_Obj_t * Amap_AndToObj( Aig_Obj_t * pObj ) +{ + return Amap_NotCond( (Amap_Obj_t *)Aig_Regular(pObj)->pData, Aig_IsComplement(pObj) ); +} + +/**Function************************************************************* + + Synopsis [Starts the AIG manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Amap_Obj_t * Amap_ManGetLast_rec( Amap_Man_t * p, Amap_Obj_t * pObj ) +{ + if ( pObj->Equiv == 0 ) + return pObj; + return Amap_ManGetLast_rec( p, Amap_ObjChoice(p, pObj) ); +} + +/**Function************************************************************* + + Synopsis [Starts the AIG manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_ManCreate( Amap_Man_t * p, Aig_Man_t * pAig ) +{ + Vec_Ptr_t * vNodes; + Amap_Obj_t * pChoices[4]; + Aig_Obj_t * pObj, * pFanin, * pPrev, * pFan0, * pFan1, * pFanC; + int i, fChoices; + if ( pAig->pEquivs ) + vNodes = Aig_ManDfsChoices( pAig ); + else + vNodes = Aig_ManDfs( pAig, 1 ); + p->pConst1 = Amap_ManCreateConst1( p ); + // print warning about excessive memory usage + if ( p->pPars->fVerbose ) + { + if ( 1.0 * Aig_ManObjNum(pAig) * sizeof(Amap_Obj_t) / (1<<30) > 0.1 ) + printf( "Warning: Mapper allocates %.3f Gb for subject graph with %d objects.\n", + 1.0 * Aig_ManObjNum(pAig) * sizeof(Amap_Obj_t) / (1<<30), Aig_ManObjNum(pAig) ); + } + // create PIs and remember them in the old nodes + Aig_ManCleanData(pAig); + Aig_ManConst1(pAig)->pData = Amap_ManConst1( p ); + Aig_ManForEachPi( pAig, pObj, i ) + pObj->pData = Amap_ManCreatePi( p ); + // load the AIG into the mapper + Vec_PtrForEachEntry( vNodes, pObj, i ) + { + fChoices = 0; + if ( p->fUseXor && Aig_ObjRecognizeExor(pObj, &pFan0, &pFan1 ) ) + { + Amap_ManCreateXorChoices( p, Amap_AndToObj(pFan0), Amap_AndToObj(pFan1), pChoices ); + fChoices = 1; + } + else if ( p->fUseMux && Aig_ObjIsMuxType(pObj) ) + { + pFanC = Aig_ObjRecognizeMux( pObj, &pFan1, &pFan0 ); + Amap_ManCreateMuxChoices( p, Amap_AndToObj(pFan0), Amap_AndToObj(pFan1), Amap_AndToObj(pFanC), pChoices ); + fChoices = 1; + } + pObj->pData = Amap_ManCreateAnd( p, (Amap_Obj_t *)Aig_ObjChild0Copy(pObj), (Amap_Obj_t *)Aig_ObjChild1Copy(pObj) ); + if ( fChoices ) + { + p->nChoicesAdded++; + Amap_ObjSetChoice( (Amap_Obj_t *)pObj->pData, pChoices[0] ); + Amap_ObjSetChoice( pChoices[0], pChoices[1] ); + Amap_ObjSetChoice( pChoices[1], pChoices[2] ); + Amap_ObjSetChoice( pChoices[2], pChoices[3] ); + Amap_ManCreateChoice( p, (Amap_Obj_t *)pObj->pData ); + } + if ( Aig_ObjIsChoice( pAig, pObj ) ) + { +// assert( !fChoices ); + p->nChoicesGiven++; + for ( pPrev = pObj, pFanin = Aig_ObjEquiv(pAig, pObj); pFanin; pPrev = pFanin, pFanin = Aig_ObjEquiv(pAig, pFanin) ) + { + ((Amap_Obj_t *)pFanin->pData)->fRepr = 0; + Amap_ObjSetChoice( Amap_ManGetLast_rec(p, (Amap_Obj_t *)pPrev->pData), + (Amap_Obj_t *)pFanin->pData ); + } + Amap_ManCreateChoice( p, (Amap_Obj_t *)pObj->pData ); + } + } + Vec_PtrFree( vNodes ); + // set the primary outputs without copying the phase + Aig_ManForEachPo( pAig, pObj, i ) + pObj->pData = Amap_ManCreatePo( p, (Amap_Obj_t *)Aig_ObjChild0Copy(pObj) ); + if ( p->pPars->fVerbose ) + printf( "Performing mapping with %d given and %d created choices.\n", + p->nChoicesGiven, p->nChoicesAdded ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3