amapRule.c File Reference

#include "amapInt.h"
#include "bool/kit/kit.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START int	Amap_LibDeriveGatePerm (Amap_Lib_t *pLib, Amap_Gat_t *pGate, Kit_DsdNtk_t *pNtk, Amap_Nod_t *pNod, char *pArray)
	DECLARATIONS ///. More...
Vec_Int_t *	Amap_CreateRulesPrime (Amap_Lib_t *p, Vec_Int_t *vNods0, Vec_Int_t *vNods1, Vec_Int_t *vNods2)
	FUNCTION DEFINITIONS ///. More...
void	Amap_CreateRulesTwo (Amap_Lib_t *p, Vec_Int_t *vNods, Vec_Int_t *vNods0, Vec_Int_t *vNods1, int fXor)
int	Amap_CreateCheckAllZero (Vec_Ptr_t *vVecNods)
Vec_Int_t *	Amap_CreateRulesVector_rec (Amap_Lib_t *p, Vec_Ptr_t *vVecNods, int fXor)
Vec_Int_t *	Amap_CreateRulesFromDsd_rec (Amap_Lib_t *pLib, Kit_DsdNtk_t *p, int iLit)
Vec_Int_t *	Amap_CreateRulesFromDsd (Amap_Lib_t *pLib, Kit_DsdNtk_t *p)
int	Amap_CreateCheckEqual_rec (Kit_DsdNtk_t *p, int iLit0, int iLit1)
void	Amap_CreateCheckAsym_rec (Kit_DsdNtk_t *p, int iLit, Vec_Int_t **pvSyms)
void	Amap_CreateCheckAsym (Kit_DsdNtk_t *p, Vec_Int_t **pvSyms)
void	Amap_CreateRulesForGate (Amap_Lib_t *pLib, Amap_Gat_t *pGate)
void	Amap_LibCreateRules (Amap_Lib_t *pLib, int fVeryVerbose)

Function Documentation

int Amap_CreateCheckAllZero

(

Vec_Ptr_t *

vVecNods

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 102 of file amapRule.c.

{
    Vec_Int_t * vNods;
    int i;
    Vec_PtrForEachEntryReverse( Vec_Int_t *, vVecNods, vNods, i )
        if ( Vec_IntSize(vNods) != 1 || Vec_IntEntry(vNods,0) != 0 )
            return 0;
    return 1;
}

void Amap_CreateCheckAsym	(	Kit_DsdNtk_t *	p,
		Vec_Int_t **	pvSyms
	)

Definition at line 314 of file amapRule.c.

{
    Amap_CreateCheckAsym_rec( p, Abc_LitRegular(p->Root), pvSyms );
}

void Amap_CreateCheckAsym_rec	(	Kit_DsdNtk_t *	p,
		int	iLit,
		Vec_Int_t **	pvSyms
	)

Definition at line 288 of file amapRule.c.

{
    Kit_DsdObj_t * pObj; 
    int i, k, iFanin;
    assert( !Abc_LitIsCompl(iLit) );
    pObj = Kit_DsdNtkObj( p, Abc_Lit2Var(iLit) );
    if ( pObj == NULL )
        return;
    Kit_DsdObjForEachFanin( p, pObj, iFanin, i )
        Amap_CreateCheckAsym_rec( p, Abc_LitRegular(iFanin), pvSyms );
    if ( pObj->Type == KIT_DSD_PRIME )
        return;
    assert( pObj->Type == KIT_DSD_AND || pObj->Type == KIT_DSD_XOR );
    for ( i = 0; i < (int)pObj->nFans; i++ )
    for ( k = i+1; k < (int)pObj->nFans; k++ )
    {
        if ( Abc_LitIsCompl(pObj->pFans[i]) != Abc_LitIsCompl(pObj->pFans[k]) && 
             Kit_DsdNtkObj(p, Abc_Lit2Var(pObj->pFans[i])) == NULL && 
             Kit_DsdNtkObj(p, Abc_Lit2Var(pObj->pFans[k])) == NULL )
        {
            if ( *pvSyms == NULL )
                *pvSyms = Vec_IntAlloc( 16 );
            Vec_IntPush( *pvSyms, (Abc_Lit2Var(pObj->pFans[i]) << 8) | Abc_Lit2Var(pObj->pFans[k]) );
        }
    }
}

int Amap_CreateCheckEqual_rec	(	Kit_DsdNtk_t *	p,
		int	iLit0,
		int	iLit1
	)

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

Synopsis [Returns 1 if DSD network contains asymentry due to complements.]

Description []

SideEffects []

SeeAlso []

Definition at line 260 of file amapRule.c.

{
    Kit_DsdObj_t * pObj0, * pObj1; 
    int i;
    assert( !Abc_LitIsCompl(iLit0) );
    assert( !Abc_LitIsCompl(iLit1) );
    pObj0 = Kit_DsdNtkObj( p, Abc_Lit2Var(iLit0) );
    pObj1 = Kit_DsdNtkObj( p, Abc_Lit2Var(iLit1) );
    if ( pObj0 == NULL && pObj1 == NULL )
        return 1;
    if ( pObj0 == NULL || pObj1 == NULL )
        return 0;
    if ( pObj0->Type != pObj1->Type )
        return 0;
    if ( pObj0->nFans != pObj1->nFans )
        return 0;
    if ( pObj0->Type == KIT_DSD_PRIME )
        return 0;
    assert( pObj0->Type == KIT_DSD_AND || pObj0->Type == KIT_DSD_XOR );
    for ( i = 0; i < (int)pObj0->nFans; i++ )
    {
        if ( Abc_LitIsCompl(pObj0->pFans[i]) != Abc_LitIsCompl(pObj1->pFans[i]) )
            return 0;
        if ( !Amap_CreateCheckEqual_rec( p, Abc_LitRegular(pObj0->pFans[i]), Abc_LitRegular(pObj1->pFans[i]) ) )
            return 0;
    }
    return 1;
}

void Amap_CreateRulesForGate	(	Amap_Lib_t *	pLib,
		Amap_Gat_t *	pGate
	)

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

Synopsis [Creates rules for the given gate]

Description []

SideEffects []

SeeAlso []

Definition at line 330 of file amapRule.c.

{ 
    Kit_DsdNtk_t * pNtk, * pTemp;
    Vec_Int_t * vSyms = NULL;
    Vec_Int_t * vNods;
    Amap_Nod_t * pNod;
    Amap_Set_t * pSet, * pSet2;
    int iNod, i, k, Entry;
//    if ( pGate->nPins > 4 )
//        return;
    pNtk = Kit_DsdDecomposeMux( pGate->pFunc, pGate->nPins, 2 );
    if ( pGate->nPins == 2 && (pGate->pFunc[0] == 0x66666666 || pGate->pFunc[0] == ~0x66666666) )
         pLib->fHasXor = 1;
    if ( Kit_DsdNonDsdSizeMax(pNtk) == 3 )
        pLib->fHasMux = pGate->fMux = 1;
    pNtk = Kit_DsdExpand( pTemp = pNtk );
    Kit_DsdNtkFree( pTemp );
    Kit_DsdVerify( pNtk, pGate->pFunc, pGate->nPins ); 
    // check symmetries
    Amap_CreateCheckAsym( pNtk, &vSyms );
//    if ( vSyms )
//        Kit_DsdPrint( stdout, pNtk ), printf( "\n" );

if ( pLib->fVerbose )
//if ( pGate->fMux )
{
printf( "\nProcessing library gate %4d: %10s ", pGate->Id, pGate->pName );
Kit_DsdPrint( stdout, pNtk );
}
    vNods = Amap_CreateRulesFromDsd( pLib, pNtk );
    if ( vNods )
    {
        Vec_IntForEachEntry( vNods, iNod, i )
        {
            assert( iNod > 1 );
            pNod = Amap_LibNod( pLib, Abc_Lit2Var(iNod) );
//            assert( pNod->Type == AMAP_OBJ_MUX || pNod->nSuppSize == pGate->nPins );
            pSet = (Amap_Set_t *)Aig_MmFlexEntryFetch( pLib->pMemSet, sizeof(Amap_Set_t) );
            memset( pSet, 0, sizeof(Amap_Set_t) );
            pSet->iGate = pGate->Id;
            pSet->fInv  = Abc_LitIsCompl(iNod);
            pSet->nIns  = pGate->nPins;
            if ( Amap_LibDeriveGatePerm( pLib, pGate, pNtk, pNod, pSet->Ins ) == 0 )
            {
if ( pLib->fVerbose )
{
                printf( "Cound not prepare gate \"%s\": ", pGate->pName );
                Kit_DsdPrint( stdout, pNtk );
}
                continue;
            }
            pSet->pNext = pNod->pSets;
            pNod->pSets = pSet;
            pLib->nSets++;
            if ( vSyms == NULL )
                continue;
//            continue;
            // add sets equivalent due to symmetry
            Vec_IntForEachEntry( vSyms, Entry, k )
            {
                int iThis = Entry & 0xff;
                int iThat = Entry >> 8;
//                printf( "%d %d\n", iThis, iThat );
                // create new set
                pSet2 = (Amap_Set_t *)Aig_MmFlexEntryFetch( pLib->pMemSet, sizeof(Amap_Set_t) );
                memset( pSet2, 0, sizeof(Amap_Set_t) );
                pSet2->iGate = pGate->Id;
                pSet2->fInv  = Abc_LitIsCompl(iNod);
                pSet2->nIns  = pGate->nPins;
                memcpy( pSet2->Ins, pSet->Ins, pGate->nPins );
                // update inputs
                pSet2->Ins[iThis] = Abc_Var2Lit( Abc_Lit2Var(pSet->Ins[iThat]), Abc_LitIsCompl(pSet->Ins[iThis]) );
                pSet2->Ins[iThat] = Abc_Var2Lit( Abc_Lit2Var(pSet->Ins[iThis]), Abc_LitIsCompl(pSet->Ins[iThat]) );
                // add set to collection
                pSet2->pNext = pNod->pSets;
                pNod->pSets  = pSet2;
                pLib->nSets++;
            }
        }
        Vec_IntFree( vNods );
    }
    Kit_DsdNtkFree( pNtk );
    Vec_IntFreeP( &vSyms );
}

Vec_Int_t* Amap_CreateRulesFromDsd	(	Amap_Lib_t *	pLib,
		Kit_DsdNtk_t *	p
	)

Definition at line 233 of file amapRule.c.

{
    Vec_Int_t * vNods;
    int iNod, i;
    assert( p->nVars >= 2 );
    vNods = Amap_CreateRulesFromDsd_rec( pLib, p, Abc_LitRegular(p->Root) );
    if ( vNods == NULL )
        return NULL;
    if ( Abc_LitIsCompl(p->Root) )
    {
        Vec_IntForEachEntry( vNods, iNod, i )
            Vec_IntWriteEntry( vNods, i, Abc_LitNot(iNod) );
    }
    return vNods;
}

Vec_Int_t* Amap_CreateRulesFromDsd_rec	(	Amap_Lib_t *	pLib,
		Kit_DsdNtk_t *	p,
		int	iLit
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 191 of file amapRule.c.

{
    Vec_Int_t * vRes;
    Vec_Ptr_t * vVecNods;
    Vec_Int_t * vNodsFanin;
    Kit_DsdObj_t * pObj;
    unsigned i;
    int iFanin, iNod, k;
    assert( !Abc_LitIsCompl(iLit) );
    pObj = Kit_DsdNtkObj( p, Abc_Lit2Var(iLit) );
    if ( pObj == NULL )
        return Vec_IntStartNatural( 1 );
    // solve for the inputs
    vVecNods = Vec_PtrAlloc( pObj->nFans );
    Kit_DsdObjForEachFanin( p, pObj, iFanin, i )
    {
        vNodsFanin = Amap_CreateRulesFromDsd_rec( pLib, p, Abc_LitRegular(iFanin) );
        if ( Abc_LitIsCompl(iFanin) )
        {
            Vec_IntForEachEntry( vNodsFanin, iNod, k )
                if ( iNod > 0 )
                    Vec_IntWriteEntry( vNodsFanin, k, Abc_LitNot(iNod) );
        }
        Vec_PtrPush( vVecNods, vNodsFanin );
    }
    if ( pObj->Type == KIT_DSD_AND )
        vRes = Amap_CreateRulesVector_rec( pLib, vVecNods, 0 );
    else if ( pObj->Type == KIT_DSD_XOR )
        vRes = Amap_CreateRulesVector_rec( pLib, vVecNods, 1 );
    else if ( pObj->Type == KIT_DSD_PRIME )
    {
        assert( pObj->nFans == 3 );
        assert( Kit_DsdObjTruth(pObj)[0] == 0xCACACACA );
        vRes = Amap_CreateRulesPrime( pLib, (Vec_Int_t *)Vec_PtrEntry(vVecNods, 0),
            (Vec_Int_t *)Vec_PtrEntry(vVecNods, 1), (Vec_Int_t *)Vec_PtrEntry(vVecNods, 2) );
    }
    else assert( 0 );
    Vec_PtrForEachEntry( Vec_Int_t *, vVecNods, vNodsFanin, k )
        Vec_IntFree( vNodsFanin );
    Vec_PtrFree( vVecNods );
    return vRes;
}

Vec_Int_t* Amap_CreateRulesPrime	(	Amap_Lib_t *	p,
		Vec_Int_t *	vNods0,
		Vec_Int_t *	vNods1,
		Vec_Int_t *	vNods2
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Checks if the three-argument rule exist.]

Description []

SideEffects []

SeeAlso []

Definition at line 48 of file amapRule.c.

{
    Vec_Int_t * vRes;
    int i, k, j, iNod, iNod0, iNod1, iNod2;
    if ( p->vRules3 == NULL )
        p->vRules3 = Vec_IntAlloc( 100 );
    vRes = Vec_IntAlloc( 10 );
    Vec_IntForEachEntry( vNods0, iNod0, i )
    Vec_IntForEachEntry( vNods1, iNod1, k )
    Vec_IntForEachEntry( vNods2, iNod2, j )
    {
        iNod = Amap_LibFindMux( p, iNod0, iNod1, iNod2 );
        if ( iNod == -1 )
            iNod = Amap_LibCreateMux( p, iNod0, iNod1, iNod2 );
        Vec_IntPush( vRes, Abc_Var2Lit(iNod, 0) );
    }
    return vRes;
}

void Amap_CreateRulesTwo	(	Amap_Lib_t *	p,
		Vec_Int_t *	vNods,
		Vec_Int_t *	vNods0,
		Vec_Int_t *	vNods1,
		int	fXor
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 78 of file amapRule.c.

{
    int i, k, iNod, iNod0, iNod1;
    Vec_IntForEachEntry( vNods0, iNod0, i )
    Vec_IntForEachEntry( vNods1, iNod1, k )
    {
        iNod = Amap_LibFindNode( p, iNod0, iNod1, fXor );
        if ( iNod == -1 )
            iNod = Amap_LibCreateNode( p, iNod0, iNod1, fXor );
        Vec_IntPushUnique( vNods, Abc_Var2Lit(iNod, 0) );
    }
}

Vec_Int_t* Amap_CreateRulesVector_rec	(	Amap_Lib_t *	p,
		Vec_Ptr_t *	vVecNods,
		int	fXor
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file amapRule.c.

{
    Vec_Ptr_t * vVecNods0, * vVecNods1;
    Vec_Int_t * vRes, * vNods, * vNods0, * vNods1;
    int i, k;
    if ( Vec_PtrSize(vVecNods) == 1 )
        return Vec_IntDup( (Vec_Int_t *)Vec_PtrEntry(vVecNods, 0) );
    vRes = Vec_IntAlloc( 10 );
    vVecNods0 = Vec_PtrAlloc( Vec_PtrSize(vVecNods) );
    vVecNods1 = Vec_PtrAlloc( Vec_PtrSize(vVecNods) );
    if ( Amap_CreateCheckAllZero(vVecNods) )
    {
        for ( i = Vec_PtrSize(vVecNods)-1; i > 0; i-- )
        {
            Vec_PtrClear( vVecNods0 );
            Vec_PtrClear( vVecNods1 );
            Vec_PtrForEachEntryStop( Vec_Int_t *, vVecNods, vNods, k, i )
                Vec_PtrPush( vVecNods0, vNods );
            Vec_PtrForEachEntryStart( Vec_Int_t *, vVecNods, vNods, k, i )
                Vec_PtrPush( vVecNods1, vNods );
            vNods0 = Amap_CreateRulesVector_rec( p, vVecNods0, fXor );
            vNods1 = Amap_CreateRulesVector_rec( p, vVecNods1, fXor );
            Amap_CreateRulesTwo( p, vRes, vNods0, vNods1, fXor );
            Vec_IntFree( vNods0 );
            Vec_IntFree( vNods1 );
        }
    }
    else
    {
        int Limit = (1 << Vec_PtrSize(vVecNods))-2;
        for ( i = 1; i < Limit; i++ )
        {
            Vec_PtrClear( vVecNods0 );
            Vec_PtrClear( vVecNods1 );
            Vec_PtrForEachEntryReverse( Vec_Int_t *, vVecNods, vNods, k )
            {
                if ( i & (1 << k) )
                    Vec_PtrPush( vVecNods1, vNods );
                else
                    Vec_PtrPush( vVecNods0, vNods );
            }
            assert( Vec_PtrSize(vVecNods0) > 0 );
            assert( Vec_PtrSize(vVecNods1) > 0 );
            assert( Vec_PtrSize(vVecNods0) < Vec_PtrSize(vVecNods) );
            assert( Vec_PtrSize(vVecNods1) < Vec_PtrSize(vVecNods) );
            vNods0 = Amap_CreateRulesVector_rec( p, vVecNods0, fXor );
            vNods1 = Amap_CreateRulesVector_rec( p, vVecNods1, fXor );
            Amap_CreateRulesTwo( p, vRes, vNods0, vNods1, fXor );
            Vec_IntFree( vNods0 );
            Vec_IntFree( vNods1 );
        }
    }
    Vec_PtrFree( vVecNods0 );
    Vec_PtrFree( vVecNods1 );
    return vRes;
}

void Amap_LibCreateRules	(	Amap_Lib_t *	pLib,
		int	fVeryVerbose
	)

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

Synopsis [Creates rules for the given gate]

Description []

SideEffects []

SeeAlso []

Definition at line 426 of file amapRule.c.

{
    Amap_Gat_t * pGate;
    int i, nGates = 0;
//    abctime clk = Abc_Clock();
    pLib->fVerbose = fVeryVerbose;
    pLib->vRules   = Vec_PtrAlloc( 100 );
    pLib->vRulesX  = Vec_PtrAlloc( 100 );
    pLib->vRules3  = Vec_IntAlloc( 100 );
    Amap_LibCreateVar( pLib );
    Vec_PtrForEachEntry( Amap_Gat_t *, pLib->vSelect, pGate, i )
    {
        if ( pGate->nPins < 2 )
            continue;
        if ( pGate->pFunc == NULL )
        {
            printf( "Amap_LibCreateRules(): Skipping gate %s (%s).\n", pGate->pName, pGate->pForm );
            continue;
        }
        Amap_CreateRulesForGate( pLib, pGate );
        nGates++;
    }
    assert( Vec_PtrSize(pLib->vRules)  == 2*pLib->nNodes );
    assert( Vec_PtrSize(pLib->vRulesX) == 2*pLib->nNodes );
    pLib->pRules  = Amap_LibLookupTableAlloc( pLib->vRules, 0 );
    pLib->pRulesX = Amap_LibLookupTableAlloc( pLib->vRulesX, 0 );
    Vec_VecFree( (Vec_Vec_t *)pLib->vRules );  pLib->vRules  = NULL;
    Vec_VecFree( (Vec_Vec_t *)pLib->vRulesX ); pLib->vRulesX = NULL;
}

ABC_NAMESPACE_IMPL_START int Amap_LibDeriveGatePerm	(	Amap_Lib_t *	pLib,
		Amap_Gat_t *	pGate,
		Kit_DsdNtk_t *	pNtk,
		Amap_Nod_t *	pNod,
		char *	pArray
	)

DECLARATIONS ///.

CFile****************************************************************

FileName [amapRule.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Technology mapper for standard cells.]

Synopsis [Matching rules.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

amapRule.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

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

Synopsis [Matches the node with the DSD of a gate.]

Description []

SideEffects []

SeeAlso []

Definition at line 331 of file amapPerm.c.

{
    int fVerbose = 0;
    Vec_Int_t * vPerm;
    int Entry, Entry2, i, k;
//    Kit_DsdPrint( stdout, pNtk );

    vPerm = Amap_LibDeriveGatePerm_rec( pLib, pNtk, Abc_LitRegular(pNtk->Root), pNod );
    if ( vPerm == NULL )
        return 0;
    // check that the permutation is valid
    assert( Vec_IntSize(vPerm) == (int)pNod->nSuppSize );
    Vec_IntForEachEntry( vPerm, Entry, i )
        Vec_IntForEachEntryStart( vPerm, Entry2, k, i+1 )
            if ( Abc_Lit2Var(Entry) == Abc_Lit2Var(Entry2) )
            {
                Vec_IntFree( vPerm );
                return 0;
            }

    // reverse the permutation
    Vec_IntForEachEntry( vPerm, Entry, i )
    {
        assert( Entry < 2 * (int)pNod->nSuppSize );
        pArray[Abc_Lit2Var(Entry)] = Abc_Var2Lit( i, Abc_LitIsCompl(Entry) );
//        pArray[i] = Entry;
//printf( "%d=%d%c ", Abc_Lit2Var(Entry), i, Abc_LitIsCompl(Entry)?'-':'+' );
    }
//printf( "\n" );
//    if ( Kit_DsdNonDsdSizeMax(pNtk) < 3 )
//        Amap_LibVerifyPerm( pLib, pGate, pNtk, pNod, Vec_IntArray(vPerm) );
    Vec_IntFree( vPerm );
    // print the result
    if ( fVerbose )
    {
    printf( "node %4d : ", pNod->Id );
    for ( i = 0; i < (int)pNod->nSuppSize; i++ )
        printf( "%d=%d%c ", i, Abc_Lit2Var(pArray[i]), Abc_LitIsCompl(pArray[i])?'-':'+' );
    printf( "\n" );
    }
    return 1;
}