giaCone.c

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

  FileName    [giaCone.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    []

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "gia.h"
#include "misc/extra/extra.h"
#include "misc/vec/vecHsh.h"
#include "misc/vec/vecWec.h"

ABC_NAMESPACE_IMPL_START


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

typedef struct Opa_Man_t_ Opa_Man_t;
struct Opa_Man_t_
{
    Gia_Man_t *    pGia;
    Vec_Int_t *    vFront;
    Vec_Int_t *    pvParts;
    int *          pId2Part; 
    int            nParts;
};

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////
    
/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Opa_Man_t * Opa_ManStart( Gia_Man_t * pGia)
{
    Opa_Man_t * p;
    Gia_Obj_t * pObj;
    int i;
    p = ABC_CALLOC( Opa_Man_t, 1 );
    p->pGia = pGia;
    p->pvParts  = ABC_CALLOC( Vec_Int_t, Gia_ManPoNum(pGia) );
    p->pId2Part = ABC_FALLOC( int, Gia_ManObjNum(pGia) );
    p->vFront   = Vec_IntAlloc( 100 );
    Gia_ManForEachPo( pGia, pObj, i )
    {
        Vec_IntPush( p->pvParts + i, Gia_ObjId(pGia, pObj) );
        p->pId2Part[Gia_ObjId(pGia, pObj)] = i;
        Vec_IntPush( p->vFront, Gia_ObjId(pGia, pObj) );
    }
    p->nParts = Gia_ManPoNum(pGia);
    return p;
}
static inline void Opa_ManStop( Opa_Man_t * p )
{
    int i;
    Vec_IntFree( p->vFront );
    for ( i = 0; i < Gia_ManPoNum(p->pGia); i++ )
        ABC_FREE( p->pvParts[i].pArray );
    ABC_FREE( p->pvParts );
    ABC_FREE( p->pId2Part );
    ABC_FREE( p );
}
static inline void Opa_ManPrint( Opa_Man_t * p )
{
    int i, k;
    printf( "Groups:\n" );
    for ( i = 0; i < Gia_ManPoNum(p->pGia); i++ )
    {
        if ( p->pvParts[i].nSize == 0 )
            continue;
        printf( "%3d : ", i );
        for ( k = 0; k < p->pvParts[i].nSize; k++ )
            printf( "%d ", p->pvParts[i].pArray[k] );
        printf( "\n" );
    }
}
static inline void Opa_ManPrint2( Opa_Man_t * p )
{
    Gia_Obj_t * pObj;
    int i, k, Count;
    printf( "Groups %d: ", p->nParts );
    for ( i = 0; i < Gia_ManPoNum(p->pGia); i++ )
    {
        if ( p->pvParts[i].nSize == 0 )
            continue;
        // count POs in this group
        Count = 0;
        Gia_ManForEachObjVec( p->pvParts + i, p->pGia, pObj, k )
            Count += Gia_ObjIsPo(p->pGia, pObj);
        printf( "%d ", Count );
    }
    printf( "\n" );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Opa_ManMoveOne( Opa_Man_t * p, Gia_Obj_t * pObj, Gia_Obj_t * pFanin )
{
    int iObj   = Gia_ObjId(p->pGia, pObj);
    int iFanin = Gia_ObjId(p->pGia, pFanin);
    if ( iFanin == 0 )
        return;
    assert( p->pId2Part[ iObj ] >= 0 );
    if ( p->pId2Part[ iFanin ] == -1 )
    {
        p->pId2Part[ iFanin ] = p->pId2Part[ iObj ];
        Vec_IntPush( p->pvParts + p->pId2Part[ iObj ], iFanin );
        assert( Gia_ObjIsCi(pFanin) || Gia_ObjIsAnd(pFanin) );
        if ( Gia_ObjIsAnd(pFanin) )
            Vec_IntPush( p->vFront, iFanin );
        else if ( Gia_ObjIsRo(p->pGia, pFanin) )
        {
            pFanin = Gia_ObjRoToRi(p->pGia, pFanin);
            iFanin = Gia_ObjId(p->pGia, pFanin);
            assert( p->pId2Part[ iFanin ] == -1 );
            p->pId2Part[ iFanin ] = p->pId2Part[ iObj ];
            Vec_IntPush( p->pvParts + p->pId2Part[ iObj ], iFanin );
            Vec_IntPush( p->vFront, iFanin );
        }
    }
    else if ( p->pId2Part[ iObj ] != p->pId2Part[ iFanin ] )
    {
        Vec_Int_t * vPartObj = p->pvParts + p->pId2Part[ iObj ];
        Vec_Int_t * vPartFan = p->pvParts + p->pId2Part[ iFanin ];
        int iTemp, i;
//        printf( "Moving %d to %d (%d -> %d)\n", iObj, iFanin, Vec_IntSize(vPartObj), Vec_IntSize(vPartFan) );
        // add group of iObj to group of iFanin
        assert( Vec_IntSize(vPartObj) > 0 );
        Vec_IntForEachEntry( vPartObj, iTemp, i )
        {
            Vec_IntPush( vPartFan, iTemp );
            p->pId2Part[ iTemp ] = p->pId2Part[ iFanin ];
        }
        Vec_IntShrink( vPartObj, 0 );
        p->nParts--;
    }
}
void Opa_ManPerform( Gia_Man_t * pGia )
{
    Opa_Man_t * p;
    Gia_Obj_t * pObj;
    int i, Limit, Count = 0;
 
    p = Opa_ManStart( pGia );
    Limit = Vec_IntSize(p->vFront);
//Opa_ManPrint2( p );
    Gia_ManForEachObjVec( p->vFront, pGia, pObj, i )
    {
        if ( i == Limit )
        {
            printf( "%6d : %6d -> %6d\n", ++Count, i, p->nParts );
            Limit = Vec_IntSize(p->vFront);
            if ( Count > 1 )
                Opa_ManPrint2( p );
        }
//        printf( "*** Object %d  ", Gia_ObjId(pGia, pObj) );
        if ( Gia_ObjIsAnd(pObj) )
        {
            Opa_ManMoveOne( p, pObj, Gia_ObjFanin0(pObj) );
            Opa_ManMoveOne( p, pObj, Gia_ObjFanin1(pObj) );
        }
        else if ( Gia_ObjIsCo(pObj) )
            Opa_ManMoveOne( p, pObj, Gia_ObjFanin0(pObj) );
        else assert( 0 );
//        if ( i % 10 == 0 )
//            printf( "%d   ", p->nParts );
        if ( p->nParts == 1 )
            break;
        if ( Count == 5 )
            break;
    }
    printf( "\n" );
    Opa_ManStop( p );
}



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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ManConeMark_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vRoots, int nLimit )
{
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return 0;
    Gia_ObjSetTravIdCurrent(p, pObj);
    if ( Gia_ObjIsAnd(pObj) )
    {
        if ( Gia_ManConeMark_rec( p, Gia_ObjFanin0(pObj), vRoots, nLimit ) )
            return 1;
        if ( Gia_ManConeMark_rec( p, Gia_ObjFanin1(pObj), vRoots, nLimit ) )
            return 1;
    }
    else if ( Gia_ObjIsCo(pObj) )
    {
        if ( Gia_ManConeMark_rec( p, Gia_ObjFanin0(pObj), vRoots, nLimit ) )
            return 1;
    }
    else if ( Gia_ObjIsRo(p, pObj) )
        Vec_IntPush( vRoots, Gia_ObjId(p, Gia_ObjRoToRi(p, pObj)) );
    else if ( Gia_ObjIsPi(p, pObj) )
    {}
    else assert( 0 );
    return (int)(Vec_IntSize(vRoots) > nLimit);
}
int Gia_ManConeMark( Gia_Man_t * p, int iOut, int Limit )
{
    Vec_Int_t * vRoots;
    Gia_Obj_t * pObj;
    int i, RetValue;
    // start the outputs
    pObj = Gia_ManPo( p, iOut );
    vRoots = Vec_IntAlloc( 100 );
    Vec_IntPush( vRoots, Gia_ObjId(p, pObj) );
    // mark internal nodes
    Gia_ManIncrementTravId( p );
    Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
    Gia_ManForEachObjVec( vRoots, p, pObj, i )
        if ( Gia_ManConeMark_rec( p, pObj, vRoots, Limit ) )
            break;
    RetValue = Vec_IntSize( vRoots ) - 1;
    Vec_IntFree( vRoots );
    return RetValue;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ManCountFlops( Gia_Man_t * p, Vec_Int_t * vOuts )
{
    int Limit = ABC_INFINITY;
    Vec_Int_t * vRoots;
    Gia_Obj_t * pObj;
    int i, RetValue, iOut;
    // start the outputs
    vRoots = Vec_IntAlloc( 100 );
    Vec_IntForEachEntry( vOuts, iOut, i )
    {
        pObj = Gia_ManPo( p, iOut );
        Vec_IntPush( vRoots, Gia_ObjId(p, pObj) );
    }
    // mark internal nodes
    Gia_ManIncrementTravId( p );
    Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
    Gia_ManForEachObjVec( vRoots, p, pObj, i )
        if ( Gia_ManConeMark_rec( p, pObj, vRoots, Limit ) )
            break;
    RetValue = Vec_IntSize( vRoots ) - Vec_IntSize(vOuts);
    Vec_IntFree( vRoots );
    return RetValue;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManFindPoPartition3( Gia_Man_t * p, int iOut, int nDelta, int nOutsMin, int nOutsMax, int fVerbose, Vec_Ptr_t ** pvPosEquivs )
{
/*
    int i, Count = 0;
    // mark nodes belonging to output 'iOut'
    for ( i = 0; i < Gia_ManPoNum(p); i++ )
        Count += (Gia_ManConeMark(p, i, 10000) < 10000);
     //   printf( "%d ", Gia_ManConeMark(p, i, 1000) );
    printf( "%d out of %d\n", Count, Gia_ManPoNum(p) );

    // add other outputs as long as they are nDelta away
*/
//    Opa_ManPerform( p );

    return NULL;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_ManFindPivots( Gia_Man_t * p, int SelectShift, int fOnlyCis, int fVerbose )
{
    Vec_Int_t * vPivots, * vWeights;
    Vec_Int_t * vCount, * vResult;
    int i, j, Count, * pPerm, Limit;
/*
    Gia_Obj_t * pObj;
    // count MUX controls
    vCount = Vec_IntStart( Gia_ManObjNum(p) );
    Gia_ManForEachAnd( p, pObj, i )
    {
        Gia_Obj_t * pNodeC, * pNodeT, * pNodeE;
        if ( !Gia_ObjIsMuxType(pObj) ) 
            continue;
        pNodeC = Gia_ObjRecognizeMux( pObj, &pNodeT, &pNodeE );
        Vec_IntAddToEntry( vCount, Gia_ObjId(p, Gia_Regular(pNodeC)), 1 );
    }
*/
    // count references
    Gia_ManCreateRefs( p );
    vCount = Vec_IntAllocArray( p->pRefs, Gia_ManObjNum(p) ); p->pRefs = NULL;

    // collect nodes 
    vPivots  = Vec_IntAlloc( 100 );
    vWeights = Vec_IntAlloc( 100 );
    Vec_IntForEachEntry( vCount, Count, i )
    {
        if ( Count < 2 ) continue;
        if ( fOnlyCis && !Gia_ObjIsCi(Gia_ManObj(p, i)) )
            continue;
        Vec_IntPush( vPivots, i );
        Vec_IntPush( vWeights, Count );
    }
    Vec_IntFree( vCount );

    if ( fVerbose )
        printf( "Selected %d pivots with more than one fanout (out of %d CIs and ANDs).\n", Vec_IntSize(vWeights), Gia_ManCiNum(p) + Gia_ManAndNum(p) );

    // permute
    Gia_ManRandom(1);
    Gia_ManRandom(0);
    for ( i = 0; i < Vec_IntSize(vWeights); i++ )
    {
        j = (Gia_ManRandom(0) >> 1) % Vec_IntSize(vWeights);
        ABC_SWAP( int, vPivots->pArray[i], vPivots->pArray[j] );
        ABC_SWAP( int, vWeights->pArray[i], vWeights->pArray[j] );
    }
    // sort
    if ( SelectShift == 0 )
        pPerm = Abc_QuickSortCost( Vec_IntArray(vWeights), Vec_IntSize(vWeights), 1 );
    else
    {
        Vec_Int_t * vTemp = Vec_IntStartNatural( Vec_IntSize(vWeights) );
        pPerm = Vec_IntReleaseArray( vTemp );
        Vec_IntFree( vTemp );
    }

    // select    
    Limit = Abc_MinInt( 64, Vec_IntSize(vWeights) );
    vResult = Vec_IntAlloc( Limit );
    for ( i = 0; i < Limit; i++ )
    {
        j = (i + SelectShift) % Vec_IntSize(vWeights);
        if ( fVerbose )
            printf( "%2d : Pivot =%7d  Fanout =%7d\n", j, Vec_IntEntry(vPivots, pPerm[j]), Vec_IntEntry(vWeights, pPerm[j]) );
        Vec_IntPush( vResult, Vec_IntEntry(vPivots, pPerm[j]) );
    }

    Vec_IntFree( vPivots );
    Vec_IntFree( vWeights );
    ABC_FREE( pPerm );

    return vResult;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wrd_t * Gia_ManDeriveSigns( Gia_Man_t * p, Vec_Int_t * vPivots, int fVerbose )
{
    Vec_Wrd_t * vSigns;
    Gia_Obj_t * pObj, * pObjRi;
    int i, fChange = 1, Counter;

    Gia_ManFillValue( p );
    Gia_ManForEachObjVec( vPivots, p, pObj, i )
        pObj->Value = i;

    if ( fVerbose )
        printf( "Signature propagation: " );
    vSigns = Vec_WrdStart( Gia_ManObjNum(p) );
    while ( fChange )
    {
        fChange = 0;
        Gia_ManForEachObj( p, pObj, i )
        {
            if ( ~pObj->Value )
            {
                assert( pObj->Value >= 0 && pObj->Value < 64 );
                *Vec_WrdEntryP( vSigns, i ) |= ( (word)1 << pObj->Value );
            }
            if ( Gia_ObjIsAnd(pObj) )
                *Vec_WrdEntryP( vSigns, i ) |= Vec_WrdEntry(vSigns, Gia_ObjFaninId0(pObj, i)) | Vec_WrdEntry(vSigns, Gia_ObjFaninId1(pObj, i));
            else if ( Gia_ObjIsCo(pObj) )
                *Vec_WrdEntryP( vSigns, i ) |= Vec_WrdEntry(vSigns, Gia_ObjFaninId0(pObj, i));
        }
        Counter = 0;
        Gia_ManForEachRiRo( p, pObjRi, pObj, i )
        {
            word Value = Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj));
            *Vec_WrdEntryP( vSigns, Gia_ObjId(p, pObj) ) |= Vec_WrdEntry(vSigns, Gia_ObjId(p, pObjRi));
            if ( Value != Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj)) )
                fChange = 1, Counter++;
        }
        if ( fVerbose )
            printf( "%d ", Counter );
    }
    if ( fVerbose )
       printf( "\n" );
    return vSigns;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Gia_ManHashOutputs( Gia_Man_t * p, Vec_Wrd_t * vSigns, int fVerbose )
{
    Vec_Ptr_t * vBins;
    Vec_Wec_t * vClasses;
    Vec_Wrd_t * vSignsPo;
    Vec_Int_t * vPriority, * vBin;
    Gia_Obj_t * pObj;
    int i;
    // collect PO signatures
    vSignsPo = Vec_WrdAlloc( Gia_ManPoNum(p) );
    Gia_ManForEachPo( p, pObj, i )
        Vec_WrdPush( vSignsPo, Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj)) );
    // find equivalence classes
    vPriority = Hsh_WrdManHashArray( vSignsPo, 1 );
    Vec_WrdFree( vSignsPo );
    vClasses = Vec_WecCreateClasses( vPriority );
    Vec_IntFree( vPriority );
    vBins = (Vec_Ptr_t *)Vec_WecConvertToVecPtr( vClasses );
    Vec_WecFree( vClasses );
    Vec_VecSort( (Vec_Vec_t *)vBins, 1 );

    if ( fVerbose )
        printf( "Computed %d partitions:\n", Vec_PtrSize(vBins) );
    if ( !fVerbose )
        printf( "Listing partitions with more than 100 outputs:\n" );
    Vec_PtrForEachEntry( Vec_Int_t *, vBins, vBin, i )
    {
        assert( Vec_IntSize(vBin) > 0 );
        if ( fVerbose || Vec_IntSize(vBin) > 100 )
        {
            int PoNum = Vec_IntEntry( vBin, 0 );
            Gia_Obj_t * pObj = Gia_ManPo( p, PoNum );
            word Sign = Vec_WrdEntry( vSigns, Gia_ObjId(p, pObj) );
            // print
            printf( "%3d ", i );
            Extra_PrintBinary( stdout, (unsigned *)&Sign, 64 );
            printf( "  " );
            printf( "PO =%7d  ", Vec_IntSize(vBin) );
            printf( "FF =%7d", Gia_ManCountFlops(p, vBin) );
            printf( "\n" );
        }
    }
    return vBins;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManFindPoPartition2( Gia_Man_t * p, int iStartNum, int nDelta, int nOutsMin, int nOutsMax, int fSetLargest, int fVerbose, Vec_Ptr_t ** pvPosEquivs )
{
    return NULL;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManFindPoPartition( Gia_Man_t * p, int SelectShift, int fOnlyCis, int fSetLargest, int fVerbose, Vec_Ptr_t ** pvPosEquivs )
{
    Gia_Man_t * pGia = NULL;
    Vec_Int_t * vPivots;
    Vec_Wrd_t * vSigns;
    Vec_Ptr_t * vParts;
    Vec_Int_t * vPart;
    abctime clk = Abc_Clock();
    vPivots = Gia_ManFindPivots( p, SelectShift, fOnlyCis, fVerbose );
    vSigns = Gia_ManDeriveSigns( p, vPivots, fVerbose );
    Vec_IntFree( vPivots );
    vParts = Gia_ManHashOutputs( p, vSigns, fVerbose );
    Vec_WrdFree( vSigns );
    if ( fSetLargest )
    {
        vPart = Vec_VecEntryInt( (Vec_Vec_t *)vParts, 0 );
        pGia = Gia_ManDupCones( p, Vec_IntArray(vPart), Vec_IntSize(vPart), 1 );
    }
    if ( pvPosEquivs )
    {
        *pvPosEquivs = vParts;
        printf( "The algorithm divided %d POs into %d partitions.   ", Gia_ManPoNum(p), Vec_PtrSize(vParts) );
        Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    }
    else
        Vec_VecFree( (Vec_Vec_t *)vParts );
    return pGia;
}

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


ABC_NAMESPACE_IMPL_END