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

  FileName    [giaMuxes.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [Multiplexer profiling algorithm.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: giaMuxes.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

#include "gia.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    [Counts XORs and MUXes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManCountMuxXor( Gia_Man_t * p, int * pnMuxes, int * pnXors )
{
    Gia_Obj_t * pObj, * pFan0, * pFan1; int i;
    *pnMuxes = *pnXors = 0;
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( !Gia_ObjIsMuxType(pObj) )
            continue;
        if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            (*pnXors)++;
        else
            (*pnMuxes)++;
    }
}
void Gia_ManPrintMuxStats( Gia_Man_t * p )
{
    int nAnds, nMuxes, nXors, nTotal;
    if ( p->pMuxes )
    {
        nAnds  = Gia_ManAndNum(p)-Gia_ManXorNum(p)-Gia_ManMuxNum(p);
        nXors  = Gia_ManXorNum(p);
        nMuxes = Gia_ManMuxNum(p);
        nTotal = nAnds + 3*nXors + 3*nMuxes;
    }
    else 
    {
        Gia_ManCountMuxXor( p, &nMuxes, &nXors );
        nAnds  = Gia_ManAndNum(p) - 3*nMuxes - 3*nXors;
        nTotal = Gia_ManAndNum(p);
    }
    Abc_Print( 1, "stats:  " );
    Abc_Print( 1, "xor =%8d %6.2f %%   ", nXors,  300.0*nXors/nTotal );
    Abc_Print( 1, "mux =%8d %6.2f %%   ", nMuxes, 300.0*nMuxes/nTotal );
    Abc_Print( 1, "and =%8d %6.2f %%   ", nAnds,  100.0*nAnds/nTotal );
    Abc_Print( 1, "obj =%8d  ", Gia_ManAndNum(p) );
    fflush( stdout );
}

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

  Synopsis    [Derives GIA with MUXes.]

  Description [Create MUX if the sum of fanin references does not exceed limit.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManDupMuxes( Gia_Man_t * p, int Limit )
{
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj, * pFan0, * pFan1, * pFanC;
    int i;
    assert( p->pMuxes == NULL );
    assert( Limit >= 2 );
    ABC_FREE( p->pRefs );
    Gia_ManCreateRefs( p ); 
    // start the new manager
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
    // create constant
    Gia_ManConst0(p)->Value = 0;
    // create PIs
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    // create internal nodes
    Gia_ManHashStart( pNew );
    Gia_ManForEachAnd( p, pObj, i )
    {
/*
        if ( !Gia_ObjIsMuxType(pObj) || Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) + Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) > Limit )
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)) );
        else
        {
            pFanC = Gia_ObjRecognizeMux( pObj, &pFan1, &pFan0 );
            pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFanC)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)) );
        }
*/
        if ( !Gia_ObjIsMuxType(pObj) )
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)) );
        else if ( Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) + Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) > Limit )
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else
        {
            pFanC = Gia_ObjRecognizeMux( pObj, &pFan1, &pFan0 );
            pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFanC)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)) );
        }
    }
    Gia_ManHashStop( pNew );
    // create ROs
    Gia_ManForEachCo( p, pObj, i )
        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
    // perform cleanup
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

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

  Synopsis    [Derives GIA without MUXes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManDupNoMuxes( Gia_Man_t * p )
{
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj;
    int i;
    assert( p->pMuxes != NULL );
    // start the new manager
    pNew = Gia_ManStart( 5000 );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    // create constant
    Gia_ManConst0(p)->Value = 0;
    // create PIs
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    // create internal nodes
    Gia_ManHashStart( pNew );
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( Gia_ObjIsMuxId(p, i) )
            pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
        else if ( Gia_ObjIsXor(pObj) )
            pObj->Value = Gia_ManHashXor( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else 
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    }
    Gia_ManHashStop( pNew );
    // create ROs
    Gia_ManForEachCo( p, pObj, i )
        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
    // perform cleanup
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

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

  Synopsis    [Test these procedures.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManDupMuxesTest( Gia_Man_t * p )
{
    Gia_Man_t * pNew, * pNew2;
    pNew = Gia_ManDupMuxes( p, 2 );
    pNew2 = Gia_ManDupNoMuxes( pNew );
    Gia_ManPrintStats( p, NULL );
    Gia_ManPrintStats( pNew, NULL );
    Gia_ManPrintStats( pNew2, NULL );
    Gia_ManStop( pNew );
//    Gia_ManStop( pNew2 );
    return pNew2;
}


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

  Synopsis    [Returns the size of MUX structure.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_MuxRef_rec( Gia_Man_t * p, int iObj )
{
    Gia_Obj_t * pObj;
    if ( !Gia_ObjIsMuxId(p, iObj) )
        return 0;
    pObj = Gia_ManObj( p, iObj );
    if ( Gia_ObjRefInc(p, pObj) )
        return 0;
    return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
           Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
           Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
}
int Gia_MuxRef( Gia_Man_t * p, int iObj )
{
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    assert( Gia_ObjIsMuxId(p, iObj) );
    return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
           Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
           Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
}
int Gia_MuxDeref_rec( Gia_Man_t * p, int iObj )
{
    Gia_Obj_t * pObj;
    if ( !Gia_ObjIsMuxId(p, iObj) )
        return 0;
    pObj = Gia_ManObj( p, iObj );
    if ( Gia_ObjRefDec(p, pObj) )
        return 0;
    return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
           Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
           Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
}
int Gia_MuxDeref( Gia_Man_t * p, int iObj )
{
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    assert( Gia_ObjIsMuxId(p, iObj) );
    return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
           Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
           Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
}
int Gia_MuxMffcSize( Gia_Man_t * p, int iObj )
{
    int Count1, Count2;
    if ( !Gia_ObjIsMuxId(p, iObj) )
        return 0;
    Count1 = Gia_MuxDeref( p, iObj );
    Count2 = Gia_MuxRef( p, iObj );
    assert( Count1 == Count2 );
    return Count1;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_MuxStructPrint_rec( Gia_Man_t * p, int iObj, int fFirst )
{
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    int iCtrl;
    if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) )
        return;
    iCtrl = Gia_ObjFaninId2p(p, pObj);
    printf( " [(" );
    if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 )
        Gia_MuxStructPrint_rec( p, iCtrl, 0 );
    else
        printf( "%d", iCtrl );
    printf( ")" );
    if ( Gia_ObjFaninC2(p, pObj) )
    {
        Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 );
        printf( "|" );
        Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 );
        printf( "] " );
    }
    else
    {
        Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 );
        printf( "|" );
        Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 );
        printf( "] " );
    }
}
void Gia_MuxStructPrint( Gia_Man_t * p, int iObj )
{
    int Count1, Count2;
    assert( Gia_ObjIsMuxId(p, iObj) );
    Count1 = Gia_MuxDeref( p, iObj );
    Gia_MuxStructPrint_rec( p, iObj, 1 );
    Count2 = Gia_MuxRef( p, iObj );
    assert( Count1 == Count2 );
    printf( "\n" );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_MuxStructDump_rec( Gia_Man_t * p, int iObj, int fFirst, Vec_Str_t * vStr, int nDigitsId )
{
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    int iCtrl;
    if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) )
        return;
    iCtrl = Gia_ObjFaninId2p(p, pObj);
    Vec_StrPush( vStr, '[' );
    Vec_StrPush( vStr, '(' );
    if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 )
        Gia_MuxStructDump_rec( p, iCtrl, 0, vStr, nDigitsId );
    else
        Vec_StrPrintNumStar( vStr, iCtrl, nDigitsId );
    Vec_StrPush( vStr, ')' );
    if ( Gia_ObjFaninC2(p, pObj) )
    {
        Gia_MuxStructDump_rec( p, Gia_ObjFaninId0p(p, pObj), 0, vStr, nDigitsId );
        Vec_StrPush( vStr, '|' );
        Gia_MuxStructDump_rec( p, Gia_ObjFaninId1p(p, pObj), 0, vStr, nDigitsId );
        Vec_StrPush( vStr, ']' );
    }
    else
    {
        Gia_MuxStructDump_rec( p, Gia_ObjFaninId1p(p, pObj), 0, vStr, nDigitsId );
        Vec_StrPush( vStr, '|' );
        Gia_MuxStructDump_rec( p, Gia_ObjFaninId0p(p, pObj), 0, vStr, nDigitsId );
        Vec_StrPush( vStr, ']' );
    }
}
void Gia_MuxStructDump( Gia_Man_t * p, int iObj, Vec_Str_t * vStr, int Num, int nDigitsNum, int nDigitsId )
{
    int Count1, Count2;
    assert( Gia_ObjIsMuxId(p, iObj) );
    Count1 = Gia_MuxDeref( p, iObj );
    Vec_StrClear( vStr );
    Vec_StrPrintNumStar( vStr, Num, nDigitsNum );
    Gia_MuxStructDump_rec( p, iObj, 1, vStr, nDigitsId );
    Vec_StrPush( vStr, '\0' );
    Count2 = Gia_MuxRef( p, iObj );
    assert( Count1 == Count2 );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ManMuxCompare( char ** pp1, char ** pp2 )
{
    int Diff = strcmp( *pp1, *pp2 );
    if ( Diff < 0 )
        return 1;
    if ( Diff > 0) 
        return -1;
    return 0; 
}
int Gia_ManMuxCountOne( char * p )
{
    int Count = 0;
    for ( ; *p; p++ )
        Count += (*p == '[');
    return Count;
}
void Gia_ManMuxProfile( Vec_Ptr_t * p, Vec_Int_t * vCounts )
{
    int i; char * pTemp;
    Vec_IntFill( vCounts, 1000, 0 );
    Vec_PtrForEachEntry( char *, p, pTemp, i )
        Vec_IntAddToEntry( vCounts, Abc_MinInt(Gia_ManMuxCountOne(pTemp), 999), 1 );
}

void Gia_ManMuxProfiling( Gia_Man_t * p )
{
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj;
    Vec_Int_t * vFans;
    Vec_Int_t * vCounts = Vec_IntAlloc( 100 );
    Vec_Ptr_t * vTrees  = Vec_PtrAlloc( 1000 );
    Vec_Str_t * vStr    = Vec_StrAlloc( 1000 );
    Vec_Int_t * vDegree = Vec_IntAlloc( 1000 );
    int i, nRefs, Size, Count, Total = 0, Roots = 0;
    int nDigitsId, nMemory = 0;
    char * pTemp;
    abctime clk = Abc_Clock();

    pNew = Gia_ManDupMuxes( p, 2 );
    nDigitsId = Abc_Base10Log( Gia_ManObjNum(pNew) );

    Gia_ManCreateRefs( pNew );
    Gia_ManForEachCo( pNew, pObj, i )
        Gia_ObjRefFanin0Inc( pNew, pObj );

    Vec_IntFill( vCounts, 1000, 0 );
    vFans = Gia_ManFirstFanouts( pNew );
    Gia_ManForEachMux( pNew, pObj, i )
    {
        Total++;
        nRefs = Gia_ObjRefNumId(pNew, i);
        assert( nRefs > 0 );
        if ( nRefs > 1 || !Gia_ObjIsMuxId(pNew, Vec_IntEntry(vFans, i)) )
        {
            Roots++;
            Size = Gia_MuxMffcSize(pNew, i);
            Vec_IntAddToEntry( vCounts, Abc_MinInt(Size, 999), 1 );
            if ( Size >= 2 )
            {
                Gia_MuxStructDump( pNew, i, vStr, Size, 3, nDigitsId );
                Vec_PtrPush( vTrees, Abc_UtilStrsav(Vec_StrArray(vStr)) );
                nMemory += Vec_StrSize(vStr);
            }
        }
    }
    printf( "MUXes: Total = %d. Roots = %d. Trees = %d.  Memory = %.2f MB\n", Total, Roots, Vec_PtrSize(vTrees), 1.0*nMemory/(1<<20) );
    Vec_IntForEachEntry( vCounts, Count, i )
        if ( Count )
            printf( "%d=%d ", i, Count );
    printf( "\n" );

//    Vec_PtrForEachEntryStop( char *, vTrees, pTemp, i, Abc_MinInt(Vec_PtrSize(vTrees), 40) )
//        printf( "%6d : %3d %3d  %s\n", i, -1, Gia_ManMuxCountOne(pTemp), pTemp );

    // uniqify
    Vec_PtrUniqify2( vTrees, (int (*)(void))Gia_ManMuxCompare, (void (*)(void))free, vDegree );
    Gia_ManMuxProfile( vTrees, vCounts );

    nMemory = 0;
    Vec_PtrForEachEntry( char *, vTrees, pTemp, i )
        nMemory += strlen(pTemp);

    printf( "MUXes: Trees = %d.  Memory = %.2f MB\n", Vec_PtrSize(vTrees), 1.0*nMemory/(1<<20) );
    Vec_IntForEachEntry( vCounts, Count, i )
        if ( Count )
            printf( "%d=%d ", i, Count );
    printf( "\n" );

//    Vec_PtrForEachEntryStop( char *, vTrees, pTemp, i, Abc_MinInt(Vec_PtrSize(vTrees), 40) )
//        printf( "%6d : %3d %3d  %s\n", i, Vec_IntEntry(vDegree, i), Gia_ManMuxCountOne(pTemp), pTemp );

    Vec_PtrForEachEntryStop( char *, vTrees, pTemp, i, Abc_MinInt(Vec_PtrSize(vTrees), 5000) )
        if ( Vec_IntEntry(vDegree, i) > 10 )
            printf( "%6d : %3d %3d  %s\n", i, Vec_IntEntry(vDegree, i), Gia_ManMuxCountOne(pTemp), pTemp );

    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );

    Vec_PtrFreeFree( vTrees );
    Vec_StrFree( vStr );
    Vec_IntFree( vDegree );
    Vec_IntFree( vCounts );
    Vec_IntFree( vFans );
    Gia_ManStop( pNew );
}


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


ABC_NAMESPACE_IMPL_END