bmcEco.c

Go to the documentation of this file.

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

  FileName    [bmcEco.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [SAT-based bounded model checking.]

  Synopsis    []

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "bmc.h"
#include "sat/cnf/cnf.h"
#include "sat/bsat/satSolver.h"
#include "aig/gia/giaAig.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    [Computes miter for ECO with given root node and fanins.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Bmc_EcoMiter( Gia_Man_t * pGold, Gia_Man_t * pOld, Vec_Int_t * vFans )
{
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pRoot = Gia_ObjFanin0( Gia_ManPo(pOld, Gia_ManPoNum(pOld)-1) ); // fanin of the last PO
    Gia_Obj_t * pObj;
    int i, NewPi, Miter;
    assert( Gia_ManCiNum(pGold) == Gia_ManCiNum(pOld) );
    assert( Gia_ManCoNum(pGold) == Gia_ManCoNum(pOld) - 1 );
    assert( Gia_ObjIsAnd(pRoot) );
    // create the miter
    pNew = Gia_ManStart( 3 * Gia_ManObjNum(pGold) );
    pNew->pName = Abc_UtilStrsav( pGold->pName );
    Gia_ManHashAlloc( pNew );
    // copy gold
    Gia_ManConst0(pGold)->Value = 0;
    Gia_ManForEachCi( pGold, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    NewPi = Gia_ManAppendCi( pNew );
    Gia_ManForEachAnd( pGold, pObj, i )
        pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( pGold, pObj, i )
        pObj->Value = Gia_ObjFanin0Copy( pObj );
    // create onset
    Gia_ManConst0(pOld)->Value = 0;
    Gia_ManForEachCi( pOld, pObj, i )
        pObj->Value = Gia_ManCi(pGold, i)->Value;
    Gia_ManForEachAnd( pOld, pObj, i )
        if ( pObj == pRoot )
            pObj->Value = NewPi;
        else
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( pOld, pObj, i )
        pObj->Value = Gia_ObjFanin0Copy( pObj );
    Gia_ManForEachCo( pGold, pObj, i )
        Gia_ManAppendCo( pNew, Gia_ManHashXor(pNew, pObj->Value, Gia_ManCo(pOld, i)->Value) );
    // create offset
    Gia_ManForEachAnd( pOld, pObj, i )
        if ( pObj == pRoot )
            pObj->Value = Abc_LitNot(NewPi);
        else
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( pOld, pObj, i )
        pObj->Value = Gia_ObjFanin0Copy( pObj );
    Miter = 0;
    Gia_ManForEachCo( pGold, pObj, i )
        Miter = Gia_ManHashOr( pNew, Miter, Gia_ManHashXor(pNew, pObj->Value, Gia_ManCo(pOld, i)->Value) );
    Gia_ManAppendCo( pNew, Miter );
    // add outputs for the nodes
    Gia_ManForEachObjVec( vFans, pOld, pObj, i )
        Gia_ManAppendCo( pNew, pObj->Value );
    // cleanup
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    assert( Gia_ManPiNum(pNew) == Gia_ManCiNum(pGold) + 1 );
    assert( Gia_ManPoNum(pNew) == Gia_ManCoNum(pGold) + 1 + Vec_IntSize(vFans) );
    return pNew;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Cnf_Dat_t * Cnf_DeriveGiaRemapped( Gia_Man_t * p )
{
    Cnf_Dat_t * pCnf;
    Aig_Man_t * pAig = Gia_ManToAigSimple( p );
    pAig->nRegs = 0;
    pCnf = Cnf_Derive( pAig, Aig_ManCoNum(pAig) );
    Aig_ManStop( pAig );
    return pCnf;
}

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

  Synopsis    [Solve the enumeration problem.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Bmc_EcoSolve( sat_solver * pSat, int Root, Vec_Int_t * vVars )
{
    int nBTLimit = 1000000;
    Vec_Int_t * vValues = Vec_IntAlloc( Vec_IntSize(vVars) );
    Vec_Int_t * vLits   = Vec_IntAlloc( Vec_IntSize(vVars) );
    int status, i, Div, iVar, nFinal, * pFinal, nIter = 0, RetValue = 0;
    int pLits[2], nVars = sat_solver_nvars( pSat );
    sat_solver_setnvars( pSat, nVars + 1 );
    pLits[0] = Abc_Var2Lit( Root, 0 );  // F = 1
    pLits[1] = Abc_Var2Lit( nVars, 0 ); // iNewLit
    while ( 1 ) 
    {
        // find onset minterm
        status = sat_solver_solve( pSat, pLits, pLits + 2, nBTLimit, 0, 0, 0 );
        if ( status == l_Undef )
            { RetValue = -1; break; }
        if ( status == l_False )
            { RetValue = 1; break; }
        assert( status == l_True );
        // remember variable values
        Vec_IntClear( vValues );
        Vec_IntForEachEntry( vVars, iVar, i )
            Vec_IntPush( vValues, sat_solver_var_value(pSat, iVar) );
        // collect divisor literals
        Vec_IntClear( vLits );
        Vec_IntPush( vLits, Abc_LitNot(pLits[0]) ); // F = 0
        Vec_IntForEachEntry( vVars, Div, i )
            Vec_IntPush( vLits, sat_solver_var_literal(pSat, Div) );
        // check against offset
        status = sat_solver_solve( pSat, Vec_IntArray(vLits), Vec_IntArray(vLits) + Vec_IntSize(vLits), nBTLimit, 0, 0, 0 );
        if ( status == l_Undef )
            { RetValue = -1; break; }
        if ( status == l_True )
            break;
        assert( status == l_False );
        // compute cube and add clause
        nFinal = sat_solver_final( pSat, &pFinal );
        Vec_IntClear( vLits );
        Vec_IntPush( vLits, Abc_LitNot(pLits[1]) ); // NOT(iNewLit)
        printf( "Cube %d : ", nIter );
        for ( i = 0; i < nFinal; i++ )
        {
            if ( pFinal[i] == pLits[0] )
                continue;
            Vec_IntPush( vLits, pFinal[i] );
            iVar = Vec_IntFind( vVars, Abc_Lit2Var(pFinal[i]) );   assert( iVar >= 0 );
            printf( "%s%d ", Abc_LitIsCompl(pFinal[i]) ? "+":"-", iVar );
        }
        printf( "\n" );
        status = sat_solver_addclause( pSat, Vec_IntArray(vLits), Vec_IntArray(vLits) + Vec_IntSize(vLits) );
        assert( status );
        nIter++;
    }
//    assert( status == l_True );
    Vec_IntFree( vValues );
    Vec_IntFree( vLits );
    return RetValue;
}

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

  Synopsis    [Compute the patch function.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Bmc_EcoPatch( Gia_Man_t * p, int nIns, int nOuts )
{
    int i, Lit, RetValue, Root;
    Gia_Obj_t * pObj;
    Vec_Int_t * vVars;
    // generate CNF and solver
    Cnf_Dat_t * pCnf = Cnf_DeriveGiaRemapped( p );
    sat_solver * pSat = sat_solver_new();
    sat_solver_setnvars( pSat, pCnf->nVars );
    // add timeframe clauses
    for ( i = 0; i < pCnf->nClauses; i++ )
        if ( !sat_solver_addclause( pSat, pCnf->pClauses[i], pCnf->pClauses[i+1] ) )
            assert( 0 );
    // add equality constraints
    assert( Gia_ManPoNum(p) == nOuts + 1 + nIns );
    Gia_ManForEachPo( p, pObj, i )
    {
        if ( i == nOuts )
            break;
        Lit = Abc_Var2Lit( pCnf->pVarNums[Gia_ObjId(p, pObj)], 1 ); // neg lit
        RetValue = sat_solver_addclause( pSat, &Lit, &Lit + 1 );
        assert( RetValue );
    }
    // add inequality constraint
    pObj = Gia_ManPo( p, nOuts );
    Lit = Abc_Var2Lit( pCnf->pVarNums[Gia_ObjId(p, pObj)], 0 ); // pos lit
    RetValue = sat_solver_addclause( pSat, &Lit, &Lit + 1 );
    assert( RetValue );
    // simplify the SAT solver
    RetValue = sat_solver_simplify( pSat );
    assert( RetValue );
    // collect input variables
    vVars = Vec_IntAlloc( nIns );
    Gia_ManForEachPo( p, pObj, i )
        if ( i >= nOuts + 1 )
            Vec_IntPush( vVars, pCnf->pVarNums[Gia_ObjId(p, pObj)] );
    assert( Vec_IntSize(vVars) == nIns );
    // derive the root variable
    pObj = Gia_ManPi( p, Gia_ManPiNum(p) - 1 );
    Root = pCnf->pVarNums[Gia_ObjId(p, pObj)];
    // solve the problem
    RetValue = Bmc_EcoSolve( pSat, Root, vVars );
    Vec_IntFree( vVars );
    return RetValue;
}

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

  Synopsis    [Tests the ECO miter.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Bmc_EcoMiterTest()
{
    char * pFileGold = "eco_gold.aig";
    char * pFileOld =  "eco_old.aig";
    Vec_Int_t * vFans;
    FILE * pFile;
    Gia_Man_t * pMiter;
    Gia_Obj_t * pObj;
    Gia_Man_t * pGold;
    Gia_Man_t * pOld;
    int i, RetValue;
    // check that the files exist
    pFile = fopen( pFileGold, "r" );
    if ( pFile == NULL )
    {
        printf( "File \"%s\" does not exist.\n", pFileGold );
        return;
    }
    fclose( pFile );
    pFile = fopen( pFileOld, "r" );
    if ( pFile == NULL )
    {
        printf( "File \"%s\" does not exist.\n", pFileOld );
        return;
    }
    fclose( pFile );
    // read files
    pGold = Gia_AigerRead( pFileGold, 0, 0 );
    pOld  = Gia_AigerRead( pFileOld, 0, 0 );
    // create ECO miter
    vFans = Vec_IntAlloc( Gia_ManCiNum(pOld) );
    Gia_ManForEachCi( pOld, pObj, i )
        Vec_IntPush( vFans, Gia_ObjId(pOld, pObj) );
    pMiter = Bmc_EcoMiter( pGold, pOld, vFans );
    Vec_IntFree( vFans );
    Gia_AigerWrite( pMiter, "eco_miter.aig", 0, 0 );
    // find the patch
    RetValue = Bmc_EcoPatch( pMiter, Gia_ManCiNum(pGold), Gia_ManCoNum(pGold) );
    if ( RetValue == 1 )
        printf( "Patch is computed.\n" );
    if ( RetValue == 0 )
        printf( "Cannot be patched.\n" );
    if ( RetValue == -1 )
        printf( "Resource limit exceeded.\n" );
    Gia_ManStop( pMiter );
}

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


ABC_NAMESPACE_IMPL_END