giaSplit.c

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

  FileName    [giaSplit.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [Structural AIG splitting.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "gia.h"
#include "misc/extra/extra.h"

ABC_NAMESPACE_IMPL_START


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

typedef struct Spl_Man_t_ Spl_Man_t;
struct Spl_Man_t_
{
    // input data
    Gia_Man_t *      pGia;       // user AIG with nodes marked
    int              iObj;       // object ID
    int              Limit;      // limit on AIG nodes
    int              fReverse;   // enable reverse search
    // intermediate
    Vec_Bit_t *      vMarksCIO;  // CI/CO marks
    Vec_Bit_t *      vMarksIn;   // input marks
    Vec_Bit_t *      vMarksNo;   // node marks
    Vec_Bit_t *      vMarksAnd;  // AND node marks
    Vec_Int_t *      vRoots;     // nodes pointing to Nodes
    Vec_Int_t *      vNodes;     // nodes used in the window
    Vec_Int_t *      vLeaves;    // nodes pointed by Nodes
    Vec_Int_t *      vAnds;      // AND nodes used in the window
    // temporary 
    Vec_Int_t *      vFanouts;   // fanouts of the node
    Vec_Int_t *      vCands;     // candidate nodes
    Vec_Int_t *      vInputs;    // non-trivial inputs
};

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

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

  Synopsis    [Transforming to the internal LUT representation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wec_t * Spl_ManToWecMapping( Gia_Man_t * p )
{
    Vec_Wec_t * vMapping = Vec_WecStart( Gia_ManObjNum(p) );
    int Obj, Fanin, k;
    assert( Gia_ManHasMapping(p) );
    Gia_ManForEachLut( p, Obj )
        Gia_LutForEachFanin( p, Obj, Fanin, k )
            Vec_WecPush( vMapping, Obj, Fanin );
    return vMapping;
}
Vec_Int_t * Spl_ManFromWecMapping( Gia_Man_t * p, Vec_Wec_t * vMap )
{
    Vec_Int_t * vMapping, * vVec; int i, k, Obj;
    assert( Gia_ManHasMapping2(p) );
    vMapping = Vec_IntAlloc( Gia_ManObjNum(p) + Vec_WecSizeSize(vMap) + 2*Vec_WecSizeUsed(vMap) );
    Vec_IntFill( vMapping, Gia_ManObjNum(p), 0 );
    Vec_WecForEachLevel( vMap, vVec, i )
        if ( Vec_IntSize(vVec) > 0 )
        {
            Vec_IntWriteEntry( vMapping, i, Vec_IntSize(vMapping) );
            Vec_IntPush( vMapping, Vec_IntSize(vVec) );
            Vec_IntForEachEntry( vVec, Obj, k )
                Vec_IntPush( vMapping, Obj );
            Vec_IntPush( vMapping, i );
        }
    assert( Vec_IntSize(vMapping) < 16 || Vec_IntSize(vMapping) == Vec_IntCap(vMapping) );
    return vMapping;
}


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

  Synopsis    [Creating manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Spl_Man_t * Spl_ManAlloc( Gia_Man_t * pGia, int Limit, int fReverse )
{
    int i, iObj;
    Spl_Man_t * p = ABC_CALLOC( Spl_Man_t, 1 );
    p->pGia       = pGia;
    p->Limit      = Limit;
    p->fReverse   = fReverse;
    // intermediate
    p->vMarksCIO  = Vec_BitStart( Gia_ManObjNum(pGia) );
    p->vMarksIn   = Vec_BitStart( Gia_ManObjNum(pGia) );
    p->vMarksNo   = Vec_BitStart( Gia_ManObjNum(pGia) );
    p->vMarksAnd  = Vec_BitStart( Gia_ManObjNum(pGia) );
    p->vRoots     = Vec_IntAlloc( 100 );
    p->vNodes     = Vec_IntAlloc( 100 );
    p->vLeaves    = Vec_IntAlloc( 100 );
    p->vAnds      = Vec_IntAlloc( 100 );
    // temporary 
    p->vFanouts   = Vec_IntAlloc( 100 );
    p->vCands     = Vec_IntAlloc( 100 );
    p->vInputs    = Vec_IntAlloc( 100 );
    // mark CIs/COs
    Vec_BitWriteEntry( p->vMarksCIO, 0, 1 );
    Gia_ManForEachCiId( pGia, iObj, i )
        Vec_BitWriteEntry( p->vMarksCIO, iObj, 1 );
    Gia_ManForEachCoId( pGia, iObj, i )
        Vec_BitWriteEntry( p->vMarksCIO, iObj, 1 );
    // mapping
    ABC_FREE( pGia->pRefs );
    Gia_ManCreateRefs( pGia );
    Gia_ManSetLutRefs( pGia );
    assert( Gia_ManHasMapping(pGia) );
    assert( !Gia_ManHasMapping2(pGia) );
    pGia->vMapping2 = Spl_ManToWecMapping( pGia );
    Vec_IntFreeP( &pGia->vMapping );
    // fanout
    Gia_ManStaticFanoutStart( pGia );
    return p;
}
void Spl_ManStop( Spl_Man_t * p )
{
    // fanout
    Gia_ManStaticFanoutStop( p->pGia );
    // mapping
    assert( !Gia_ManHasMapping(p->pGia) );
    assert( Gia_ManHasMapping2(p->pGia) );
    p->pGia->vMapping = Spl_ManFromWecMapping( p->pGia, p->pGia->vMapping2 );
    Vec_WecFreeP( &p->pGia->vMapping2 );
    // intermediate
    Vec_BitFree( p->vMarksCIO );
    Vec_BitFree( p->vMarksIn );
    Vec_BitFree( p->vMarksNo );
    Vec_BitFree( p->vMarksAnd );
    Vec_IntFree( p->vRoots );
    Vec_IntFree( p->vNodes );
    Vec_IntFree( p->vLeaves );
    Vec_IntFree( p->vAnds );
    // temporary 
    Vec_IntFree( p->vFanouts );
    Vec_IntFree( p->vCands );
    Vec_IntFree( p->vInputs );
    ABC_FREE( p );
}

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

  Synopsis    [Takes Nodes and Marks. Returns Leaves and Roots.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Spl_ManWinFindLeavesRoots( Spl_Man_t * p )
{
    Vec_Int_t * vVec;
    int iObj, iFan, i, k;
    // collect leaves
/*
    Vec_IntClear( p->vLeaves );
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
    {
        assert( Vec_BitEntry(p->vMarksNo, iObj) );
        Vec_IntForEachEntry( vVec, iFan, k )
            if ( !Vec_BitEntry(p->vMarksNo, iFan) )
            {
                Vec_BitWriteEntry(p->vMarksNo, iFan, 1);
                Vec_IntPush( p->vLeaves, iFan );
            }
    }
    Vec_IntForEachEntry( p->vLeaves, iFan, i )
        Vec_BitWriteEntry(p->vMarksNo, iFan, 0);
*/
    Vec_IntClear( p->vLeaves );
    Vec_IntForEachEntry( p->vAnds, iObj, i )
    {
        Gia_Obj_t * pObj = Gia_ManObj( p->pGia, iObj );
        assert( Vec_BitEntry(p->vMarksAnd, iObj) );
        iFan = Gia_ObjFaninId0( pObj, iObj );
        if ( !Vec_BitEntry(p->vMarksAnd, iFan) )
        {
            assert( Gia_ObjIsLut2(p->pGia, iFan) || Vec_BitEntry(p->vMarksCIO, iFan) );
            Vec_BitWriteEntry(p->vMarksAnd, iFan, 1);
            Vec_IntPush( p->vLeaves, iFan );
        }
        iFan = Gia_ObjFaninId1( pObj, iObj );
        if ( !Vec_BitEntry(p->vMarksAnd, iFan) )
        {
            assert( Gia_ObjIsLut2(p->pGia, iFan) || Vec_BitEntry(p->vMarksCIO, iFan) );
            Vec_BitWriteEntry(p->vMarksAnd, iFan, 1);
            Vec_IntPush( p->vLeaves, iFan );
        }
    }
    Vec_IntForEachEntry( p->vLeaves, iFan, i )
        Vec_BitWriteEntry(p->vMarksAnd, iFan, 0);

    // collect roots
    Vec_IntClear( p->vRoots );
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
        Vec_IntForEachEntry( vVec, iFan, k )
            Gia_ObjLutRefDecId( p->pGia, iFan );
    Vec_IntForEachEntry( p->vAnds, iObj, i )
        if ( Gia_ObjLutRefNumId(p->pGia, iObj) )
            Vec_IntPush( p->vRoots, iObj );
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
        Vec_IntForEachEntry( vVec, iFan, k )
            Gia_ObjLutRefIncId( p->pGia, iFan );
}




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

  Synopsis    [Computes LUTs that are fanouts of the node outside of the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Spl_ManLutFanouts_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vFanouts, Vec_Bit_t * vMarksNo, Vec_Bit_t * vMarksCIO )
{
    int iFanout, i;
    if ( Vec_BitEntry(vMarksNo, iObj) || Vec_BitEntry(vMarksCIO, iObj) )
        return;
    if ( Gia_ObjIsLut2(p, iObj) )
    {
        Vec_BitWriteEntry( vMarksCIO, iObj, 1 );
        Vec_IntPush( vFanouts, iObj );
        return;
    }
    Gia_ObjForEachFanoutStaticId( p, iObj, iFanout, i )
        Spl_ManLutFanouts_rec( p, iFanout, vFanouts, vMarksNo, vMarksCIO );
}
int Spl_ManLutFanouts( Gia_Man_t * p, int iObj, Vec_Int_t * vFanouts, Vec_Bit_t * vMarksNo, Vec_Bit_t * vMarksCIO )
{
    int i, iFanout;
    assert( Gia_ObjIsLut2(p, iObj) );
    Vec_IntClear( vFanouts );
    Gia_ObjForEachFanoutStaticId( p, iObj, iFanout, i )
        Spl_ManLutFanouts_rec( p, iFanout, vFanouts, vMarksNo, vMarksCIO );
    // clean up
    Vec_IntForEachEntry( vFanouts, iFanout, i )
        Vec_BitWriteEntry( vMarksCIO, iFanout, 0 );
    return Vec_IntSize(vFanouts);
}


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

  Synopsis    [Returns the number of fanins beloning to the set.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Spl_ManCountMarkedFanins( Gia_Man_t * p, int iObj, Vec_Bit_t * vMarks )
{
    int i, iFan, Count = 0;
    Vec_Int_t * vFanins = Gia_ObjLutFanins2(p, iObj);
    Vec_IntForEachEntry( vFanins, iFan, i )
        if ( Vec_BitEntry(vMarks, iFan) )
            Count++;
    return Count;
}
int Spl_ManFindGoodCand( Spl_Man_t * p )
{
    int i, iObj;
    int Res = 0, InCount, InCountMax = -1; 
    // mark leaves
    Vec_IntForEachEntry( p->vInputs, iObj, i )
        Vec_BitWriteEntry( p->vMarksIn, iObj, 1 );
    // find candidate with maximum input overlap
    Vec_IntForEachEntry( p->vCands, iObj, i )
    {
        InCount = Spl_ManCountMarkedFanins( p->pGia, iObj, p->vMarksIn );
        if ( InCountMax < InCount )
        {
            InCountMax = InCount;
            Res = iObj;
        }
    }
    // unmark leaves
    Vec_IntForEachEntry( p->vInputs, iObj, i )
        Vec_BitWriteEntry( p->vMarksIn, iObj, 0 );
    return Res;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Spl_ManFindOne( Spl_Man_t * p )
{
    Vec_Int_t * vVec;
    int nFanouts, iObj, iFan, i, k;
    int Res = 0; 

    // deref
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
        Vec_IntForEachEntry( vVec, iFan, k )
            Gia_ObjLutRefDecId( p->pGia, iFan );

    // collect external nodes
    if ( p->fReverse && (Vec_IntSize(p->vNodes) & 1) )
    {
        Vec_IntForEachEntry( p->vNodes, iObj, i )
        {
            if ( Gia_ObjLutRefNumId(p->pGia, iObj) == 0 )
                continue;
            assert( Gia_ObjLutRefNumId(p->pGia, iObj) > 0 );
            if ( Gia_ObjLutRefNumId(p->pGia, iObj) >= 5 )  // skip nodes with high fanout!
                continue;
            nFanouts = Spl_ManLutFanouts( p->pGia, iObj, p->vFanouts, p->vMarksNo, p->vMarksCIO );
            if ( Gia_ObjLutRefNumId(p->pGia, iObj) == 1 && nFanouts == 1 )
            {
                Res = Vec_IntEntry(p->vFanouts, 0);
                goto finish;
            }
            //Vec_IntAppend( p->vCands, p->vFanouts );
        }
    }

    // consider LUT inputs - get one that has no refs
    Vec_IntClear( p->vCands );
    Vec_IntClear( p->vInputs );
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
        Vec_IntForEachEntry( vVec, iFan, k )
            if ( !Vec_BitEntry(p->vMarksNo, iFan) && !Vec_BitEntry(p->vMarksCIO, iFan) && !Gia_ObjLutRefNumId(p->pGia, iFan) )
            {
                Vec_IntPush( p->vCands, iFan );
                Vec_IntPush( p->vInputs, iFan );
            }
    Res = Spl_ManFindGoodCand( p );
    if ( Res )
        goto finish;

    // collect candidates
    Vec_IntClear( p->vCands );
    Vec_IntClear( p->vInputs );
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
        Vec_IntForEachEntry( vVec, iFan, k )
            if ( !Vec_BitEntry(p->vMarksNo, iFan) && !Vec_BitEntry(p->vMarksCIO, iFan) )
            {
                Vec_IntPush( p->vCands, iFan );
                Vec_IntPush( p->vInputs, iFan );
            }

    // all inputs have refs - collect external nodes
    Vec_IntForEachEntry( p->vNodes, iObj, i )
    {
        if ( Gia_ObjLutRefNumId(p->pGia, iObj) == 0 )
            continue;
        assert( Gia_ObjLutRefNumId(p->pGia, iObj) > 0 );
        if ( Gia_ObjLutRefNumId(p->pGia, iObj) >= 5 )  // skip nodes with high fanout!
            continue;
        nFanouts = Spl_ManLutFanouts( p->pGia, iObj, p->vFanouts, p->vMarksNo, p->vMarksCIO );
        if ( Gia_ObjLutRefNumId(p->pGia, iObj) == 1 && nFanouts == 1 )
        {
            Res = Vec_IntEntry(p->vFanouts, 0);
            goto finish;
        }
        Vec_IntAppend( p->vCands, p->vFanouts );
    }

    // choose among not-so-good ones
    Res = Spl_ManFindGoodCand( p );
    if ( Res )
        goto finish;

    // get the first candidate
    if ( Res == 0 && Vec_IntSize(p->vCands) > 0 )
        Res = Vec_IntEntry( p->vCands, 0 );

finish:
    // ref
    Gia_ManForEachLut2Vec( p->vNodes, p->pGia, vVec, iObj, i )
        Vec_IntForEachEntry( vVec, iFan, k )
            Gia_ObjLutRefIncId( p->pGia, iFan );
    return Res;
}



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

  Synopsis    [Computing window for one pivot node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Spl_ManLutMffcSize( Gia_Man_t * p, int iObj, Vec_Int_t * vTemp, Vec_Bit_t * vMarksAnd )
{
    int iTemp, i, k = 0;
    assert( Gia_ObjIsLut2(p, iObj) );
//Vec_IntPrint( Gia_ObjLutFanins2(p, iObj) );
    Gia_ManIncrementTravId( p );
    Gia_ManCollectAnds( p, &iObj, 1, vTemp, Gia_ObjLutFanins2(p, iObj) );
    Vec_IntForEachEntry( vTemp, iTemp, i )
        if ( !Vec_BitEntry(vMarksAnd, iTemp) )
            Vec_IntWriteEntry( vTemp, k++, iTemp );
    Vec_IntShrink( vTemp, k );
    return k;
}
void Spl_ManAddNode( Spl_Man_t * p, int iPivot, Vec_Int_t * vCands )
{
    int i, iObj;
    Vec_IntPush( p->vNodes, iPivot );
    Vec_BitWriteEntry( p->vMarksNo, iPivot, 1 );
    Vec_IntAppend( p->vAnds, vCands );
    Vec_IntForEachEntry( vCands, iObj, i )
        Vec_BitWriteEntry( p->vMarksAnd, iObj, 1 );
}
int Spl_ManComputeOne( Spl_Man_t * p, int iPivot )
{
    int CountAdd, iObj, i;
    assert( Gia_ObjIsLut2(p->pGia, iPivot) );
//Gia_ManPrintCone2( p->pGia, Gia_ManObj(p->pGia, iPivot) );
    // assume it was previously filled in
    Vec_IntForEachEntry( p->vNodes, iObj, i )
        Vec_BitWriteEntry( p->vMarksNo, iObj, 0 );
    Vec_IntForEachEntry( p->vAnds, iObj, i )
        Vec_BitWriteEntry( p->vMarksAnd, iObj, 0 );
    // double check that it is empty
    //Gia_ManForEachLut2( p->pGia, iObj )
    //    assert( !Vec_BitEntry(p->vMarksNo, iObj) );
    //Gia_ManForEachLut2( p->pGia, iObj )
    //    assert( !Vec_BitEntry(p->vMarksAnd, iObj) );
    // clean arrays
    Vec_IntClear( p->vNodes );
    Vec_IntClear( p->vAnds );
    // add root node
    Spl_ManLutMffcSize( p->pGia, iPivot, p->vCands, p->vMarksAnd );
    Spl_ManAddNode( p, iPivot, p->vCands );
    if ( Vec_IntSize(p->vAnds) > p->Limit )
        return 0;
    //printf( "%d ", iPivot );
    // add one node at a time
    while ( (iObj = Spl_ManFindOne(p)) )
    {
        assert( Gia_ObjIsLut2(p->pGia, iObj) );
        assert( !Vec_BitEntry(p->vMarksNo, iObj) );
        CountAdd = Spl_ManLutMffcSize( p->pGia, iObj, p->vCands, p->vMarksAnd );
        if ( Vec_IntSize(p->vAnds) + CountAdd > p->Limit )
            break;
        Spl_ManAddNode( p, iObj, p->vCands );
        //printf( "+%d ", iObj );
    }
    //printf( "\n" );
    Vec_IntSort( p->vNodes, 0 );
    Vec_IntSort( p->vAnds, 0 );
    Spl_ManWinFindLeavesRoots( p );
    Vec_IntSort( p->vLeaves, 0 );
    Vec_IntSort( p->vRoots, 0 );
    return 1;
}

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

  Synopsis    [External procedures.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ManComputeOneWin( Gia_Man_t * pGia, int iPivot, Vec_Int_t ** pvRoots, Vec_Int_t ** pvNodes, Vec_Int_t ** pvLeaves, Vec_Int_t ** pvAnds )
{
    Spl_Man_t * p = (Spl_Man_t *)pGia->pSatlutWinman;
    assert( p != NULL );
    if ( iPivot == -1 )
    {
        Spl_ManStop( p );
        pGia->pSatlutWinman = NULL;
        return 0;
    }
    if ( !Spl_ManComputeOne( p, iPivot ) )
    {
        *pvRoots  = NULL;
        *pvNodes  = NULL;
        *pvLeaves = NULL;
        *pvAnds   = NULL;
        return 0;
    }
    *pvRoots  = p->vRoots;
    *pvNodes  = p->vNodes;
    *pvLeaves = p->vLeaves;
    *pvAnds   = p->vAnds;
    // Vec_IntPrint( p->vNodes );
    return Vec_IntSize(p->vAnds);
}
void Gia_ManComputeOneWinStart( Gia_Man_t * pGia, int nAnds, int fReverse )
{
    assert( pGia->pSatlutWinman == NULL );
    pGia->pSatlutWinman = Spl_ManAlloc( pGia, nAnds, fReverse );
}

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

  Synopsis    [Testing procedure.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Spl_ManComputeOneTest( Gia_Man_t * pGia )
{
    int iLut, Count;
    Gia_ManComputeOneWinStart( pGia, 64, 0 );
    Gia_ManForEachLut2( pGia, iLut )
    {
        Vec_Int_t * vRoots, * vNodes, * vLeaves, * vAnds;
        Count = Gia_ManComputeOneWin( pGia, iLut, &vRoots, &vNodes, &vLeaves, &vAnds );
        printf( "Obj = %6d : Leaf = %2d.  Node = %2d.  Root = %2d.    AND = %3d.\n", 
            iLut, Vec_IntSize(vLeaves), Vec_IntSize(vNodes), Vec_IntSize(vRoots), Count ); 
    }
    Gia_ManComputeOneWin( pGia, -1, NULL, NULL, NULL, NULL );
}

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


ABC_NAMESPACE_IMPL_END