resSat.c

Go to the documentation of this file.

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

  FileName    [resSat.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Resynthesis package.]

  Synopsis    [Interface with the SAT solver.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - January 15, 2007.]

  Revision    [$Id: resSat.c,v 1.00 2007/01/15 00:00:00 alanmi Exp $]

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

#include "base/abc/abc.h"
#include "resInt.h"
#include "aig/hop/hop.h"
#include "sat/bsat/satSolver.h"

ABC_NAMESPACE_IMPL_START


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

extern int Res_SatAddConst1( sat_solver * pSat, int iVar, int fCompl );
extern int Res_SatAddEqual( sat_solver * pSat, int iVar0, int iVar1, int fCompl );
extern int Res_SatAddAnd( sat_solver * pSat, int iVar, int iVar0, int iVar1, int fCompl0, int fCompl1 );

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

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

  Synopsis    [Loads AIG into the SAT solver for checking resubstitution.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void * Res_SatProveUnsat( Abc_Ntk_t * pAig, Vec_Ptr_t * vFanins )
{
    void * pCnf = NULL;
    sat_solver * pSat;
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pObj;
    int i, nNodes, status;

    // make sure fanins contain POs of the AIG
    pObj = (Abc_Obj_t *)Vec_PtrEntry( vFanins, 0 );
    assert( pObj->pNtk == pAig && Abc_ObjIsPo(pObj) );

    // collect reachable nodes
    vNodes = Abc_NtkDfsNodes( pAig, (Abc_Obj_t **)vFanins->pArray, vFanins->nSize );

    // assign unique numbers to each node
    nNodes = 0;
    Abc_AigConst1(pAig)->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;
    Abc_NtkForEachPi( pAig, pObj, i )
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i ) // useful POs
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;

    // start the solver
    pSat = sat_solver_new();
    sat_solver_store_alloc( pSat );

    // add clause for the constant node
    Res_SatAddConst1( pSat, (int)(ABC_PTRUINT_T)Abc_AigConst1(pAig)->pCopy, 0 );
    // add clauses for AND gates
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
        Res_SatAddAnd( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 
            (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pCopy, (int)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pCopy, Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) );
    Vec_PtrFree( vNodes );
    // add clauses for POs
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i )
        Res_SatAddEqual( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 
            (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pCopy, Abc_ObjFaninC0(pObj) );
    // add trivial clauses
    pObj = (Abc_Obj_t *)Vec_PtrEntry(vFanins, 0);
    Res_SatAddConst1( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 0 ); // care-set
    pObj = (Abc_Obj_t *)Vec_PtrEntry(vFanins, 1);
    Res_SatAddConst1( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 0 ); // on-set

    // bookmark the clauses of A
    sat_solver_store_mark_clauses_a( pSat );

    // duplicate the clauses
    pObj = (Abc_Obj_t *)Vec_PtrEntry(vFanins, 1);
    Sat_SolverDoubleClauses( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy );
    // add the equality constraints
    Vec_PtrForEachEntryStart( Abc_Obj_t *, vFanins, pObj, i, 2 )
        Res_SatAddEqual( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, ((int)(ABC_PTRUINT_T)pObj->pCopy) + nNodes, 0 );

    // bookmark the roots
    sat_solver_store_mark_roots( pSat );

    // solve the problem
    status = sat_solver_solve( pSat, NULL, NULL, (ABC_INT64_T)10000, (ABC_INT64_T)0, (ABC_INT64_T)0, (ABC_INT64_T)0 );
    if ( status == l_False )
    {
        pCnf = sat_solver_store_release( pSat );
//        printf( "unsat\n" );
    }
    else if ( status == l_True )
    {
//        printf( "sat\n" );
    }
    else
    {
//        printf( "undef\n" );
    }
    sat_solver_delete( pSat );
    return pCnf;
}

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

  Synopsis    [Loads AIG into the SAT solver for constrained simulation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void * Res_SatSimulateConstr( Abc_Ntk_t * pAig, int fOnSet )
{
    sat_solver * pSat;
    Vec_Ptr_t * vFanins;
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pObj;
    int i, nNodes;

    // start the array
    vFanins = Vec_PtrAlloc( 2 );
    pObj = Abc_NtkPo( pAig, 0 );
    Vec_PtrPush( vFanins, pObj );
    pObj = Abc_NtkPo( pAig, 1 );
    Vec_PtrPush( vFanins, pObj );

    // collect reachable nodes
    vNodes = Abc_NtkDfsNodes( pAig, (Abc_Obj_t **)vFanins->pArray, vFanins->nSize );

    // assign unique numbers to each node
    nNodes = 0;
    Abc_AigConst1(pAig)->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;
    Abc_NtkForEachPi( pAig, pObj, i )
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i ) // useful POs
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)nNodes++;

    // start the solver
    pSat = sat_solver_new();

    // add clause for the constant node
    Res_SatAddConst1( pSat, (int)(ABC_PTRUINT_T)Abc_AigConst1(pAig)->pCopy, 0 );
    // add clauses for AND gates
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
        Res_SatAddAnd( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 
            (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pCopy, (int)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pCopy, Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) );
    Vec_PtrFree( vNodes );
    // add clauses for the first PO
    pObj = Abc_NtkPo( pAig, 0 );
    Res_SatAddEqual( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 
        (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pCopy, Abc_ObjFaninC0(pObj) );
    // add clauses for the second PO
    pObj = Abc_NtkPo( pAig, 1 );
    Res_SatAddEqual( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 
        (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pCopy, Abc_ObjFaninC0(pObj) );

    // add trivial clauses
    pObj = Abc_NtkPo( pAig, 0 );
    Res_SatAddConst1( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, 0 ); // care-set

    pObj = Abc_NtkPo( pAig, 1 );
    Res_SatAddConst1( pSat, (int)(ABC_PTRUINT_T)pObj->pCopy, !fOnSet ); // on-set

    Vec_PtrFree( vFanins );
    return pSat;
}

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

  Synopsis    [Loads AIG into the SAT solver for constrained simulation.]

  Description [Returns 1 if the required number of patterns are found. 
  Returns 0 if the solver ran out of time or proved a constant. 
  In the latter, case one of the flags, fConst0 or fConst1, are set to 1.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Res_SatSimulate( Res_Sim_t * p, int nPatsLimit, int fOnSet )
{
    Vec_Int_t * vLits;
    Vec_Ptr_t * vPats;
    sat_solver * pSat;
    int RetValue = -1; // Suppress "might be used uninitialized"
    int i, k, value, status, Lit, Var, iPat;
    abctime clk = Abc_Clock();

//printf( "Looking for %s:  ", fOnSet? "onset " : "offset" );

    // decide what problem should be solved
    Lit = toLitCond( (int)(ABC_PTRUINT_T)Abc_NtkPo(p->pAig,1)->pCopy, !fOnSet );
    if ( fOnSet )
    {
        iPat = p->nPats1;
        vPats = p->vPats1;
    }
    else
    {
        iPat = p->nPats0;
        vPats = p->vPats0;
    }
    assert( iPat < nPatsLimit );

    // derive the SAT solver
    pSat = (sat_solver *)Res_SatSimulateConstr( p->pAig, fOnSet );
    pSat->fSkipSimplify = 1;
    status = sat_solver_simplify( pSat );
    if ( status == 0 )
    {
        if ( iPat == 0 )
        {
//            if ( fOnSet )
//                p->fConst0 = 1;
//            else
//                p->fConst1 = 1;
            RetValue = 0;
        }
        goto finish;
    }
 
    // enumerate through the SAT assignments
    RetValue = 1;
    vLits = Vec_IntAlloc( 32 );
    for ( k = iPat; k < nPatsLimit; k++ )
    {
        // solve with the assumption
//        status = sat_solver_solve( pSat, &Lit, &Lit + 1, (ABC_INT64_T)10000, (ABC_INT64_T)0, (ABC_INT64_T)0, (ABC_INT64_T)0 );
        status = sat_solver_solve( pSat, NULL, NULL, (ABC_INT64_T)10000, (ABC_INT64_T)0, (ABC_INT64_T)0, (ABC_INT64_T)0 );
        if ( status == l_False )
        {
//printf( "Const %d\n", !fOnSet );
            if ( k == 0 )
            {
                if ( fOnSet )
                    p->fConst0 = 1;
                else
                    p->fConst1 = 1;
                RetValue = 0;
            }
            break;
        }
        else if ( status == l_True )
        {
            // save the pattern
            Vec_IntClear( vLits );
            for ( i = 0; i < p->nTruePis; i++ )
            {
                Var = (int)(ABC_PTRUINT_T)Abc_NtkPi(p->pAig,i)->pCopy;
//                value = (int)(pSat->model.ptr[Var] == l_True);
                value = sat_solver_var_value(pSat, Var);
                if ( value )
                    Abc_InfoSetBit( (unsigned *)Vec_PtrEntry(vPats, i), k );
                Lit = toLitCond( Var, value );
                Vec_IntPush( vLits, Lit );
//                printf( "%d", value );
            }
//            printf( "\n" );

            status = sat_solver_addclause( pSat, Vec_IntArray(vLits), Vec_IntArray(vLits) + Vec_IntSize(vLits) );
            if ( status == 0 )
            {
                k++;
                RetValue = 1; 
                break;
            }
        }
        else
        {
//printf( "Undecided\n" );
            if ( k == 0 )
                RetValue = 0;
            else
                RetValue = 1; 
            break;
        }
    }
    Vec_IntFree( vLits );
//printf( "Found %d patterns\n", k - iPat );

    // set the new number of patterns
    if ( fOnSet )
        p->nPats1 = k;
    else
        p->nPats0 = k;

finish:

    sat_solver_delete( pSat );
p->timeSat += Abc_Clock() - clk;
    return RetValue;
}


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

  Synopsis    [Asserts equality of the variable to a constant.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Res_SatAddConst1( sat_solver * pSat, int iVar, int fCompl )
{
    lit Lit = toLitCond( iVar, fCompl );
    if ( !sat_solver_addclause( pSat, &Lit, &Lit + 1 ) )
        return 0;
    return 1;
}

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

  Synopsis    [Asserts equality of two variables.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Res_SatAddEqual( sat_solver * pSat, int iVar0, int iVar1, int fCompl )
{
    lit Lits[2];

    Lits[0] = toLitCond( iVar0, 0 );
    Lits[1] = toLitCond( iVar1, !fCompl );
    if ( !sat_solver_addclause( pSat, Lits, Lits + 2 ) )
        return 0;

    Lits[0] = toLitCond( iVar0, 1 );
    Lits[1] = toLitCond( iVar1, fCompl );
    if ( !sat_solver_addclause( pSat, Lits, Lits + 2 ) )
        return 0;

    return 1;
}

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

  Synopsis    [Adds constraints for the two-input AND-gate.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Res_SatAddAnd( sat_solver * pSat, int iVar, int iVar0, int iVar1, int fCompl0, int fCompl1 )
{
    lit Lits[3];

    Lits[0] = toLitCond( iVar, 1 );
    Lits[1] = toLitCond( iVar0, fCompl0 );
    if ( !sat_solver_addclause( pSat, Lits, Lits + 2 ) )
        return 0;

    Lits[0] = toLitCond( iVar, 1 );
    Lits[1] = toLitCond( iVar1, fCompl1 );
    if ( !sat_solver_addclause( pSat, Lits, Lits + 2 ) )
        return 0;

    Lits[0] = toLitCond( iVar, 0 );
    Lits[1] = toLitCond( iVar0, !fCompl0 );
    Lits[2] = toLitCond( iVar1, !fCompl1 );
    if ( !sat_solver_addclause( pSat, Lits, Lits + 3 ) )
        return 0;

    return 1;
}

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


ABC_NAMESPACE_IMPL_END