src/aig/aig/aigTsim.c

Go to the documentation of this file.

#include "aig.h"


#define TSI_MAX_ROUNDS    1000

#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; }


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;
}

void Aig_TsiStop( Aig_Tsi_t * p )
{
    Aig_MmFixedStop( p->pMem, 0 );
    Vec_PtrFree( p->vStates );
    free( p->pBins );
    free( p );
}

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;
}

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;
}

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;    
}

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;
}

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 );
}


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 (not a bug).\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;
}

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;
}

---