giaSatLE.c

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

  FileName    [giaSatLE.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [Mapping with edges.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "gia.h"
#include "misc/extra/extra.h"
#include "misc/tim/tim.h"
#include "sat/bsat/satStore.h"

ABC_NAMESPACE_IMPL_START


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

static inline int   Sle_CutSize( int * pCut )          { return pCut[0] & 0xF;  }  //  4 bits
static inline int   Sle_CutSign( int * pCut )          { return ((unsigned)pCut[0]) >> 4;   }  // 28 bits
static inline int   Sle_CutSetSizeSign( int s, int S ) { return (S << 4) | s;   }
static inline int * Sle_CutLeaves( int * pCut )        { return pCut + 1;       } 

static inline int   Sle_CutIsUsed( int * pCut )        { return pCut[1] != 0;   }
static inline void  Sle_CutSetUnused( int * pCut )     { pCut[1] = 0;           }

static inline int   Sle_ListCutNum( int * pList )      { return pList[0];       }

#define Sle_ForEachCut( pList, pCut, i )   for ( i = 0, pCut = pList + 1; i <  pList[0]; i++, pCut += Sle_CutSize(pCut) + 1 ) // cuts with unit-cut
#define Sle_ForEachCut1( pList, pCut, i )  for ( i = 0, pCut = pList + 1; i <= pList[0]; i++, pCut += Sle_CutSize(pCut) + 1 ) // only non-unit cuts

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

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

  Synopsis    [Cut computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Sle_CutMergeOrder( int * pCut0, int * pCut1, int * pCut, int nLutSize )
{ 
    int nSize0   = Sle_CutSize(pCut0);
    int nSize1   = Sle_CutSize(pCut1);
    int i, * pC0 = Sle_CutLeaves(pCut0);
    int k, * pC1 = Sle_CutLeaves(pCut1);
    int c, * pC  = Sle_CutLeaves(pCut);
    // the case of the largest cut sizes
    if ( nSize0 == nLutSize && nSize1 == nLutSize )
    {
        for ( i = 0; i < nSize0; i++ )
        {
            if ( pC0[i] != pC1[i] )  return 0;
            pC[i] = pC0[i];
        }
        pCut[0] = Sle_CutSetSizeSign( nLutSize, Sle_CutSign(pCut0) | Sle_CutSign(pCut1) );
        return 1;
    }
    // compare two cuts with different numbers
    i = k = c = 0;
    if ( nSize0 == 0 ) goto FlushCut1;
    if ( nSize1 == 0 ) goto FlushCut0;
    while ( 1 )
    {
        if ( c == nLutSize ) return 0;
        if ( pC0[i] < pC1[k] )
        {
            pC[c++] = pC0[i++];
            if ( i >= nSize0 ) goto FlushCut1;
        }
        else if ( pC0[i] > pC1[k] )
        {
            pC[c++] = pC1[k++];
            if ( k >= nSize1 ) goto FlushCut0;
        }
        else
        {
            pC[c++] = pC0[i++]; k++;
            if ( i >= nSize0 ) goto FlushCut1;
            if ( k >= nSize1 ) goto FlushCut0;
        }
    }

FlushCut0:
    if ( c + nSize0 > nLutSize + i ) return 0;
    while ( i < nSize0 )
        pC[c++] = pC0[i++];
    pCut[0] = Sle_CutSetSizeSign( c, Sle_CutSign(pCut0) | Sle_CutSign(pCut1) );
    return 1;

FlushCut1:
    if ( c + nSize1 > nLutSize + k ) return 0;
    while ( k < nSize1 )
        pC[c++] = pC1[k++];
    pCut[0] = Sle_CutSetSizeSign( c, Sle_CutSign(pCut0) | Sle_CutSign(pCut1) );
    return 1;
}
static inline int Sle_SetCutIsContainedOrder( int * pBase, int * pCut ) // check if pCut is contained in pBase
{
    int i, nSizeB = Sle_CutSize(pBase);
    int k, nSizeC = Sle_CutSize(pCut);
    int * pLeaveB = Sle_CutLeaves(pBase);
    int * pLeaveC = Sle_CutLeaves(pCut);
    if ( nSizeB == nSizeC )
    {
        for ( i = 0; i < nSizeB; i++ )
            if ( pLeaveB[i] != pLeaveC[i] )
                return 0;
        return 1;
    }
    assert( nSizeB > nSizeC ); 
    if ( nSizeC == 0 )
        return 1;
    for ( i = k = 0; i < nSizeB; i++ )
    {
        if ( pLeaveB[i] > pLeaveC[k] )
            return 0;
        if ( pLeaveB[i] == pLeaveC[k] )
        {
            if ( ++k == nSizeC )
                return 1;
        }
    }
    return 0;
}
static inline int Sle_CutCountBits( unsigned i )
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F);
    return (i*(0x01010101))>>24;
}
static inline int Sle_SetLastCutIsContained( Vec_Int_t * vTemp, int * pBase )
{
    int i, * pCut, * pList = Vec_IntArray(vTemp);
    Sle_ForEachCut( pList, pCut, i )
        if ( Sle_CutIsUsed(pCut) && Sle_CutSize(pCut) <= Sle_CutSize(pBase) && (Sle_CutSign(pCut) & Sle_CutSign(pBase)) == Sle_CutSign(pCut) && Sle_SetCutIsContainedOrder(pBase, pCut) )
            return 1;
    return 0;
}
static inline void Sle_SetAddCut( Vec_Int_t * vTemp, int * pCut )
{
    int i, * pBase, * pList = Vec_IntArray(vTemp);
    Sle_ForEachCut( pList, pBase, i )
        if ( Sle_CutIsUsed(pBase) && Sle_CutSize(pCut) < Sle_CutSize(pBase) && (Sle_CutSign(pCut) & Sle_CutSign(pBase)) == Sle_CutSign(pCut) && Sle_SetCutIsContainedOrder(pBase, pCut) )
            Sle_CutSetUnused( pBase );
    Vec_IntPushArray( vTemp, pCut, Sle_CutSize(pCut)+1 );
    Vec_IntAddToEntry( vTemp, 0, 1 );
}
int Sle_ManCutMerge( Gia_Man_t * p, int iObj, Vec_Int_t * vCuts, Vec_Int_t * vTemp, int nLutSize )
{
    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
    int * pList0 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId0(pObj, iObj)) );
    int * pList1 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId1(pObj, iObj)) );
    int * pCut0, * pCut1, i, k, Cut[8], nCuts = 0;
    Vec_IntFill( vTemp, 1, 0 );
    Sle_ForEachCut1( pList0, pCut0, i )
    Sle_ForEachCut1( pList1, pCut1, k )
    {
        if ( Sle_CutSize(pCut0) + Sle_CutSize(pCut1) > nLutSize && Sle_CutCountBits(Sle_CutSign(pCut0) | Sle_CutSign(pCut1)) > nLutSize )
            continue;
        if ( !Sle_CutMergeOrder(pCut0, pCut1, Cut, nLutSize) )
            continue;
        if ( Sle_SetLastCutIsContained(vTemp, Cut) )
            continue;
        Sle_SetAddCut( vTemp, Cut );
    }
    // reload
    Vec_IntWriteEntry( vCuts, iObj, Vec_IntSize(vCuts) );
    Vec_IntPush( vCuts, -1 );
    pList0 = Vec_IntArray(vTemp);
    Sle_ForEachCut( pList0, pCut0, i )
    {
        if ( !Sle_CutIsUsed(pCut0) )
            continue;
        Vec_IntPushArray( vCuts, pCut0, Sle_CutSize(pCut0)+1 );
        nCuts++;
    }
    // add unit cut
    Vec_IntPush( vCuts, Sle_CutSetSizeSign(1, 1<<(iObj % 28)) );
    Vec_IntPush( vCuts, iObj );
    Vec_IntWriteEntry( vCuts, Vec_IntEntry(vCuts, iObj), nCuts );
    return nCuts;
}
Vec_Int_t * Sle_ManComputeCuts( Gia_Man_t * p, int nLutSize, int fVerbose )
{
    int i, iObj, nCuts = 0;
    Vec_Int_t * vTemp = Vec_IntAlloc( 1000 );
    Vec_Int_t * vCuts = Vec_IntAlloc( 30 * Gia_ManAndNum(p) );
    assert( nLutSize <= 6 );
    Vec_IntFill( vCuts, Gia_ManObjNum(p), 0 );
    Gia_ManForEachCiId( p, iObj, i )
    {
        Vec_IntWriteEntry( vCuts, iObj, Vec_IntSize(vCuts) );
        Vec_IntPush( vCuts, 0 );
        Vec_IntPush( vCuts, Sle_CutSetSizeSign(1, 1<<(iObj % 28)) );
        Vec_IntPush( vCuts, iObj );
    }
    Gia_ManForEachAndId( p, iObj )
        nCuts += Sle_ManCutMerge( p, iObj, vCuts, vTemp, nLutSize );
    if ( fVerbose )
        printf( "Nodes = %d.  Cuts = %d.  Cuts/Node = %.2f.  Ints/Node = %.2f.  Mem = %.2f MB.\n", 
            Gia_ManAndNum(p), nCuts, 1.0*nCuts/Gia_ManAndNum(p), 
            1.0*(Vec_IntSize(vCuts)-Gia_ManObjNum(p))/Gia_ManAndNum(p), 
            1.0*Vec_IntMemory(vCuts) / (1<<20) );
    Vec_IntFree( vTemp );
    return vCuts;
}

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

  Synopsis    [Cut delay computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sle_ManComputeDelayCut( Gia_Man_t * p, int * pCut, Vec_Int_t * vTime )
{
    int nSize   = Sle_CutSize(pCut);
    int k, * pC = Sle_CutLeaves(pCut);
    int DelayMax = 0;
    for ( k = 0; k < nSize; k++ )
        DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(vTime, pC[k]) );
    return DelayMax + 1;
}
int Sle_ManComputeDelayOne( Gia_Man_t * p, int iObj, Vec_Int_t * vCuts, Vec_Int_t * vTime )
{
    int i, * pCut, Delay, DelayMin = ABC_INFINITY;
    int * pList = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, iObj) );
    Sle_ForEachCut( pList, pCut, i )
    {
        Delay = Sle_ManComputeDelayCut( p, pCut, vTime );
        DelayMin = Abc_MinInt( DelayMin, Delay );
    }
    Vec_IntWriteEntry( vTime, iObj, DelayMin );
    return DelayMin;
}
int Sle_ManComputeDelay( Gia_Man_t * p, Vec_Int_t * vCuts )
{
    int iObj, Delay, DelayMax = 0;
    Vec_Int_t * vTime = Vec_IntStart( Gia_ManObjNum(p) );
    Gia_ManForEachAndId( p, iObj )
    {
        Delay = Sle_ManComputeDelayOne( p, iObj, vCuts, vTime );
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    Vec_IntFree( vTime );
    //printf( "Delay = %d.\n", DelayMax );
    return DelayMax;
}

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

  Synopsis    [Cut printing.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sle_ManPrintCut( int * pCut )
{
    int nSize   = Sle_CutSize(pCut);
    int k, * pC = Sle_CutLeaves(pCut);
    printf( "{" );
    for ( k = 0; k < nSize; k++ )
        printf( " %d", pC[k] );
    printf( " }\n" );
}
void Sle_ManPrintCuts( Gia_Man_t * p, Vec_Int_t * vCuts, int iObj )
{
    int i, * pCut;
    int * pList = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, iObj) );
    printf( "Obj %3d\n", iObj );
    Sle_ForEachCut( pList, pCut, i )
        Sle_ManPrintCut( pCut );
    printf( "\n" );
}
void Sle_ManPrintCutsAll( Gia_Man_t * p, Vec_Int_t * vCuts )
{
    int iObj;
    Gia_ManForEachAndId( p, iObj )
        Sle_ManPrintCuts( p, vCuts, iObj );
}
void Sle_ManComputeCutsTest( Gia_Man_t * p )
{
    Vec_Int_t * vCuts = Sle_ManComputeCuts( p, 4, 1 );
    //Sle_ManPrintCutsAll( p, vCuts );
    Vec_IntFree( vCuts );
}



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

  Synopsis    [Derive mask representing internal nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Bit_t * Sle_ManInternalNodeMask( Gia_Man_t * pGia )
{
    int iObj;
    Vec_Bit_t * vMask = Vec_BitStart( Gia_ManObjNum(pGia) );  
    Gia_ManForEachAndId( pGia, iObj )
        Vec_BitWriteEntry( vMask, iObj, 1 );
    return vMask;
}

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

  Synopsis    [Check if the cut contains only primary inputs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sle_ManCutHasPisOnly( int * pCut, Vec_Bit_t * vMask )
{
    int k, * pC = Sle_CutLeaves(pCut);
    for ( k = 0; k < Sle_CutSize(pCut); k++ )
        if ( Vec_BitEntry(vMask, pC[k]) ) // internal node
            return 0;
    return 1;
}

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

  Synopsis    [Derive cut fanins of each node.]

  Description [These are nodes that are fanins of some cut of this node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sle_ManCollectCutFaninsOne( Gia_Man_t * pGia, int iObj, Vec_Int_t * vCuts, Vec_Bit_t * vMask, Vec_Int_t * vCutFanins, Vec_Bit_t * vMap )
{
    int i, iFanin, * pCut, * pList = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, iObj) );
    Sle_ForEachCut( pList, pCut, i )
    {
        int nSize   = Sle_CutSize(pCut);
        int k, * pC = Sle_CutLeaves(pCut);
        assert( nSize > 1 );
        for ( k = 0; k < nSize; k++ )
            if ( Vec_BitEntry(vMask, pC[k]) && !Vec_BitEntry(vMap, pC[k]) )
            {
                Vec_BitWriteEntry( vMap, pC[k], 1 );
                Vec_IntPush( vCutFanins, pC[k] );
            }
    }
    Vec_IntForEachEntry( vCutFanins, iFanin, i )
        Vec_BitWriteEntry( vMap, iFanin, 0 );
}
Vec_Wec_t * Sle_ManCollectCutFanins( Gia_Man_t * pGia, Vec_Int_t * vCuts, Vec_Bit_t * vMask )
{
    int iObj;
    Vec_Bit_t * vMap = Vec_BitStart( Gia_ManObjNum(pGia) );
    Vec_Wec_t * vCutFanins = Vec_WecStart( Gia_ManObjNum(pGia) );
    Gia_ManForEachAndId( pGia, iObj )
        Sle_ManCollectCutFaninsOne( pGia, iObj, vCuts, vMask, Vec_WecEntry(vCutFanins, iObj), vMap );
    Vec_BitFree( vMap );
    return vCutFanins;
}


typedef struct Sle_Man_t_ Sle_Man_t;
struct Sle_Man_t_
{
    // user's data
    Gia_Man_t *    pGia;         // user's manager (with mapping and edges)
    int            nLevels;      // total number of levels
    int            fVerbose;     // verbose flag
    int            nSatCalls;    // the number of SAT calls
    // SAT variables
    int            nNodeVars;    // node variables (Gia_ManAndNum(pGia))
    int            nCutVars;     // cut variables (total number of non-trivial cuts)
    int            nEdgeVars;    // edge variables (total number of internal edges)
    int            nDelayVars;   // delay variables (nNodeVars * nLevelsMax)
    int            nVarsTotal;   // total number of variables
    // SAT clauses
    int            nCutClas;     // cut clauses
    int            nEdgeClas;    // edge clauses
    int            nEdgeClas2;   // edge clauses exclusivity
    int            nDelayClas;   // delay clauses
    // internal data
    sat_solver *   pSat;         // SAT solver
    Vec_Bit_t *    vMask;        // internal node mask
    Vec_Int_t *    vCuts;        // cuts for each node
    Vec_Wec_t *    vCutFanins;   // internal cut fanins of each node
    Vec_Wec_t *    vFanoutEdges; // internal cut fanins of each node
    Vec_Wec_t *    vEdgeCuts;    // cuts of each edge for one node
    Vec_Int_t *    vObjMap;      // temporary object map
    Vec_Int_t *    vCutFirst;    // first cut of each node
    Vec_Int_t *    vEdgeFirst;   // first edge of each node
    Vec_Int_t *    vDelayFirst;  // first edge of each node
    Vec_Int_t *    vPolars;      // initial 
    Vec_Int_t *    vLits;        // literals 
    // statistics
    abctime        timeStart;
};

static inline int * Sle_ManList( Sle_Man_t * p, int i ) { return Vec_IntEntryP(p->vCuts, Vec_IntEntry(p->vCuts, i)); }

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sle_Man_t * Sle_ManAlloc( Gia_Man_t * pGia, int nLevels, int fVerbose )
{
    Sle_Man_t * p   = ABC_CALLOC( Sle_Man_t, 1 );
    p->pGia         = pGia;
    p->nLevels      = nLevels;
    p->fVerbose     = fVerbose;
    p->vMask        = Sle_ManInternalNodeMask( pGia );
    p->vCuts        = Sle_ManComputeCuts( pGia, 4, fVerbose );
    p->vCutFanins   = Sle_ManCollectCutFanins( pGia, p->vCuts, p->vMask );
    p->vFanoutEdges = Vec_WecStart( Gia_ManObjNum(pGia) );
    p->vEdgeCuts    = Vec_WecAlloc( 100 );
    p->vObjMap      = Vec_IntStartFull( Gia_ManObjNum(pGia) );
    p->vCutFirst    = Vec_IntStartFull( Gia_ManObjNum(pGia) );
    p->vEdgeFirst   = Vec_IntStartFull( Gia_ManObjNum(pGia) );
    p->vDelayFirst  = Vec_IntStartFull( Gia_ManObjNum(pGia) );
    p->vPolars      = Vec_IntAlloc( 100 );
    p->vLits        = Vec_IntAlloc( 100 );
    p->nLevels      = Sle_ManComputeDelay( pGia, p->vCuts );
    return p;
}
void Sle_ManStop( Sle_Man_t * p )
{
    sat_solver_delete( p->pSat );
    Vec_BitFree( p->vMask );
    Vec_IntFree( p->vCuts );
    Vec_WecFree( p->vCutFanins );
    Vec_WecFree( p->vFanoutEdges );
    Vec_WecFree( p->vEdgeCuts );
    Vec_IntFree( p->vObjMap );
    Vec_IntFree( p->vCutFirst );
    Vec_IntFree( p->vEdgeFirst );
    Vec_IntFree( p->vDelayFirst );
    Vec_IntFree( p->vPolars );
    Vec_IntFree( p->vLits );
    ABC_FREE( p );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sle_ManMarkupVariables( Sle_Man_t * p )
{
    int iObj, Counter = Gia_ManObjNum(p->pGia);
    // node variables
    p->nNodeVars = Counter;
    // cut variables
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        Vec_IntWriteEntry( p->vCutFirst, iObj, Counter );
        Counter += Sle_ListCutNum( Sle_ManList(p, iObj) );
    }
    p->nCutVars = Counter - p->nNodeVars;
    // edge variables
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        Vec_IntWriteEntry( p->vEdgeFirst, iObj, Counter );
        Counter += Vec_IntSize( Vec_WecEntry(p->vCutFanins, iObj) );
    }
    p->nEdgeVars = Counter - p->nCutVars - p->nNodeVars;
    // delay variables
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        Vec_IntWriteEntry( p->vDelayFirst, iObj, Counter );
        Counter += p->nLevels;
    }
    p->nDelayVars = Counter - p->nEdgeVars - p->nCutVars - p->nNodeVars;
    p->nVarsTotal = Counter;
}


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

  Synopsis    [Derive initial variable assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
// returns 1 if Cut can represent LUT (Cut is equal or is contained in LUT)
static inline int Sle_ManCheckContained( int * pCutLeaves, int nCutLeaves, int * pLutFanins, int nLutFanins )
{
    int i, k;
    if ( nCutLeaves > nLutFanins )
        return 0;
    for ( i = 0; i < nCutLeaves; i++ )
    {
        for ( k = 0; k < nLutFanins; k++ )
            if ( pCutLeaves[i] == pLutFanins[k] )
                break;
        if ( k == nLutFanins ) // not found
            return 0;
    }
    return 1;
}
void Sle_ManDeriveInit( Sle_Man_t * p )
{
    Vec_Int_t * vEdges;
    int i, iObj, iFanin, iEdge;
    if ( !Gia_ManHasMapping(p->pGia) )
        return;
    // derive initial state
    Vec_IntClear( p->vPolars );
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        int nFanins, * pFanins, * pCut, * pList, iFound = -1;
        if ( !Gia_ObjIsLut(p->pGia, iObj) )
            continue;
        Vec_IntPush( p->vPolars, iObj ); // node var
        nFanins = Gia_ObjLutSize( p->pGia, iObj );
        pFanins = Gia_ObjLutFanins( p->pGia, iObj );
        // find cut
        pList = Sle_ManList( p, iObj );
        Sle_ForEachCut( pList, pCut, i )
            if ( Sle_ManCheckContained( Sle_CutLeaves(pCut), Sle_CutSize(pCut), pFanins, nFanins ) )
            {
                iFound = i;
                break;
            }
        if ( iFound == -1 )
        {
            printf( "Cannot find the following cut at node %d: {", iObj );
            for ( i = 0; i < nFanins; i++ )
                printf( " %d", pFanins[i] );
            printf( " }\n" );
            Sle_ManPrintCuts( p->pGia, p->vCuts, iObj );
            fflush( stdout );
        }
        assert( iFound >= 0 );
        Vec_IntPush( p->vPolars, Vec_IntEntry(p->vCutFirst, iObj) + iFound ); // cut var
        // check if the cut contains only primary inputs - if so, its delay is equal to 1
        if ( Sle_ManCutHasPisOnly(pCut, p->vMask) )
            Vec_IntPush( p->vPolars, Vec_IntEntry(p->vDelayFirst, iObj) ); // delay var
    }
    Vec_IntSort( p->vPolars, 0 );
    // find zero-delay edges
    if ( !p->pGia->vEdge1 )
        return;
    vEdges = Gia_ManEdgeToArray( p->pGia );
    Vec_IntForEachEntryDouble( vEdges, iFanin, iObj, i )
    {
        assert( iFanin < iObj );
        assert( Gia_ObjIsLut(p->pGia, iFanin) );
        assert( Gia_ObjIsLut(p->pGia, iObj) );
        assert( Gia_ObjIsAnd(Gia_ManObj(p->pGia, iFanin)) );
        assert( Gia_ObjIsAnd(Gia_ManObj(p->pGia, iObj)) );
        // find edge
        iEdge = Vec_IntFind( Vec_WecEntry(p->vCutFanins, iObj), iFanin );
        if ( iEdge < 0 )
            continue;
        assert( iEdge >= 0 );
        Vec_IntPush( p->vPolars, Vec_IntEntry(p->vEdgeFirst, iObj) + iEdge ); // edge
    }
    Vec_IntFree( vEdges );
}

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

  Synopsis    [Derive CNF.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sle_ManDeriveCnf( Sle_Man_t * p, int nBTLimit, int fDynamic )
{
    int nTimeOut = 0;
    int i, iObj, value;
    Vec_Int_t * vArray;

    // start the SAT solver
    p->pSat = sat_solver_new();
    sat_solver_setnvars( p->pSat, p->nVarsTotal );
    sat_solver_set_resource_limits( p->pSat, nBTLimit, 0, 0, 0 );
    sat_solver_set_runtime_limit( p->pSat, nTimeOut ? nTimeOut * CLOCKS_PER_SEC + Abc_Clock(): 0 );
    sat_solver_set_random( p->pSat, 1 );
    sat_solver_set_polarity( p->pSat, Vec_IntArray(p->vPolars), Vec_IntSize(p->vPolars) );
    //sat_solver_set_var_activity( p->pSat, NULL, p->nVarsTotal );

    // set drivers to be mapped
    Gia_ManForEachCoDriverId( p->pGia, iObj, i )
        if ( Vec_BitEntry(p->vMask, iObj) ) // internal node
        {
            Vec_IntFill( p->vLits, 1, Abc_Var2Lit(iObj, 0) ); // pos lit
            value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
            assert( value );
        }

    // add cover clauses and edge-to-cut clauses
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        int e, iEdge, nEdges = 0, Entry;
        int iCutVar0  = Vec_IntEntry( p->vCutFirst, iObj );
        int iEdgeVar0 = Vec_IntEntry( p->vEdgeFirst, iObj );
        int * pCut, * pList  = Sle_ManList( p, iObj );
        Vec_Int_t * vCutFans = Vec_WecEntry( p->vCutFanins, iObj );
        assert( iCutVar0 > 0 && iEdgeVar0 > 0 );
        // node requires one of the cuts
        Vec_IntFill( p->vLits, 1, Abc_Var2Lit(iObj, 1) ); // neg lit
        for ( i = 0; i < Sle_ListCutNum(pList); i++ )
            Vec_IntPush( p->vLits, Abc_Var2Lit(iCutVar0 + i, 0) );
        value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
        assert( value );
        // cuts are mutually exclusive
        for ( i = 0; i < Sle_ListCutNum(pList); i++ )
            for ( e = i+1; e < Sle_ListCutNum(pList); e++ )
            {
                Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(iCutVar0 + i, 1), Abc_Var2Lit(iCutVar0 + e, 1) );
                value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                assert( value );
            }
        // cut requires fanin nodes
        Vec_WecInit( p->vEdgeCuts, Vec_IntSize(vCutFans) );
        Sle_ForEachCut( pList, pCut, i )
        {
            int nSize   = Sle_CutSize(pCut);
            int k, * pC = Sle_CutLeaves(pCut);
            assert( nSize > 1 );
            for ( k = 0; k < nSize; k++ )
            {
                if ( !Vec_BitEntry(p->vMask, pC[k]) )
                    continue;
                Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(iCutVar0 + i, 1), Abc_Var2Lit(pC[k], 0) );
                value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                assert( value );
                // find the edge ID between pC[k] and iObj
                iEdge = Vec_IntEntry(p->vObjMap, pC[k]);
                if ( iEdge == -1 )
                {
                    Vec_IntWriteEntry( p->vObjMap, pC[k], (iEdge = nEdges++) );
                    Vec_WecPush( p->vFanoutEdges, pC[k], iEdgeVar0 + iEdge );
                }
                Vec_WecPush( p->vEdgeCuts, iEdge, iCutVar0 + i );
                p->nCutClas++;
            }
            // cut requires the node
            Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(iCutVar0 + i, 1), Abc_Var2Lit(iObj, 0) );
            value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
            assert( value );
        }
        assert( nEdges == Vec_IntSize(vCutFans) );

        // edge requires one of the fanout cuts
        Vec_WecForEachLevel( p->vEdgeCuts, vArray, e )
        {
            assert( Vec_IntSize(vArray) > 0 );
            Vec_IntFill( p->vLits, 1, Abc_Var2Lit(iEdgeVar0 + e, 1) ); // neg lit (edge)
            Vec_IntForEachEntry( vArray, Entry, i )
                Vec_IntPush( p->vLits, Abc_Var2Lit(Entry, 0) ); // pos lit (cut)
            value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
            assert( value );
            p->nEdgeClas++;
        }

        // clean object map
        Vec_IntForEachEntry( vCutFans, Entry, i )
            Vec_IntWriteEntry( p->vObjMap, Entry, -1 );
    }

    // mutual exclusivity of edges
    Vec_WecForEachLevel( p->vFanoutEdges, vArray, iObj )
    {
        int j, k, EdgeJ, EdgeK;
        int iEdgeVar0 = Vec_IntEntry( p->vEdgeFirst, iObj );
        Vec_Int_t * vCutFans = Vec_WecEntry( p->vCutFanins, iObj );
        // add fanin edges
        for ( i = 0; i < Vec_IntSize(vCutFans); i++ )
            Vec_IntPush( vArray, iEdgeVar0 + i );
        // generate pairs
        if ( fDynamic )
            continue;
        Vec_IntForEachEntry( vArray, EdgeJ, j )
            Vec_IntForEachEntryStart( vArray, EdgeK, k, j+1 )
            {
                Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(EdgeJ, 1), Abc_Var2Lit(EdgeK, 1) );
                value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                assert( value );
            }
        p->nEdgeClas2 += Vec_IntSize(vArray) * (Vec_IntSize(vArray) - 1) / 2;
    }

    // add delay clauses
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        int e, iFanin;
        int iEdgeVar0 = Vec_IntEntry( p->vEdgeFirst, iObj );
        int iDelayVar0 = Vec_IntEntry( p->vDelayFirst, iObj );
        Vec_Int_t * vCutFans = Vec_WecEntry( p->vCutFanins, iObj );
        // check if the node has cuts containing only primary inputs
        int * pCut, * pList = Sle_ManList( p, iObj );
        Sle_ForEachCut( pList, pCut, i )
            if ( Sle_ManCutHasPisOnly(pCut, p->vMask) )
            {
                Vec_IntFill( p->vLits, 1, Abc_Var2Lit(iDelayVar0, 0) ); // pos lit
//                Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(iObj, 1), Abc_Var2Lit(iDelayVar0, 0) );
                value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                assert( value );
                break;
            }
//        if ( i < Sle_ListCutNum(pList) )
//            continue;
        // create delay requirements for each cut fanin of this node
        Vec_IntForEachEntry( vCutFans, iFanin, e )
        {
            int d, iDelayVarIn = Vec_IntEntry( p->vDelayFirst, iFanin );
            for ( d = 0; d < p->nLevels; d++ )
            {
                Vec_IntClear( p->vLits );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iObj, 1) );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iFanin, 1) );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iDelayVarIn + d, 1) );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iEdgeVar0 + e, 0) );
                if ( d < p->nLevels-1 )
                    Vec_IntPush( p->vLits, Abc_Var2Lit(iDelayVar0 + d+1, 0) );
                value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                assert( value );

                Vec_IntClear( p->vLits );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iObj, 1) );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iFanin, 1) );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iDelayVarIn + d, 1) );
                if ( d < p->nLevels-1 )
                    Vec_IntPush( p->vLits, Abc_Var2Lit(iEdgeVar0 + e, 1) );
                Vec_IntPush( p->vLits, Abc_Var2Lit(iDelayVar0 + d, 0) );
                value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                assert( value );
            }
            p->nDelayClas += 2*p->nLevels;
        }
    }
}

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

  Synopsis    [Add edge compatibility constraints.]

  Description [Returns 1 if constraints have been added.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sle_ManAddEdgeConstraints( Sle_Man_t * p, int nEdges )
{
    Vec_Int_t * vArray;
    Vec_Int_t * vTemp = Vec_IntAlloc( 100 );
    int value, iObj, nAdded = 0;
    assert( nEdges == 1 || nEdges == 2 );
    Vec_WecForEachLevel( p->vFanoutEdges, vArray, iObj )
    {
        int j, k, EdgeJ, EdgeK;
        // check if they are incompatible
        Vec_IntClear( vTemp );
        Vec_IntForEachEntry( vArray, EdgeJ, j )
            if ( sat_solver_var_value(p->pSat, EdgeJ) )
                Vec_IntPush( vTemp, EdgeJ );
        if ( Vec_IntSize(vTemp) <= nEdges )
            continue;
        nAdded++;
        if ( nEdges == 1 )
        {
            // generate pairs
            Vec_IntForEachEntry( vTemp, EdgeJ, j )
                Vec_IntForEachEntryStart( vTemp, EdgeK, k, j+1 )
                {
                    Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(EdgeJ, 1), Abc_Var2Lit(EdgeK, 1) );
                    value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                    assert( value );
                }
            p->nEdgeClas2 += Vec_IntSize(vTemp) * (Vec_IntSize(vTemp) - 1) / 2;
        }
        else if ( nEdges == 2 )
        {
            int m, EdgeM;
            // generate triples
            Vec_IntForEachEntry( vTemp, EdgeJ, j )
                Vec_IntForEachEntryStart( vTemp, EdgeK, k, j+1 )
                    Vec_IntForEachEntryStart( vTemp, EdgeM, m, k+1 )
                    {
                        Vec_IntFillTwo( p->vLits, 2, Abc_Var2Lit(EdgeJ, 1), Abc_Var2Lit(EdgeK, 1) );
                        Vec_IntPush( p->vLits, Abc_Var2Lit(EdgeM, 1) );
                        value = sat_solver_addclause( p->pSat, Vec_IntArray(p->vLits), Vec_IntLimit(p->vLits)  );
                        assert( value );
                    }
            p->nEdgeClas2 += Vec_IntSize(vTemp) * (Vec_IntSize(vTemp) - 1) * (Vec_IntSize(vTemp) - 2) / 6;
        }
        else assert( 0 );
    }
    Vec_IntFree( vTemp );
    //printf( "Added clauses to %d nodes.\n", nAdded );
    return nAdded;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sle_ManDeriveResult( Sle_Man_t * p, Vec_Int_t * vEdge2, Vec_Int_t * vMapping )
{
    Vec_Int_t * vMapTemp;
    int iObj;
    // create mapping
    Vec_IntFill( vMapping, Gia_ManObjNum(p->pGia), 0 );
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        int i, iCut, iCutVar0 = Vec_IntEntry( p->vCutFirst, iObj );
        int * pCut, * pCutThis = NULL, * pList = Sle_ManList( p, iObj );
        if ( !sat_solver_var_value(p->pSat, iObj) )
            continue;
        Sle_ForEachCut( pList, pCut, iCut )
            if ( sat_solver_var_value(p->pSat, iCutVar0 + iCut) )
            {
                assert( pCutThis == NULL );
                pCutThis = pCut;
            }
        assert( pCutThis != NULL );
        Vec_IntWriteEntry( vMapping, iObj, Vec_IntSize(vMapping) );
        Vec_IntPush( vMapping, Sle_CutSize(pCutThis) );
        for ( i = 0; i < Sle_CutSize(pCutThis); i++ )
            Vec_IntPush( vMapping, Sle_CutLeaves(pCutThis)[i] );
        Vec_IntPush( vMapping, iObj );
    }
    vMapTemp = p->pGia->vMapping;
    p->pGia->vMapping = vMapping;
    // collect edges
    Vec_IntClear( vEdge2 );
    Gia_ManForEachAndId( p->pGia, iObj )
    {
        int i, iFanin, iEdgeVar0 = Vec_IntEntry( p->vEdgeFirst, iObj );
        Vec_Int_t * vCutFans = Vec_WecEntry( p->vCutFanins, iObj );
        //int * pCut, * pList  = Sle_ManList( p, iObj );
        // int iCutVar0  = Vec_IntEntry( p->vCutFirst, iObj );
        if ( !sat_solver_var_value(p->pSat, iObj) )
            continue;
        //for ( i = 0; i < Sle_ListCutNum(pList); i++ )
        //    printf( "%d", sat_solver_var_value(p->pSat, iCutVar0 + i) );
        //printf( "\n" );
        Vec_IntForEachEntry( vCutFans, iFanin, i )
            if ( sat_solver_var_value(p->pSat, iFanin) && sat_solver_var_value(p->pSat, iEdgeVar0 + i) )
            {
                // verify edge
                int * pFanins = Gia_ObjLutFanins( p->pGia, iObj );
                int k, nFanins = Gia_ObjLutSize( p->pGia, iObj );
                for ( k = 0; k < nFanins; k++ )
                {
                    //printf( "%d ", pFanins[k] );
                    if ( pFanins[k] == iFanin )
                        break;
                }
                //printf( "\n" );
                if ( k == nFanins )
//                    printf( "Cannot find LUT with input %d at node %d.\n", iFanin, iObj );
                    continue;
                Vec_IntPushTwo( vEdge2, iFanin, iObj );
            }
    }
    p->pGia->vMapping = vMapTemp;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sle_ManExplore( Gia_Man_t * pGia, int nBTLimit, int DelayInit, int fDynamic, int fTwoEdges, int fVerbose )
{
    int fVeryVerbose = 0;
    abctime clk = Abc_Clock();
    Vec_Int_t * vEdges2  = Vec_IntAlloc(1000);
    Vec_Int_t * vMapping = Vec_IntAlloc(1000);
    int i, iLut, nConfs, status, Delay, iFirstVar;
    int DelayStart = (DelayInit || !Gia_ManHasMapping(pGia)) ? DelayInit : Gia_ManLutLevel(pGia, NULL);
    Sle_Man_t * p = Sle_ManAlloc( pGia, DelayStart, fVerbose );
    if ( fVerbose )
        printf( "Running solver with %d conflicts, %d initial delay, and %d edges. Dynamic constraints = %s.\n", nBTLimit, DelayInit, 1+fTwoEdges, fDynamic?"yes":"no" );
    Sle_ManMarkupVariables( p );
    if ( fVerbose )
        printf( "Vars:  Total = %d.  Node = %d. Cut = %d. Edge = %d. Delay = %d.\n", 
            p->nVarsTotal, p->nNodeVars, p->nCutVars, p->nEdgeVars, p->nDelayVars );
    Sle_ManDeriveInit( p );
    Sle_ManDeriveCnf( p, nBTLimit, fDynamic || fTwoEdges );
    if ( fVerbose )
        printf( "Clas:  Total = %d.  Cut = %d. Edge = %d. EdgeEx = %d. Delay = %d.\n", 
            sat_solver_nclauses(p->pSat), p->nCutClas, p->nEdgeClas, p->nEdgeClas2, p->nDelayClas );
    //Sat_SolverWriteDimacs( p->pSat, "temp.cnf", NULL, NULL, 0 );
    for ( Delay = p->nLevels; Delay >= 0; Delay-- )
    {
        // we constrain COs, although it would be fine to constrain only POs
        if ( Delay < p->nLevels )
        {
            Gia_ManForEachCoDriverId( p->pGia, iLut, i )
                if ( Vec_BitEntry(p->vMask, iLut) ) // internal node
                {
                    iFirstVar = Vec_IntEntry( p->vDelayFirst, iLut );
                    if ( !sat_solver_push(p->pSat, Abc_Var2Lit(iFirstVar + Delay, 1)) )
                        break;
                }
            if ( i < Gia_ManCoNum(p->pGia) )
            {
                if ( fVerbose )
                {
                    printf( "Proved UNSAT for delay %d.  ", Delay );
                    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
                }
                break;
            }
        }
        // solve with assumptions
        //clk = Abc_Clock();
        nConfs = sat_solver_nconflicts( p->pSat );
        while ( 1 )
        {
            p->nSatCalls++;
            status = sat_solver_solve_internal( p->pSat );
            if ( status != l_True )
                break;
            if ( !Sle_ManAddEdgeConstraints(p, 1+fTwoEdges) )
                break;
        }
        nConfs = sat_solver_nconflicts( p->pSat ) - nConfs;
        if ( status == l_True )
        {
            if ( fVerbose )
            {
                int nNodes = 0, nEdges = 0;
                for ( i = 0; i < p->nNodeVars; i++ )
                    nNodes += sat_solver_var_value(p->pSat, i);
                for ( i = 0; i < p->nEdgeVars; i++ )
                    nEdges += sat_solver_var_value(p->pSat, p->nNodeVars + p->nCutVars + i);
                printf( "Solution with delay %2d, node count %5d, and edge count %5d exists. Conf = %8d.  ", Delay, nNodes, nEdges, nConfs );
                Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
            }
            // save the result
            Sle_ManDeriveResult( p, vEdges2, vMapping );
            if ( fVeryVerbose )
            {
                printf( "Nodes:  " );
                for ( i = 0; i < p->nNodeVars; i++ )
                    if ( sat_solver_var_value(p->pSat, i) )
                        printf( "%d ", i );
                printf( "\n" );
                printf( "\n" );

                Vec_IntPrint( p->vCutFirst );
                printf( "Cuts:   " );
                for ( i = 0; i < p->nCutVars; i++ )
                    if ( sat_solver_var_value(p->pSat, p->nNodeVars + i) )
                        printf( "%d ", p->nNodeVars + i );
                printf( "\n" );
                printf( "\n" );

                Vec_IntPrint( p->vEdgeFirst );
                printf( "Edges:  " );
                for ( i = 0; i < p->nEdgeVars; i++ )
                    if ( sat_solver_var_value(p->pSat, p->nNodeVars + p->nCutVars + i) )
                        printf( "%d ", p->nNodeVars + p->nCutVars + i );
                printf( "\n" );
                printf( "\n" );

                Vec_IntPrint( p->vDelayFirst );
                printf( "Delays: " );
                for ( i = 0; i < p->nDelayVars; i++ )
                    if ( sat_solver_var_value(p->pSat, p->nNodeVars + p->nCutVars + p->nEdgeVars + i) )
                        printf( "%d ", p->nNodeVars + p->nCutVars + p->nEdgeVars + i );
                printf( "\n" );
                printf( "\n" );
            }
        }
        else
        {
            if ( fVerbose )
            {
                if ( status == l_False )
                    printf( "Proved UNSAT for delay %d. Conf = %8d.  ", Delay, nConfs );
                else
                    printf( "Resource limit reached for delay %d. Conf = %8d.  ", Delay, nConfs );
                Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
            }
            break;
        }
    }
    if ( fVerbose )
        printf( "Clas:  Total = %d.  Cut = %d. Edge = %d. EdgeEx = %d. Delay = %d.  Calls = %d.\n", 
            sat_solver_nclauses(p->pSat), p->nCutClas, p->nEdgeClas, p->nEdgeClas2, p->nDelayClas, p->nSatCalls );
    if ( Vec_IntSize(vMapping) > 0 )
    {
        Gia_ManEdgeFromArray( p->pGia, vEdges2 );
        Vec_IntFree( vEdges2 );
        Vec_IntFreeP( &p->pGia->vMapping );
        p->pGia->vMapping = vMapping;
    }
    else
    {
        Vec_IntFree( vEdges2 );
        Vec_IntFree( vMapping );
    }
    Vec_IntFreeP( &p->pGia->vPacking );
    Sle_ManStop( p );
}

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


ABC_NAMESPACE_IMPL_END