wlcGraft.c

/**CFile****************************************************************

  FileName    [wlcGraft.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Verilog parser.]

  Synopsis    [Parses several flavors of word-level Verilog.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - August 22, 2014.]

  Revision    [$Id: wlcGraft.c,v 1.00 2014/09/12 00:00:00 alanmi Exp $]

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

#include "wlc.h"
#include "sat/bsat/satStore.h"

ABC_NAMESPACE_IMPL_START

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

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

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

  Synopsis    [Internal simulation APIs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline word * Wlc_ObjSim( Gia_Man_t * p, int iObj )
{
    return Vec_WrdEntryP( p->vSims, p->nSimWords * iObj );
}
static inline void Wlc_ObjSimPi( Gia_Man_t * p, int iObj )
{
    int w;
    word * pSim = Wlc_ObjSim( p, iObj );
    for ( w = 0; w < p->nSimWords; w++ )
        pSim[w] = Gia_ManRandomW( 0 );
    pSim[0] <<= 1;
}
static inline void Wlc_ObjSimRo( Gia_Man_t * p, int iObj )
{
    int w;
    word * pSimRo = Wlc_ObjSim( p, iObj );
    word * pSimRi = Wlc_ObjSim( p, Gia_ObjRoToRiId(p, iObj) );
    for ( w = 0; w < p->nSimWords; w++ )
        pSimRo[w] = pSimRi[w];
}
static inline void Wlc_ObjSimCo( Gia_Man_t * p, int iObj )
{
    int w;
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    word * pSimCo  = Wlc_ObjSim( p, iObj );
    word * pSimDri = Wlc_ObjSim( p, Gia_ObjFaninId0(pObj, iObj) );
    if ( Gia_ObjFaninC0(pObj) )
        for ( w = 0; w < p->nSimWords; w++ )
            pSimCo[w] = ~pSimDri[w];
    else
        for ( w = 0; w < p->nSimWords; w++ )
            pSimCo[w] =  pSimDri[w];
}
static inline void Wlc_ObjSimAnd( Gia_Man_t * p, int iObj )
{
    int w;
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    word * pSim  = Wlc_ObjSim( p, iObj );
    word * pSim0 = Wlc_ObjSim( p, Gia_ObjFaninId0(pObj, iObj) );
    word * pSim1 = Wlc_ObjSim( p, Gia_ObjFaninId1(pObj, iObj) );
    if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
        for ( w = 0; w < p->nSimWords; w++ )
            pSim[w] = ~pSim0[w] & ~pSim1[w];
    else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
        for ( w = 0; w < p->nSimWords; w++ )
            pSim[w] = ~pSim0[w] & pSim1[w];
    else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
        for ( w = 0; w < p->nSimWords; w++ )
            pSim[w] = pSim0[w] & ~pSim1[w];
    else
        for ( w = 0; w < p->nSimWords; w++ )
            pSim[w] = pSim0[w] & pSim1[w];
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Wlc_NtkCollectObjs_rec( Wlc_Ntk_t * p, Wlc_Obj_t * pObj, Vec_Int_t * vObjs )
{
    int i, iFanin, Count = 0;
    if ( Wlc_ObjIsCi(pObj) )
        return 0;
    if ( pObj->Mark )
        return 0;
    pObj->Mark = 1;
    Wlc_ObjForEachFanin( pObj, iFanin, i )
        Count += Wlc_NtkCollectObjs_rec( p, Wlc_NtkObj(p, iFanin), vObjs );
    Vec_IntPush( vObjs, Wlc_ObjId(p, pObj) );
    return Count + (int)(pObj->Type == WLC_OBJ_ARI_MULTI);
}
Vec_Int_t * Wlc_NtkCollectObjs( Wlc_Ntk_t * p, int fEven, int * pCount )
{
    Vec_Int_t * vObjs = Vec_IntAlloc( 100 );
    Wlc_Obj_t * pObj; 
    int i, Count = 0;
    Wlc_NtkCleanMarks( p );
    Wlc_NtkForEachCo( p, pObj, i )
        if ( (i & 1) == fEven )
            Count += Wlc_NtkCollectObjs_rec( p, pObj, vObjs );
    Wlc_NtkCleanMarks( p );
    if ( pCount )
        *pCount = Count;
    return vObjs;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Wlc_NtkSaveOneNode( Wlc_Ntk_t * p, Wlc_Obj_t * pWlcObj, Gia_Man_t * pGia, Vec_Mem_t * vTtMem )
{
    int k, Entry;
    int nWords = Vec_MemEntrySize(vTtMem);
    int nBits = Wlc_ObjRange(pWlcObj);
    int iFirst = Vec_IntEntry( &p->vCopies, Wlc_ObjId(p, pWlcObj) );
    for ( k = 0; k < nBits; k++ )
    {
        int iLit = Vec_IntEntry( &p->vBits, iFirst + k );
        word * pInfoObj = Wlc_ObjSim( pGia, Abc_Lit2Var(iLit) );
        int fCompl = pInfoObj[0] & 1;
        if ( fCompl ) Abc_TtNot( pInfoObj, nWords );
        Entry = Vec_MemHashInsert( vTtMem, pInfoObj );
        if ( fCompl ) Abc_TtNot( pInfoObj, nWords );
        printf( "%2d(%d) ", Entry, fCompl ^ Abc_LitIsCompl(iLit) );
        Extra_PrintHex( stdout, (unsigned*)pInfoObj, 8 );
        printf( "\n" );
    }
    printf( "\n" );
}
void Wlc_NtkFindOneNode( Wlc_Ntk_t * p, Wlc_Obj_t * pWlcObj, Gia_Man_t * pGia, Vec_Mem_t * vTtMem )
{
    int k, Entry;
    int nWords = Vec_MemEntrySize(vTtMem);
    int nBits = Wlc_ObjRange(pWlcObj);
    int iFirst = Vec_IntEntry( &p->vCopies, Wlc_ObjId(p, pWlcObj) );
    for ( k = 0; k < nBits; k++ )
    {
        int iLit = Vec_IntEntry( &p->vBits, iFirst + k );
        word * pInfoObj = Wlc_ObjSim( pGia, Abc_Lit2Var(iLit) );
        int fCompl = pInfoObj[0] & 1;
        if ( fCompl ) Abc_TtNot( pInfoObj, nWords );
        Entry = *Vec_MemHashLookup( vTtMem, pInfoObj );
        if ( Entry > 0 )
            printf( "Obj %4d.  Range = %2d.  Bit %2d.  Entry %d(%d).  %s\n", Wlc_ObjId(p, pWlcObj), Wlc_ObjRange(pWlcObj), k, Entry, fCompl ^ Abc_LitIsCompl(iLit), Wlc_ObjName(p, Wlc_ObjId(p, pWlcObj)) );
        if ( fCompl ) Abc_TtNot( pInfoObj, nWords );
        //printf( "%2d ", Entry );
        //Extra_PrintHex( stdout, (unsigned*)pInfoObj, 8 );
        //printf( "\n" );
    }
    //printf( "\n" );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Wlc_Ntk_t * Wlc_NtkGraftMulti( Wlc_Ntk_t * p, int fVerbose )
{
    int nWords = 4;
    int i, nMultiLHS, nMultiRHS;
    word * pInfoObj;
    Wlc_Ntk_t * pNew = NULL;
    Wlc_Obj_t * pWlcObj;
    Gia_Obj_t * pObj;
    Vec_Int_t * vObjsLHS = Wlc_NtkCollectObjs( p, 0, &nMultiLHS );
    Vec_Int_t * vObjsRHS = Wlc_NtkCollectObjs( p, 1, &nMultiRHS );
    Gia_Man_t * pGia = Wlc_NtkBitBlast( p, NULL ); //, -1, 0, 0, 0, 0, 1, 0, 0 ); // <= no cleanup
    Vec_Mem_t * vTtMem = Vec_MemAlloc( nWords, 10 );
    Vec_MemHashAlloc( vTtMem, 10000 );

    // check if there are multipliers
    if ( nMultiLHS == 0 && nMultiRHS == 0 )
    {
        printf( "No multipliers are present.\n" );
        return NULL;
    }
    // compare multipliers
    if ( nMultiLHS > 0 && nMultiRHS > 0 )
    {
        printf( "Multipliers are present in both sides of the miter.\n" );
        return NULL;
    }
    // swap if wrong side
    if ( nMultiRHS > 0 )
    {
        ABC_SWAP( Vec_Int_t *, vObjsLHS, vObjsRHS );
        ABC_SWAP( int, nMultiLHS, nMultiRHS );
    }
    assert( nMultiLHS > 0 );
    assert( nMultiRHS == 0 );

    // allocate simulation info for one timeframe
    Vec_WrdFreeP( &pGia->vSims );
    pGia->vSims = Vec_WrdStart( Gia_ManObjNum(pGia) * nWords );
    pGia->nSimWords = nWords;
    // perform simulation
    Gia_ManRandomW( 1 );
    Gia_ManForEachObj1( pGia, pObj, i )
    {
        if ( Gia_ObjIsAnd(pObj) )
            Wlc_ObjSimAnd( pGia, i );
        else if ( Gia_ObjIsCo(pObj) )
            Wlc_ObjSimCo( pGia, i );
        else if ( Gia_ObjIsCi(pObj) )
            Wlc_ObjSimPi( pGia, i );
        else assert( 0 );
    }

    // hash constant 0
    pInfoObj = Wlc_ObjSim( pGia, 0 );
    Vec_MemHashInsert( vTtMem, pInfoObj );

    // hash sim info on the multiplier boundary
    Wlc_NtkForEachObjVec( vObjsLHS, p, pWlcObj, i )
        if ( Wlc_ObjType(pWlcObj) == WLC_OBJ_ARI_MULTI )
        {
            Wlc_NtkSaveOneNode( p, Wlc_ObjFanin0(p, pWlcObj), pGia, vTtMem );
            Wlc_NtkSaveOneNode( p, Wlc_ObjFanin1(p, pWlcObj), pGia, vTtMem );
            Wlc_NtkSaveOneNode( p, pWlcObj, pGia, vTtMem );
        }

    // check if there are similar signals in LHS
    Wlc_NtkForEachObjVec( vObjsRHS, p, pWlcObj, i )
        Wlc_NtkFindOneNode( p, pWlcObj, pGia, vTtMem );

    // perform grafting


    Vec_MemHashFree( vTtMem );
    Vec_MemFreeP( &vTtMem );

    // cleanup
    Vec_WrdFreeP( &pGia->vSims );
    pGia->nSimWords = 0;

    Vec_IntFree( vObjsLHS );
    Vec_IntFree( vObjsRHS );
    Gia_ManStop( pGia );
    return pNew;
}





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

  Synopsis    [Generate simulation vectors.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sbc_Mult( word a, word b, word r[2] )
{
    word Msk = 0xFFFFFFFF;
    word pL  = (a & Msk) * (b & Msk);
    word pM1 = (a & Msk) * (b >> 32);
    word pM2 = (a >> 32) * (b & Msk);
    word pH  = (a >> 32) * (b >> 32);
    word Car = (pM1 & Msk) + (pM2 & Msk) + (pL >> 32);
    r[0] = a * b;
    r[1] = pH + (pM1 >> 32) + (pM2 >> 32) + (Car >> 32);
}
void Sbc_SimMult( word A[64], word B[64], word R[128], int nIns )
{
    word a, b, r[2], Mask = Abc_Tt6Mask(nIns); int i, k;
    for ( i = 0; i < 64; i++ )
        A[i] = B[i] = R[i] = R[i+64] = 0;
    Gia_ManRandom(1);
    for ( i = 0; i < 64; i++ )
    {
        a = i ? (Mask & Gia_ManRandomW(0)) : 0;
        b = i ? (Mask & Gia_ManRandomW(0)) : 0;        
        Sbc_Mult( a, b, r );
        for ( k = 0; k < 64; k++ )
        {
            if ( (a    >> k) & 1 )  A[k]    |= ((word)1 << i);
            if ( (b    >> k) & 1 )  B[k]    |= ((word)1 << i);
            if ( (r[0] >> k) & 1 )  R[k]    |= ((word)1 << i);
            if ( (r[1] >> k) & 1 )  R[k+64] |= ((word)1 << i);
        }
    }
//    for ( i = 0; i < 128; i++ )
//        for ( k = 0; k < 64; k++, printf( "\n" ) )
//            printf( "%d", (R[i] >> k) & 1 );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Sbc_ManDetectMult( Gia_Man_t * p, Vec_Int_t * vIns )
{
    int nWords = 1;
    Vec_Int_t * vGia2Out = Vec_IntStartFull( Gia_ManObjNum(p) );
    Gia_Obj_t * pObj; int i, Entry, nIns = Vec_IntSize(vIns)/2;
    word A[64], B[64], R[128], * pInfoObj; word Temp;

    // create hash table
    Vec_Mem_t * vTtMem = Vec_MemAlloc( nWords, 10 );
    Vec_MemHashAlloc( vTtMem, 1000 );
    Sbc_SimMult( A, B, R, nIns );
    for ( i = 0; i < 2*nIns; i++ )
    {
        Vec_MemHashInsert( vTtMem, R+i );
        //printf( "Out %2d : ", i );
        //Extra_PrintHex( stdout, (unsigned *)(R+i), 6 ); printf( "\n" );
    }
    assert( Vec_MemEntryNum(vTtMem) == 2*nIns );

    // alloc simulation info
    Vec_WrdFreeP( &p->vSims );
    p->vSims = Vec_WrdStart( Gia_ManObjNum(p) * nWords );
    p->nSimWords = nWords;

    // mark inputs
    Gia_ManIncrementTravId( p );
    Gia_ObjSetTravIdCurrentId( p, 0 );
    Gia_ManForEachCi( p, pObj, i )
    {
        Gia_ObjSetTravIdCurrent( p, pObj );
        //Wlc_ObjSimPi( p, Gia_ObjId(p, pObj) );
    }

    // assign inputs
    assert( Vec_IntSize(vIns) % 2 == 0 );
    Gia_ManForEachObjVec( vIns, p, pObj, i )
    {
        Gia_ObjSetTravIdCurrent( p, pObj );
        pInfoObj = Wlc_ObjSim( p, Gia_ObjId(p, pObj) );
        *pInfoObj = i < nIns ? A[i] : B[i - nIns];
    }

    // perform simulation
    Gia_ManForEachObj1( p, pObj, i )
    {
        if ( Gia_ObjIsTravIdCurrent(p, pObj) )
            continue;

        if ( Gia_ObjIsAnd(pObj) )
            Wlc_ObjSimAnd( p, i );
        else if ( Gia_ObjIsCo(pObj) )
            Wlc_ObjSimCo( p, i );
        else assert( 0 );

        // mark direct polarity
        pInfoObj = Wlc_ObjSim( p, i );
        Entry = *Vec_MemHashLookup( vTtMem, pInfoObj );
        if ( Entry >= 0 )
        {
            Vec_IntWriteEntry( vGia2Out, i, Abc_Var2Lit(Entry, 0) );
            continue;
        }

        // mark negated polarity
        Temp = *pInfoObj;
        Abc_TtNot( pInfoObj, nWords );
        Entry = *Vec_MemHashLookup( vTtMem, pInfoObj );
        Abc_TtNot( pInfoObj, nWords );
        assert( Temp == *pInfoObj );
        if ( Entry >= 0 )
        {
            Vec_IntWriteEntry( vGia2Out, i, Abc_Var2Lit(Entry, 1) );
            continue;
        }
    }

    Gia_ManForEachCo( p, pObj, i )
    {
        pInfoObj = Wlc_ObjSim( p, Gia_ObjId(p, pObj) );
        //printf( "Out %2d : Driver = %5d(%d)", i, Gia_ObjFaninId0p(p, pObj), Gia_ObjFaninC0(pObj) );
        //Extra_PrintHex( stdout, (unsigned *)pInfoObj, 6 ); printf( "\n" );
    }

    // cleanup
    Vec_MemHashFree( vTtMem );
    Vec_MemFreeP( &vTtMem );
    //Vec_WrdFreeP( &p->vSims );
    //p->nSimWords = 0;
    return vGia2Out;
}
Vec_Int_t * Sbc_ManWlcNodes2( Wlc_Ntk_t * pNtk, Gia_Man_t * p, Vec_Int_t * vGiaLits )
{
    Wlc_Obj_t * pObj;  int i, k, iGiaLit, iFirst, nBits;
    Vec_Int_t * vRes = Vec_IntAlloc( 100 );
    Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) );
    Vec_IntForEachEntry( vGiaLits, iGiaLit, i )
        if ( iGiaLit != -1 )
            Vec_IntWriteEntry( vMap, Abc_Lit2Var(iGiaLit), Abc_Var2Lit(i, Abc_LitIsCompl(iGiaLit)) );
    Wlc_NtkForEachObj( pNtk, pObj, i )
    {
        iFirst = Vec_IntEntry( &pNtk->vCopies, i );
        nBits  = Wlc_ObjRange(pObj);
        for ( k = 0; k < nBits; k++ )
        {
            int iLitGia = Vec_IntEntry( &pNtk->vBits, iFirst + k );
            int iLitOut = Vec_IntEntry( vMap, Abc_Lit2Var(iLitGia) );
            if ( iLitOut == -1 )
                continue;
            Vec_IntWriteEntry( vMap, Abc_Lit2Var(iLitGia), -1 );
            iLitOut = Abc_LitNotCond( iLitOut, Abc_LitIsCompl(iLitGia) );
            printf( "Matched out %d in phase %d with object %d (%s) bit %d (out of %d).\n", Abc_Lit2Var(iLitOut), Abc_LitIsCompl(iLitOut), i, Wlc_ObjName(pNtk, Wlc_ObjId(pNtk, pObj)), k, nBits );
            Vec_IntPushUnique( vRes, i );
        }
    }
    Vec_IntFree( vMap );
    Vec_IntSort( vRes, 0 );
    // consider the last one
    pObj   = Wlc_NtkObj( pNtk, Vec_IntEntryLast(vRes) );
    iFirst = Vec_IntEntry( &pNtk->vCopies, Wlc_ObjId(pNtk, pObj) );
    nBits  = Wlc_ObjRange(pObj);
    printf( "Considering object %d (%s):\n", Wlc_ObjId(pNtk, pObj), Wlc_ObjName(pNtk, Wlc_ObjId(pNtk, pObj)) );
    for ( k = 0; k < nBits; k++ )
    {
        int iLitGia  = Vec_IntEntry( &pNtk->vBits, iFirst + k );
        int iLitOutP = Vec_IntFind( vGiaLits, iLitGia );
        int iLitOutN = Vec_IntFind( vGiaLits, Abc_LitNot(iLitGia) );
        printf( "Matching bit %d with output %d / %d.\n", k, iLitOutP, iLitOutN );
        // print simulation signature
        {
            word * pInfoObj = Wlc_ObjSim( p, Abc_Lit2Var(iLitGia) );
            Extra_PrintHex( stdout, (unsigned *)pInfoObj, 6 ); printf( "\n" );
        }
    }
    return vRes;
}
int Sbc_ManWlcNodes( Wlc_Ntk_t * pNtk, Gia_Man_t * p, Vec_Int_t * vGia2Out, int nOuts )
{
    Wlc_Obj_t * pObj;  
    int i, k, iLitGia, iLitOut, iFirst, nBits, iObjFound = -1;
    Vec_Int_t * vMatched = Vec_IntAlloc( 100 );
    Wlc_NtkForEachObj( pNtk, pObj, i )
    {
        iFirst = Vec_IntEntry( &pNtk->vCopies, i );
        nBits  = Wlc_ObjRange(pObj);
        Vec_IntClear( vMatched );
        for ( k = 0; k < nBits; k++ )
        {
            iLitGia = Vec_IntEntry( &pNtk->vBits, iFirst + k );
            iLitOut = Vec_IntEntry( vGia2Out, Abc_Lit2Var(iLitGia) );
            if ( iLitOut == -1 )
                continue;
            iLitOut = Abc_LitNotCond( iLitOut, Abc_LitIsCompl(iLitGia) );
            printf( "Matched node %5d (%10s) bit %3d (out of %3d) with output %3d(%d).\n", 
                i, Wlc_ObjName(pNtk, Wlc_ObjId(pNtk, pObj)), k, nBits, Abc_Lit2Var(iLitOut), Abc_LitIsCompl(iLitOut) );
            Vec_IntPushOrder( vMatched, Abc_Lit2Var(iLitOut) );
        }
        if ( Vec_IntSize(vMatched) > 0 )
            printf( "\n" );
        if ( Vec_IntSize(vMatched) == nOuts )
        {
            if ( iObjFound == -1 )
                iObjFound = i;
            printf( "Found object %d with all bits matched.\n", i );
            /*
            for ( k = nBits-2; k < nBits; k++ )
            {
                iLitGia = Vec_IntEntry( &pNtk->vBits, iFirst + k );
                {
                    word * pInfoObj = Wlc_ObjSim( p, Abc_Lit2Var(iLitGia) );
                    Extra_PrintHex( stdout, (unsigned *)pInfoObj, 6 ); printf( "\n" );
                }
            }
            */
            break;
        }
    }
    Vec_IntFree( vMatched );
    return iObjFound;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sbc_ManDetectMultTest( Wlc_Ntk_t * pNtk, int fVerbose )
{
    extern Vec_Int_t * Sdb_StoComputeCutsDetect( Gia_Man_t * pGia );
    Gia_Man_t * p = Wlc_NtkBitBlast( pNtk, NULL );//, -1, 0, 0, 0, 0, 1, 0, 0 ); // <= no cleanup
    Vec_Int_t * vIns, * vGia2Out;
    int iObjFound = -1;
//    Gia_Obj_t * pObj; int i;
//    Gia_ManForEachCo( p, pObj, i )
//        printf( "Output %2d - driver %5d (%d)\n", i, Gia_ObjFaninId0p(p, pObj), Gia_ObjFaninC0(pObj) );

    vIns = Sdb_StoComputeCutsDetect( p );
    if ( vIns == NULL || Vec_IntSize(vIns) == 0 || (Vec_IntSize(vIns) % 2) != 0 )
    {
        printf( "Input identification did not work out.\n" );
        return;
    }

    vGia2Out = Sbc_ManDetectMult( p, vIns );

    iObjFound = Sbc_ManWlcNodes( pNtk, p, vGia2Out, Vec_IntSize(vIns) );

    Vec_IntFree( vGia2Out );
    Vec_IntFree( vIns );

    Gia_ManStop( p );
}

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


ABC_NAMESPACE_IMPL_END