/**CFile**************************************************************** FileName [aigTsim.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [AIG package.] Synopsis [Ternary simulation.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - April 28, 2007.] Revision [$Id: aigTsim.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] ***********************************************************************/ #include "aig.h" #include "aig/saig/saig.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// #define TSI_MAX_ROUNDS 1000 #define TSI_ONE_SERIES 300 #define AIG_XVS0 1 #define AIG_XVS1 2 #define AIG_XVSX 3 static inline void Aig_ObjSetXsim( Aig_Obj_t * pObj, int Value ) { pObj->nCuts = Value; } static inline int Aig_ObjGetXsim( Aig_Obj_t * pObj ) { return pObj->nCuts; } static inline int Aig_XsimInv( int Value ) { if ( Value == AIG_XVS0 ) return AIG_XVS1; if ( Value == AIG_XVS1 ) return AIG_XVS0; assert( Value == AIG_XVSX ); return AIG_XVSX; } static inline int Aig_XsimAnd( int Value0, int Value1 ) { if ( Value0 == AIG_XVS0 || Value1 == AIG_XVS0 ) return AIG_XVS0; if ( Value0 == AIG_XVSX || Value1 == AIG_XVSX ) return AIG_XVSX; assert( Value0 == AIG_XVS1 && Value1 == AIG_XVS1 ); return AIG_XVS1; } static inline int Aig_XsimRand2() { return (Aig_ManRandom(0) & 1) ? AIG_XVS1 : AIG_XVS0; } static inline int Aig_XsimRand3() { int RetValue; do { RetValue = Aig_ManRandom(0) & 3; } while ( RetValue == 0 ); return RetValue; } static inline int Aig_ObjGetXsimFanin0( Aig_Obj_t * pObj ) { int RetValue; RetValue = Aig_ObjGetXsim(Aig_ObjFanin0(pObj)); return Aig_ObjFaninC0(pObj)? Aig_XsimInv(RetValue) : RetValue; } static inline int Aig_ObjGetXsimFanin1( Aig_Obj_t * pObj ) { int RetValue; RetValue = Aig_ObjGetXsim(Aig_ObjFanin1(pObj)); return Aig_ObjFaninC1(pObj)? Aig_XsimInv(RetValue) : RetValue; } static inline void Aig_XsimPrint( FILE * pFile, int Value ) { if ( Value == AIG_XVS0 ) { fprintf( pFile, "0" ); return; } if ( Value == AIG_XVS1 ) { fprintf( pFile, "1" ); return; } assert( Value == AIG_XVSX ); fprintf( pFile, "x" ); } // simulation manager typedef struct Aig_Tsi_t_ Aig_Tsi_t; struct Aig_Tsi_t_ { Aig_Man_t * pAig; // the original AIG manager // ternary state representation int nWords; // the number of words in the states Vec_Ptr_t * vStates; // the collection of ternary states Aig_MmFixed_t * pMem; // memory for ternary states // hash table for terminary states unsigned ** pBins; int nBins; }; static inline unsigned * Aig_TsiNext( unsigned * pState, int nWords ) { return *((unsigned **)(pState + nWords)); } static inline void Aig_TsiSetNext( unsigned * pState, int nWords, unsigned * pNext ) { *((unsigned **)(pState + nWords)) = pNext; } //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Allocates simulation manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Tsi_t * Aig_TsiStart( Aig_Man_t * pAig ) { Aig_Tsi_t * p; p = ABC_ALLOC( Aig_Tsi_t, 1 ); memset( p, 0, sizeof(Aig_Tsi_t) ); p->pAig = pAig; p->nWords = Abc_BitWordNum( 2*Aig_ManRegNum(pAig) ); p->vStates = Vec_PtrAlloc( 1000 ); p->pMem = Aig_MmFixedStart( sizeof(unsigned) * p->nWords + sizeof(unsigned *), 10000 ); p->nBins = Abc_PrimeCudd(TSI_MAX_ROUNDS/2); p->pBins = ABC_ALLOC( unsigned *, p->nBins ); memset( p->pBins, 0, sizeof(unsigned *) * p->nBins ); return p; } /**Function************************************************************* Synopsis [Deallocates simulation manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_TsiStop( Aig_Tsi_t * p ) { Aig_MmFixedStop( p->pMem, 0 ); Vec_PtrFree( p->vStates ); ABC_FREE( p->pBins ); ABC_FREE( p ); } /**Function************************************************************* Synopsis [Computes hash value of the node using its simulation info.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Aig_TsiStateHash( unsigned * pState, int nWords, int nTableSize ) { static int s_FPrimes[128] = { 1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459, 1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997, 2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543, 2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089, 3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671, 3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243, 4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871, 4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471, 5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073, 6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689, 6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309, 7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933, 8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147 }; unsigned uHash; int i; uHash = 0; for ( i = 0; i < nWords; i++ ) uHash ^= pState[i] * s_FPrimes[i & 0x7F]; return uHash % nTableSize; } /**Function************************************************************* Synopsis [Inserts value into the table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Aig_TsiStateLookup( Aig_Tsi_t * p, unsigned * pState, int nWords ) { unsigned * pEntry; int Hash; Hash = Aig_TsiStateHash( pState, nWords, p->nBins ); for ( pEntry = p->pBins[Hash]; pEntry; pEntry = Aig_TsiNext(pEntry, nWords) ) if ( !memcmp( pEntry, pState, sizeof(unsigned) * nWords ) ) return 1; return 0; } /**Function************************************************************* Synopsis [Inserts value into the table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_TsiStateInsert( Aig_Tsi_t * p, unsigned * pState, int nWords ) { int Hash = Aig_TsiStateHash( pState, nWords, p->nBins ); assert( !Aig_TsiStateLookup( p, pState, nWords ) ); Aig_TsiSetNext( pState, nWords, p->pBins[Hash] ); p->pBins[Hash] = pState; } /**Function************************************************************* Synopsis [Inserts value into the table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ unsigned * Aig_TsiStateNew( Aig_Tsi_t * p ) { unsigned * pState; pState = (unsigned *)Aig_MmFixedEntryFetch( p->pMem ); memset( pState, 0, sizeof(unsigned) * p->nWords ); Vec_PtrPush( p->vStates, pState ); return pState; } /**Function************************************************************* Synopsis [Inserts value into the table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_TsiStatePrint( Aig_Tsi_t * p, unsigned * pState ) { int i, Value, nZeros = 0, nOnes = 0, nDcs = 0; for ( i = 0; i < Aig_ManRegNum(p->pAig); i++ ) { Value = (Abc_InfoHasBit( pState, 2 * i + 1 ) << 1) | Abc_InfoHasBit( pState, 2 * i ); if ( Value == 1 ) printf( "0" ), nZeros++; else if ( Value == 2 ) printf( "1" ), nOnes++; else if ( Value == 3 ) printf( "x" ), nDcs++; else assert( 0 ); } printf( " (0=%5d, 1=%5d, x=%5d)\n", nZeros, nOnes, nDcs ); } /**Function************************************************************* Synopsis [Count constant values in the state.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Aig_TsiStateCount( Aig_Tsi_t * p, unsigned * pState ) { Aig_Obj_t * pObjLi, * pObjLo; int i, Value, nCounter = 0; Aig_ManForEachLiLoSeq( p->pAig, pObjLi, pObjLo, i ) { Value = (Abc_InfoHasBit( pState, 2 * i + 1 ) << 1) | Abc_InfoHasBit( pState, 2 * i ); nCounter += (Value == 1 || Value == 2); } return nCounter; } /**Function************************************************************* Synopsis [Count constant values in the state.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_TsiStateOrAll( Aig_Tsi_t * pTsi, unsigned * pState ) { unsigned * pPrev; int i, k; Vec_PtrForEachEntry( unsigned *, pTsi->vStates, pPrev, i ) { for ( k = 0; k < pTsi->nWords; k++ ) pState[k] |= pPrev[k]; } } /**Function************************************************************* Synopsis [Cycles the circuit to create a new initial state.] Description [Simulates the circuit with random input for the given number of timeframes to get a better initial state.] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManTernarySimulate( Aig_Man_t * p, int fVerbose, int fVeryVerbose ) { Aig_Tsi_t * pTsi; Vec_Ptr_t * vMap; Aig_Obj_t * pObj, * pObjLi, * pObjLo; unsigned * pState;//, * pPrev; int i, f, fConstants, Value, nCounter, nRetired; // allocate the simulation manager pTsi = Aig_TsiStart( p ); // initialize the values Aig_ObjSetXsim( Aig_ManConst1(p), AIG_XVS1 ); Aig_ManForEachPiSeq( p, pObj, i ) Aig_ObjSetXsim( pObj, AIG_XVSX ); Aig_ManForEachLoSeq( p, pObj, i ) Aig_ObjSetXsim( pObj, AIG_XVS0 ); // simulate for the given number of timeframes for ( f = 0; f < TSI_MAX_ROUNDS; f++ ) { // collect this state pState = Aig_TsiStateNew( pTsi ); Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) { Value = Aig_ObjGetXsim(pObjLo); if ( Value & 1 ) Abc_InfoSetBit( pState, 2 * i ); if ( Value & 2 ) Abc_InfoSetBit( pState, 2 * i + 1 ); } // printf( "%d ", Aig_TsiStateCount(pTsi, pState) ); if ( fVeryVerbose ) { printf( "%3d : ", f ); Aig_TsiStatePrint( pTsi, pState ); } // check if this state exists if ( Aig_TsiStateLookup( pTsi, pState, pTsi->nWords ) ) break; // nCounter = 0; // Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) // nCounter += (Aig_ObjGetXsim(pObjLo) == AIG_XVS0); //printf( "%d -> ", nCounter ); // insert this state Aig_TsiStateInsert( pTsi, pState, pTsi->nWords ); // simulate internal nodes Aig_ManForEachNode( p, pObj, i ) { Aig_ObjSetXsim( pObj, Aig_XsimAnd(Aig_ObjGetXsimFanin0(pObj), Aig_ObjGetXsimFanin1(pObj)) ); // printf( "%d %d Id = %2d. Value = %d.\n", // Aig_ObjGetXsimFanin0(pObj), Aig_ObjGetXsimFanin1(pObj), // i, Aig_XsimAnd(Aig_ObjGetXsimFanin0(pObj), Aig_ObjGetXsimFanin1(pObj)) ); } // transfer the latch values Aig_ManForEachLiSeq( p, pObj, i ) Aig_ObjSetXsim( pObj, Aig_ObjGetXsimFanin0(pObj) ); nCounter = 0; nRetired = 0; Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) { if ( f < TSI_ONE_SERIES ) Aig_ObjSetXsim( pObjLo, Aig_ObjGetXsim(pObjLi) ); else { if ( Aig_ObjGetXsim(pObjLi) != Aig_ObjGetXsim(pObjLo) ) { Aig_ObjSetXsim( pObjLo, AIG_XVSX ); nRetired++; } } nCounter += (Aig_ObjGetXsim(pObjLo) == AIG_XVS0); } // if ( nRetired ) // printf( "Retired %d registers.\n", nRetired ); // if ( f && (f % 1000 == 0) ) // printf( "%d \n", f ); //printf( "%d ", nCounter ); } //printf( "\n" ); if ( f == TSI_MAX_ROUNDS ) { printf( "Aig_ManTernarySimulate(): Did not reach a fixed point after %d iterations (not a bug).\n", TSI_MAX_ROUNDS ); Aig_TsiStop( pTsi ); return NULL; } // OR all the states pState = (unsigned *)Vec_PtrEntry( pTsi->vStates, 0 ); Aig_TsiStateOrAll( pTsi, pState ); // check if there are constants fConstants = 0; if ( 2*Aig_ManRegNum(p) == 32*pTsi->nWords ) { for ( i = 0; i < pTsi->nWords; i++ ) if ( pState[i] != ~0 ) fConstants = 1; } else { for ( i = 0; i < pTsi->nWords - 1; i++ ) if ( pState[i] != ~0 ) fConstants = 1; if ( pState[i] != Abc_InfoMask( 2*Aig_ManRegNum(p) - 32*(pTsi->nWords-1) ) ) fConstants = 1; } if ( fConstants == 0 ) { if ( fVerbose ) printf( "Detected 0 constants after %d iterations of ternary simulation.\n", f ); Aig_TsiStop( pTsi ); return NULL; } // start mapping by adding the true PIs vMap = Vec_PtrAlloc( Aig_ManCiNum(p) ); Aig_ManForEachPiSeq( p, pObj, i ) Vec_PtrPush( vMap, pObj ); // find constant registers nCounter = 0; Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) { Value = (Abc_InfoHasBit( pState, 2 * i + 1 ) << 1) | Abc_InfoHasBit( pState, 2 * i ); nCounter += (Value == 1 || Value == 2); if ( Value == 1 ) Vec_PtrPush( vMap, Aig_ManConst0(p) ); else if ( Value == 2 ) Vec_PtrPush( vMap, Aig_ManConst1(p) ); else if ( Value == 3 ) Vec_PtrPush( vMap, pObjLo ); else assert( 0 ); // Aig_XsimPrint( stdout, Value ); } // printf( "\n" ); Aig_TsiStop( pTsi ); if ( fVerbose ) printf( "Detected %d constants after %d iterations of ternary simulation.\n", nCounter, f ); return vMap; } /**Function************************************************************* Synopsis [Reduces the circuit using ternary simulation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Man_t * Aig_ManConstReduce( Aig_Man_t * p, int fUseMvSweep, int nFramesSymb, int nFramesSatur, int fVerbose, int fVeryVerbose ) { Aig_Man_t * pTemp; Vec_Ptr_t * vMap; while ( Aig_ManRegNum(p) > 0 ) { if ( fUseMvSweep ) vMap = Saig_MvManSimulate( p, nFramesSymb, nFramesSatur, fVerbose, fVeryVerbose ); else vMap = Aig_ManTernarySimulate( p, fVerbose, fVeryVerbose ); if ( vMap == NULL ) break; p = Aig_ManRemap( pTemp = p, vMap ); Vec_PtrFree( vMap ); Aig_ManSeqCleanup( p ); if ( fVerbose ) Aig_ManReportImprovement( pTemp, p ); Aig_ManStop( pTemp ); } return p; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END