aigTsim.c File Reference

#include "aig.h"
#include "aig/saig/saig.h"

Go to the source code of this file.

Data Structures
struct	Aig_Tsi_t_

Macros
#define	TSI_MAX_ROUNDS   1000
	DECLARATIONS ///. More...
#define	TSI_ONE_SERIES   300
#define	AIG_XVS0   1
#define	AIG_XVS1   2
#define	AIG_XVSX   3

Typedefs
typedef struct Aig_Tsi_t_	Aig_Tsi_t

Functions
static void	Aig_ObjSetXsim (Aig_Obj_t *pObj, int Value)
static int	Aig_ObjGetXsim (Aig_Obj_t *pObj)
static int	Aig_XsimInv (int Value)
static int	Aig_XsimAnd (int Value0, int Value1)
static int	Aig_XsimRand2 ()
static int	Aig_XsimRand3 ()
static int	Aig_ObjGetXsimFanin0 (Aig_Obj_t *pObj)
static int	Aig_ObjGetXsimFanin1 (Aig_Obj_t *pObj)
static void	Aig_XsimPrint (FILE *pFile, int Value)
static unsigned *	Aig_TsiNext (unsigned *pState, int nWords)
static void	Aig_TsiSetNext (unsigned *pState, int nWords, unsigned *pNext)
Aig_Tsi_t *	Aig_TsiStart (Aig_Man_t *pAig)
	FUNCTION DEFINITIONS ///. More...
void	Aig_TsiStop (Aig_Tsi_t *p)
int	Aig_TsiStateHash (unsigned *pState, int nWords, int nTableSize)
int	Aig_TsiStateLookup (Aig_Tsi_t *p, unsigned *pState, int nWords)
void	Aig_TsiStateInsert (Aig_Tsi_t *p, unsigned *pState, int nWords)
unsigned *	Aig_TsiStateNew (Aig_Tsi_t *p)
void	Aig_TsiStatePrint (Aig_Tsi_t *p, unsigned *pState)
int	Aig_TsiStateCount (Aig_Tsi_t *p, unsigned *pState)
void	Aig_TsiStateOrAll (Aig_Tsi_t *pTsi, unsigned *pState)
Vec_Ptr_t *	Aig_ManTernarySimulate (Aig_Man_t *p, int fVerbose, int fVeryVerbose)
Aig_Man_t *	Aig_ManConstReduce (Aig_Man_t *p, int fUseMvSweep, int nFramesSymb, int nFramesSatur, int fVerbose, int fVeryVerbose)

Macro Definition Documentation

#define AIG_XVS0   1

Definition at line 34 of file aigTsim.c.

#define AIG_XVS1   2

Definition at line 35 of file aigTsim.c.

#define AIG_XVSX   3

Definition at line 36 of file aigTsim.c.

#define TSI_MAX_ROUNDS   1000

DECLARATIONS ///.

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

]

Definition at line 31 of file aigTsim.c.

#define TSI_ONE_SERIES   300

Definition at line 32 of file aigTsim.c.

Typedef Documentation

typedef struct Aig_Tsi_t_ Aig_Tsi_t

Definition at line 99 of file aigTsim.c.

Function Documentation

Aig_Man_t* Aig_ManConstReduce	(	Aig_Man_t *	p,
		int	fUseMvSweep,
		int	nFramesSymb,
		int	nFramesSatur,
		int	fVerbose,
		int	fVeryVerbose
	)

Function*************************************************************

Synopsis [Reduces the circuit using ternary simulation.]

Description []

SideEffects []

SeeAlso []

Definition at line 498 of file aigTsim.c.

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

Vec_Ptr_t* Aig_ManTernarySimulate	(	Aig_Man_t *	p,
		int	fVerbose,
		int	fVeryVerbose
	)

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 []

Definition at line 348 of file aigTsim.c.

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

static int Aig_ObjGetXsim ( Aig_Obj_t *  pObj )

inlinestatic

Definition at line 39 of file aigTsim.c.

{ return pObj->nCuts;   }

static int Aig_ObjGetXsimFanin0 ( Aig_Obj_t *  pObj )

inlinestatic

Definition at line 70 of file aigTsim.c.

{ 
    int RetValue;
    RetValue = Aig_ObjGetXsim(Aig_ObjFanin0(pObj));
    return Aig_ObjFaninC0(pObj)? Aig_XsimInv(RetValue) : RetValue;
}

static int Aig_ObjGetXsimFanin1 ( Aig_Obj_t *  pObj )

inlinestatic

Definition at line 76 of file aigTsim.c.

{ 
    int RetValue;
    RetValue = Aig_ObjGetXsim(Aig_ObjFanin1(pObj));
    return Aig_ObjFaninC1(pObj)? Aig_XsimInv(RetValue) : RetValue;
}

static void Aig_ObjSetXsim ( Aig_Obj_t *  pObj, int  Value  )

inlinestatic

Definition at line 38 of file aigTsim.c.

{ pObj->nCuts = Value;  }

static unsigned* Aig_TsiNext ( unsigned *  pState, int  nWords  )

inlinestatic

Definition at line 112 of file aigTsim.c.

{ return *((unsigned **)(pState + nWords));  }

static void Aig_TsiSetNext ( unsigned *  pState, int  nWords, unsigned *  pNext  )

inlinestatic

Definition at line 113 of file aigTsim.c.

{ *((unsigned **)(pState + nWords)) = pNext; }

Aig_Tsi_t* Aig_TsiStart

(

Aig_Man_t *

pAig

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Allocates simulation manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 130 of file aigTsim.c.

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

int Aig_TsiStateCount	(	Aig_Tsi_t *	p,
		unsigned *	pState
	)

Function*************************************************************

Synopsis [Count constant values in the state.]

Description []

SideEffects []

SeeAlso []

Definition at line 301 of file aigTsim.c.

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

int Aig_TsiStateHash	(	unsigned *	pState,
		int	nWords,
		int	nTableSize
	)

Function*************************************************************

Synopsis [Computes hash value of the node using its simulation info.]

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file aigTsim.c.

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

void Aig_TsiStateInsert	(	Aig_Tsi_t *	p,
		unsigned *	pState,
		int	nWords
	)

Function*************************************************************

Synopsis [Inserts value into the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 233 of file aigTsim.c.

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

int Aig_TsiStateLookup	(	Aig_Tsi_t *	p,
		unsigned *	pState,
		int	nWords
	)

Function*************************************************************

Synopsis [Inserts value into the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 211 of file aigTsim.c.

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

unsigned* Aig_TsiStateNew

(

Aig_Tsi_t *

p

)

Function*************************************************************

Synopsis [Inserts value into the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 252 of file aigTsim.c.

{
    unsigned * pState;
    pState = (unsigned *)Aig_MmFixedEntryFetch( p->pMem );
    memset( pState, 0, sizeof(unsigned) * p->nWords );
    Vec_PtrPush( p->vStates, pState );
    return pState;
}

void Aig_TsiStateOrAll	(	Aig_Tsi_t *	pTsi,
		unsigned *	pState
	)

Function*************************************************************

Synopsis [Count constant values in the state.]

Description []

SideEffects []

SeeAlso []

Definition at line 324 of file aigTsim.c.

{
    unsigned * pPrev;
    int i, k;
    Vec_PtrForEachEntry( unsigned *, pTsi->vStates, pPrev, i )
    {
        for ( k = 0; k < pTsi->nWords; k++ )
            pState[k] |= pPrev[k];
    }
}

void Aig_TsiStatePrint	(	Aig_Tsi_t *	p,
		unsigned *	pState
	)

Function*************************************************************

Synopsis [Inserts value into the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 272 of file aigTsim.c.

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

void Aig_TsiStop

(

Aig_Tsi_t *

p

)

Function*************************************************************

Synopsis [Deallocates simulation manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 156 of file aigTsim.c.

{
    Aig_MmFixedStop( p->pMem, 0 );
    Vec_PtrFree( p->vStates );
    ABC_FREE( p->pBins );
    ABC_FREE( p );
}

static int Aig_XsimAnd ( int  Value0, int  Value1  )

inlinestatic

Definition at line 49 of file aigTsim.c.

{ 
    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 int Aig_XsimInv ( int  Value )

inlinestatic

Definition at line 40 of file aigTsim.c.

{ 
    if ( Value == AIG_XVS0 )
        return AIG_XVS1;
    if ( Value == AIG_XVS1 )
        return AIG_XVS0;
    assert( Value == AIG_XVSX );       
    return AIG_XVSX;
}

static void Aig_XsimPrint ( FILE *  pFile, int  Value  )

inlinestatic

Definition at line 82 of file aigTsim.c.

{ 
    if ( Value == AIG_XVS0 )
    {
        fprintf( pFile, "0" );
        return;
    }
    if ( Value == AIG_XVS1 )
    {
        fprintf( pFile, "1" );
        return;
    }
    assert( Value == AIG_XVSX );       
    fprintf( pFile, "x" );
}

static int Aig_XsimRand2 ( )

inlinestatic

Definition at line 58 of file aigTsim.c.

{
    return (Aig_ManRandom(0) & 1) ? AIG_XVS1 : AIG_XVS0;
}

static int Aig_XsimRand3 ( )

inlinestatic

Definition at line 62 of file aigTsim.c.

{
    int RetValue;
    do { 
        RetValue = Aig_ManRandom(0) & 3; 
    } while ( RetValue == 0 );
    return RetValue;
}