diff options
Diffstat (limited to 'src/aig/aig/aigTsim.c')
| -rw-r--r-- | src/aig/aig/aigTsim.c | 436 |
1 files changed, 436 insertions, 0 deletions
diff --git a/src/aig/aig/aigTsim.c b/src/aig/aig/aigTsim.c new file mode 100644 index 00000000..b8296cb2 --- /dev/null +++ b/src/aig/aig/aigTsim.c @@ -0,0 +1,436 @@ +/**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" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define TSI_MAX_ROUNDS 10000 + +#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 (rand() & 1) ? AIG_XVS1 : AIG_XVS0; +} +static inline int Aig_XsimRand3() +{ + int RetValue; + do { + RetValue = rand() & 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 = (Aig_Tsi_t *)malloc( sizeof(Aig_Tsi_t) ); + memset( p, 0, sizeof(Aig_Tsi_t) ); + p->pAig = pAig; + p->nWords = Aig_BitWordNum( 2*Aig_ManRegNum(pAig) ); + p->vStates = Vec_PtrAlloc( 1000 ); + p->pMem = Aig_MmFixedStart( sizeof(unsigned) * p->nWords + sizeof(unsigned *), 10000 ); + p->nBins = Aig_PrimeCudd(TSI_MAX_ROUNDS/2); + p->pBins = 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 ); + free( p->pBins ); + 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 = (Aig_InfoHasBit( pState, 2 * i + 1 ) << 1) | Aig_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 [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 ) +{ + Aig_Tsi_t * pTsi; + Vec_Ptr_t * vMap; + Aig_Obj_t * pObj, * pObjLi, * pObjLo; + unsigned * pState, * pPrev; + int i, k, f, fConstants, Value, nCounter; + // 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 ) + Aig_InfoSetBit( pState, 2 * i ); + if ( Value & 2 ) + Aig_InfoSetBit( pState, 2 * i + 1 ); + } +// Aig_TsiStatePrint( pTsi, pState ); + // check if this state exists + if ( Aig_TsiStateLookup( pTsi, pState, pTsi->nWords ) ) + break; + // 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)) ); + // transfer the latch values + Aig_ManForEachLiSeq( p, pObj, i ) + Aig_ObjSetXsim( pObj, Aig_ObjGetXsimFanin0(pObj) ); + Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) + Aig_ObjSetXsim( pObjLo, Aig_ObjGetXsim(pObjLi) ); + } + if ( f == TSI_MAX_ROUNDS ) + { + printf( "Aig_ManTernarySimulate(): Did not reach a fixed point after %d iterations.\n", TSI_MAX_ROUNDS ); + Aig_TsiStop( pTsi ); + return NULL; + } + // OR all the states + pState = Vec_PtrEntry( pTsi->vStates, 0 ); + Vec_PtrForEachEntry( pTsi->vStates, pPrev, i ) + { + for ( k = 0; k < pTsi->nWords; k++ ) + pState[k] |= pPrev[k]; + } + // 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] != Aig_InfoMask( 2*Aig_ManRegNum(p) - 32*(pTsi->nWords-1) ) ) + fConstants = 1; + } + if ( fConstants == 0 ) + { + Aig_TsiStop( pTsi ); + return NULL; + } + + // start mapping by adding the true PIs + vMap = Vec_PtrAlloc( Aig_ManPiNum(p) ); + Aig_ManForEachPiSeq( p, pObj, i ) + Vec_PtrPush( vMap, pObj ); + // find constant registers + nCounter = 0; + Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) + { + Value = (Aig_InfoHasBit( pState, 2 * i + 1 ) << 1) | Aig_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 fVerbose ) +{ + Aig_Man_t * pTemp; + Vec_Ptr_t * vMap; + while ( vMap = Aig_ManTernarySimulate( p, fVerbose ) ) + { + if ( fVerbose ) + printf( "RBeg = %5d. NBeg = %6d. ", Aig_ManRegNum(p), Aig_ManNodeNum(p) ); + p = Aig_ManRemap( pTemp = p, vMap ); + Aig_ManStop( pTemp ); + Vec_PtrFree( vMap ); + Aig_ManSeqCleanup( p ); + if ( fVerbose ) + printf( "REnd = %5d. NEnd = %6d. \n", Aig_ManRegNum(p), Aig_ManNodeNum(p) ); + } + return p; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |