amapRule.c

Go to the documentation of this file.

/**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 $]

***********************************************************************/

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

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

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

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Amap_CreateRulesPrime( Amap_Lib_t * p, Vec_Int_t * vNods0, Vec_Int_t * vNods1, Vec_Int_t * vNods2 )
{
    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;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Amap_CreateRulesTwo( Amap_Lib_t * p, Vec_Int_t * vNods, Vec_Int_t * vNods0, Vec_Int_t * vNods1, int fXor )
{
    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) );
    }
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Amap_CreateCheckAllZero( Vec_Ptr_t * vVecNods )
{
    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;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Amap_CreateRulesVector_rec( Amap_Lib_t * p, Vec_Ptr_t * vVecNods, int fXor )
{
    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;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Amap_CreateRulesFromDsd_rec( Amap_Lib_t * pLib, Kit_DsdNtk_t * p, int iLit )
{
    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_CreateRulesFromDsd( Amap_Lib_t * pLib, Kit_DsdNtk_t * p )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Amap_CreateCheckEqual_rec( Kit_DsdNtk_t * p, int iLit0, int iLit1 )
{
    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_CreateCheckAsym_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t ** pvSyms )
{
    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]) );
        }
    }
}
void Amap_CreateCheckAsym( Kit_DsdNtk_t * p, Vec_Int_t ** pvSyms )
{
    Amap_CreateCheckAsym_rec( p, Abc_LitRegular(p->Root), pvSyms );
}

/**Function*************************************************************

  Synopsis    [Creates rules for the given gate]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Amap_CreateRulesForGate( Amap_Lib_t * pLib, Amap_Gat_t * pGate )
{ 
    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 );
}

/**Function*************************************************************

  Synopsis    [Creates rules for the given gate]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Amap_LibCreateRules( Amap_Lib_t * pLib, int fVeryVerbose )
{
    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;
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END