diff options
Diffstat (limited to 'src/aig/gia/giaBalMap.c')
-rw-r--r-- | src/aig/gia/giaBalMap.c | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/src/aig/gia/giaBalMap.c b/src/aig/gia/giaBalMap.c new file mode 100644 index 00000000..b285daea --- /dev/null +++ b/src/aig/gia/giaBalMap.c @@ -0,0 +1,326 @@ +/**CFile**************************************************************** + + FileName [giaSopb.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [SOP balancing for a window.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: giaSopb.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManHighlight_rec( Gia_Man_t * p, int iObj ) +{ + Gia_Obj_t * pObj; + if ( Gia_ObjIsTravIdCurrentId(p, iObj) ) + return; + Gia_ObjSetTravIdCurrentId(p, iObj); + pObj = Gia_ManObj( p, iObj ); + if ( Gia_ObjIsAnd(pObj) ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId0(pObj, iObj) ); + if ( Gia_ObjIsAnd(pObj) ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId1(pObj, iObj) ); +} +void Gia_ManPrepareWin( Gia_Man_t * p, Vec_Int_t * vOuts, Vec_Int_t ** pvPis, Vec_Int_t ** pvPos, Vec_Int_t ** pvAnds, int fPoOnly ) +{ + Gia_Obj_t * pObj; + int i; + // mark the section + Gia_ManIncrementTravId( p ); + Gia_ManForEachCoVec( vOuts, p, pObj, i ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId0p(p, pObj) ); + // mark fanins of the outside area + Gia_ManCleanMark0( p ); + if ( fPoOnly ) + { + Gia_ManForEachCoVec( vOuts, p, pObj, i ) + Gia_ObjFanin0(pObj)->fMark0 = 1; + } + else + { + Gia_ManForEachObj1( p, pObj, i ) + { + if ( Gia_ObjIsCi(pObj) ) + continue; + if ( Gia_ObjIsAnd(pObj) && !Gia_ObjIsTravIdCurrentId(p, i) ) + continue; + Gia_ObjFanin0(pObj)->fMark0 = 1; + if ( Gia_ObjIsAnd(pObj) ) + Gia_ObjFanin1(pObj)->fMark0 = 1; + } + } + // collect pointed nodes + *pvPis = Vec_IntAlloc( 1000 ); + *pvPos = Vec_IntAlloc( 1000 ); + *pvAnds = Vec_IntAlloc( 1000 ); + Gia_ManForEachObj1( p, pObj, i ) + { + if ( !Gia_ObjIsTravIdCurrentId(p, i) ) + continue; + if ( Gia_ObjIsCi(pObj) ) + Vec_IntPush( *pvPis, i ); + else if ( pObj->fMark0 ) + Vec_IntPush( *pvPos, i ); + if ( Gia_ObjIsAnd(pObj) ) + Vec_IntPush( *pvAnds, i ); + } + Gia_ManCleanMark0( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManExtractWin( Gia_Man_t * p, Vec_Int_t * vOuts, int fPoOnly ) +{ + Vec_Int_t * vPis, * vPos, * vAnds; + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i; + Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, fPoOnly ); + // create AIG + pNew = Gia_ManStart( Vec_IntSize(vPis) + Vec_IntSize(vPos) + Vec_IntSize(vAnds) + 1 ); + pNew->pName = Abc_UtilStrsav( p->pName ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachObjVec( vPis, p, pObj, i ) + pObj->Value = Gia_ManAppendCi( pNew ); + Gia_ManForEachObjVec( vAnds, p, pObj, i ) + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachObjVec( vPos, p, pObj, i ) + Gia_ManAppendCo( pNew, pObj->Value ); + Vec_IntFree( vPis ); + Vec_IntFree( vPos ); + Vec_IntFree( vAnds ); + return pNew; +} +Gia_Man_t * Gia_ManInsertWin( Gia_Man_t * p, Vec_Int_t * vOuts, Gia_Man_t * pWin ) +{ + Vec_Int_t * vPos, * vPis, * vAnds; + Gia_Man_t * pNew, * pTemp; + Gia_Obj_t * pObj; + int i; + Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, 0 ); + // create AIG + pNew = Gia_ManStart( Gia_ManObjNum(p) - Vec_IntSize(vAnds) + Gia_ManAndNum(pWin) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + // inputs + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachCi( p, pObj, i ) + pObj->Value = Gia_ManAppendCi( pNew ); + Gia_ManConst0(pWin)->Value = 0; + Gia_ManForEachCi( pWin, pObj, i ) + pObj->Value = Gia_ManObj(p, Vec_IntEntry(vPis, i))->Value; + // internal nodes + Gia_ManHashAlloc( pNew ); + Gia_ManForEachAnd( pWin, pObj, i ) + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( pWin, pObj, i ) + Gia_ManObj( p, Vec_IntEntry(vPos, i) )->Value = Gia_ObjFanin0Copy(pObj); + Gia_ManForEachAnd( p, pObj, i ) + if ( !Gia_ObjIsTravIdCurrentId(p, i) ) + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( p, pObj, i ) + Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + Gia_ManHashStop( pNew ); + // cleanup + Vec_IntFree( vPis ); + Vec_IntFree( vPos ); + Vec_IntFree( vAnds ); + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManFindLatest( Gia_Man_t * p, int LevelMax, int nTimeWindow ) +{ + Gia_Obj_t * pObj; + Vec_Int_t * vOuts; + vOuts = Vec_IntAlloc( 1000 ); + if ( Gia_ManHasMapping(p) ) + { + int i, k, iFan, nLevels = 0; + int * pLevels = ABC_CALLOC( int, Gia_ManObjNum(p) ); + Gia_ManForEachLut( p, i ) + { + Gia_LutForEachFanin( p, i, iFan, k ) + pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[iFan] ); + pLevels[i]++; + nLevels = Abc_MaxInt( nLevels, pLevels[i] ); + } + if ( nTimeWindow ) + LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels); + if ( nLevels < LevelMax ) + printf( "The maximum mapped level (%d) is less than the target level (%d).\n", nLevels, LevelMax ); + Gia_ManForEachCo( p, pObj, i ) + if ( pLevels[Gia_ObjFaninId0p(p, pObj)] >= LevelMax ) + Vec_IntPush( vOuts, i ); + ABC_FREE( pLevels ); + } + else + { + int i, nLevels = Gia_ManLevelNum( p ); + if ( nTimeWindow ) + LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels); + if ( nLevels < LevelMax ) + printf( "The maximum AIG level (%d) is less than the target level (%d).\n", nLevels, LevelMax ); + Gia_ManForEachCo( p, pObj, i ) + if ( Gia_ObjLevel(p, pObj) >= LevelMax ) + Vec_IntPush( vOuts, i ); + } + return vOuts; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManExtractWindow( Gia_Man_t * p, int LevelMax, int nTimeWindow, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pWin; + assert( !LevelMax != !nTimeWindow ); + vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); + if ( fVerbose ) + printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts, 1 ); + Vec_IntFree( vOuts ); + return pWin; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManPerformSopBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pNew, * pWin, * pWinNew; + assert( !LevelMax != !nTimeWindow ); + vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); + if ( fVerbose ) + printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts, 0 ); + pWinNew = Gia_ManPerformSopBalance( pWin, nCutNum, nRelaxRatio, fVerbose ); + Gia_ManStop( pWin ); + pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); + Gia_ManStop( pWinNew ); + Vec_IntFree( vOuts ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManPerformDsdBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pNew, * pWin, * pWinNew; + assert( !LevelMax != !nTimeWindow ); + vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow ); + if ( fVerbose ) + printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts, 0 ); + pWinNew = Gia_ManPerformDsdBalance( pWin, nLutSize, nCutNum, nRelaxRatio, fVerbose ); + Gia_ManStop( pWin ); + pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); + Gia_ManStop( pWinNew ); + Vec_IntFree( vOuts ); + return pNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + |