saigInd.c

Go to the documentation of this file.

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

  FileName    [saigLoc.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Sequential AIG package.]

  Synopsis    [K-step induction for one property only.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "saig.h"
#include "sat/cnf/cnf.h"
#include "sat/bsat/satSolver.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    [Returns 1 if two state are equal.]

  Description [Array vState contains indexes of CNF variables for each
  flop in the first N time frames (0 < i < k, i < N, k < N).]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Saig_ManStatesAreEqual( sat_solver * pSat, Vec_Int_t * vState, int nRegs, int i, int k )
{
    int * pStateI = (int *)Vec_IntArray(vState) + nRegs * i;
    int * pStateK = (int *)Vec_IntArray(vState) + nRegs * k;
    int v;
    assert( i && k && i < k );
    assert( nRegs * k <= Vec_IntSize(vState) );
    // check if the states are available
    for ( v = 0; v < nRegs; v++ )
        if ( pStateI[v] >= 0 && pStateK[v] == -1 )
            return 0;
/*
    printf( "\nchecking uniqueness\n" );
    printf( "%3d : ", i );
    for ( v = 0; v < nRegs; v++ )
        printf( "%d", sat_solver_var_value(pSat, pStateI[v]) );
    printf( "\n" );

    printf( "%3d : ", k );
    for ( v = 0; v < nRegs; v++ )
        printf( "%d", sat_solver_var_value(pSat, pStateK[v]) );
    printf( "\n" );
*/
    for ( v = 0; v < nRegs; v++ )
        if ( pStateI[v] >= 0 )
        {
            if ( sat_solver_var_value(pSat, pStateI[v]) != sat_solver_var_value(pSat, pStateK[v]) )
                return 0;
        }
    return 1;
}

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

  Synopsis    [Add uniqueness constraint.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Saig_ManAddUniqueness( sat_solver * pSat, Vec_Int_t * vState, int nRegs, int i, int k, int * pnSatVarNum, int * pnClauses, int fVerbose )
{
    int * pStateI = (int *)Vec_IntArray(vState) + nRegs * i;
    int * pStateK = (int *)Vec_IntArray(vState) + nRegs * k;
    int v, iVars, nSatVarsOld, RetValue, * pClause;
    assert( i && k && i < k );
    assert( nRegs * k <= Vec_IntSize(vState) );
    // check if the states are available
    for ( v = 0; v < nRegs; v++ )
        if ( pStateI[v] >= 0 && pStateK[v] == -1 )
        {
            if ( fVerbose )
                printf( "Cannot constrain an incomplete state.\n" );
            return 0;
        }
    // add XORs
    nSatVarsOld = *pnSatVarNum;
    for ( v = 0; v < nRegs; v++ )
        if ( pStateI[v] >= 0 )
        {
            *pnClauses += 4;
            RetValue = Cnf_DataAddXorClause( pSat, pStateI[v], pStateK[v], (*pnSatVarNum)++ );
            if ( RetValue == 0 )
            {
                if ( fVerbose )
                    printf( "SAT solver became UNSAT after adding a uniqueness constraint.\n" );
                return 1;
            }
        }
    // add OR clause
    (*pnClauses)++;
    iVars = 0;
    pClause = ABC_ALLOC( int, nRegs );
    for ( v = nSatVarsOld; v < *pnSatVarNum; v++ )
        pClause[iVars++] = toLitCond( v, 0 );
    assert( iVars <= nRegs );
    RetValue = sat_solver_addclause( pSat, pClause, pClause + iVars );
    ABC_FREE( pClause );
    if ( RetValue == 0 )
    {
        if ( fVerbose )
            printf( "SAT solver became UNSAT after adding a uniqueness constraint.\n" );
        return 1;
    }
    return 0;
}

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

  Synopsis    [Performs induction by unrolling timeframes backward.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Saig_ManInduction( Aig_Man_t * p, int nTimeOut, int nFramesMax, int nConfMax, int fUnique, int fUniqueAll, int fGetCex, int fVerbose, int fVeryVerbose )
{
    sat_solver * pSat;
    Aig_Man_t * pAigPart = NULL;
    Cnf_Dat_t * pCnfPart = NULL;
    Vec_Int_t * vTopVarNums, * vState, * vTopVarIds = NULL;
    Vec_Ptr_t * vTop, * vBot;
    Aig_Obj_t * pObjPi, * pObjPiCopy, * pObjPo;
    int i, k, f, Lits[2], status = -1, RetValue, nSatVarNum, nConfPrev;
    int nOldSize, iReg, iLast, fAdded, nConstrs = 0, nClauses = 0;
    abctime clk, nTimeToStop = nTimeOut ? nTimeOut * CLOCKS_PER_SEC + Abc_Clock() : 0;
    assert( fUnique == 0 || fUniqueAll == 0 );
    assert( Saig_ManPoNum(p) == 1 );
    Aig_ManSetCioIds( p );

    // start the top by including the PO
    vBot = Vec_PtrAlloc( 100 );
    vTop = Vec_PtrAlloc( 100 );
    vState = Vec_IntAlloc( 1000 );
    Vec_PtrPush( vTop, Aig_ManCo(p, 0) );
    // start the array of CNF variables
    vTopVarNums = Vec_IntAlloc( 100 );
    // start the solver
    pSat = sat_solver_new();
    sat_solver_setnvars( pSat, 1000 );

    // set runtime limit
    if ( nTimeToStop )
        sat_solver_set_runtime_limit( pSat, nTimeToStop );

    // iterate backward unrolling
    RetValue = -1;
    nSatVarNum = 0;
    if ( fVerbose )
        printf( "Induction parameters: FramesMax = %5d. ConflictMax = %6d.\n", nFramesMax, nConfMax );
    for ( f = 0; ; f++ )
    { 
        if ( f > 0 )
        {
            Aig_ManStop( pAigPart );
            Cnf_DataFree( pCnfPart );
        }
        clk = Abc_Clock();
        // get the bottom
        Aig_SupportNodes( p, (Aig_Obj_t **)Vec_PtrArray(vTop), Vec_PtrSize(vTop), vBot );
        // derive AIG for the part between top and bottom
        pAigPart = Aig_ManDupSimpleDfsPart( p, vBot, vTop );
        // convert it into CNF
        pCnfPart = Cnf_Derive( pAigPart, Aig_ManCoNum(pAigPart) );
        Cnf_DataLift( pCnfPart, nSatVarNum );
        nSatVarNum += pCnfPart->nVars;
        nClauses   += pCnfPart->nClauses;

        // remember top frame var IDs
        if ( fGetCex && vTopVarIds == NULL )
        {
            vTopVarIds = Vec_IntStartFull( Aig_ManCiNum(p) );
            Aig_ManForEachCi( p, pObjPi, i )
            {
                if ( pObjPi->pData == NULL )
                    continue;
                pObjPiCopy = (Aig_Obj_t *)pObjPi->pData;
                assert( Aig_ObjIsCi(pObjPiCopy) );
                if ( Saig_ObjIsPi(p, pObjPi) )
                    Vec_IntWriteEntry( vTopVarIds, Aig_ObjCioId(pObjPi) + Saig_ManRegNum(p), pCnfPart->pVarNums[Aig_ObjId(pObjPiCopy)] );
                else if ( Saig_ObjIsLo(p, pObjPi) )
                    Vec_IntWriteEntry( vTopVarIds, Aig_ObjCioId(pObjPi) - Saig_ManPiNum(p), pCnfPart->pVarNums[Aig_ObjId(pObjPiCopy)] );
                else assert( 0 );
            }
        }

        // stitch variables of top and bot
        assert( Aig_ManCoNum(pAigPart)-1 == Vec_IntSize(vTopVarNums) );
        Aig_ManForEachCo( pAigPart, pObjPo, i )
        {
            if ( i == 0 )
            {
                // do not perform inductive strengthening
//                if ( f > 0 )
//                    continue;
                // add topmost literal
                Lits[0] = toLitCond( pCnfPart->pVarNums[pObjPo->Id], f>0 );
                if ( !sat_solver_addclause( pSat, Lits, Lits+1 ) )
                    assert( 0 );
                nClauses++;
                continue;
            }
            Lits[0] = toLitCond( Vec_IntEntry(vTopVarNums, i-1), 0 );
            Lits[1] = toLitCond( pCnfPart->pVarNums[pObjPo->Id], 1 );
            if ( !sat_solver_addclause( pSat, Lits, Lits+2 ) )
                assert( 0 );
            Lits[0] = toLitCond( Vec_IntEntry(vTopVarNums, i-1), 1 );
            Lits[1] = toLitCond( pCnfPart->pVarNums[pObjPo->Id], 0 );
            if ( !sat_solver_addclause( pSat, Lits, Lits+2 ) )
                assert( 0 );
            nClauses += 2;
        }
        // add CNF to the SAT solver
        for ( i = 0; i < pCnfPart->nClauses; i++ )
            if ( !sat_solver_addclause( pSat, pCnfPart->pClauses[i], pCnfPart->pClauses[i+1] ) )
                break;
        if ( i < pCnfPart->nClauses )
        {
//            printf( "SAT solver became UNSAT after adding clauses.\n" );
            RetValue = 1;
            break;
        }

        // create new set of POs to derive new top
        Vec_PtrClear( vTop );
        Vec_PtrPush( vTop, Aig_ManCo(p, 0) );
        Vec_IntClear( vTopVarNums );
        nOldSize = Vec_IntSize(vState);
        Vec_IntFillExtra( vState, nOldSize + Aig_ManRegNum(p), -1 );
        Vec_PtrForEachEntry( Aig_Obj_t *, vBot, pObjPi, i )
        {
            assert( Aig_ObjIsCi(pObjPi) );
            if ( Saig_ObjIsLo(p, pObjPi) )
            {
                pObjPiCopy = (Aig_Obj_t *)pObjPi->pData;
                assert( pObjPiCopy != NULL );
                Vec_PtrPush( vTop, Saig_ObjLoToLi(p, pObjPi) );
                Vec_IntPush( vTopVarNums, pCnfPart->pVarNums[pObjPiCopy->Id] );

                iReg = pObjPi->CioId - Saig_ManPiNum(p);
                assert( iReg >= 0 && iReg < Aig_ManRegNum(p) );
                Vec_IntWriteEntry( vState, nOldSize+iReg, pCnfPart->pVarNums[pObjPiCopy->Id] );
            }
        } 
        assert( Vec_IntSize(vState)%Aig_ManRegNum(p) == 0 );
        iLast = Vec_IntSize(vState)/Aig_ManRegNum(p);
        if ( fUniqueAll )
        {
            for ( i = 1; i < iLast-1; i++ )
            {
                nConstrs++;
                if ( fVeryVerbose )
                    printf( "Adding constaint for state %2d and state %2d.\n", i, iLast-1 );
                if ( Saig_ManAddUniqueness( pSat, vState, Aig_ManRegNum(p), i, iLast-1, &nSatVarNum, &nClauses, fVerbose ) )
                    break;
            }
            if ( i < iLast-1 )
            {
                RetValue = 1;
                break;
            }
        }

nextrun:
        fAdded = 0;
        // run the SAT solver
        nConfPrev = pSat->stats.conflicts;
        status = sat_solver_solve( pSat, NULL, NULL, (ABC_INT64_T)nConfMax, 0, 0, 0 );
        if ( fVerbose )
        {
            printf( "Frame %4d : PI =%5d. PO =%5d. AIG =%5d. Var =%7d. Clau =%7d. Conf =%7d. ",
                f, Aig_ManCiNum(pAigPart), Aig_ManCoNum(pAigPart), Aig_ManNodeNum(pAigPart), 
                nSatVarNum, nClauses, (int)pSat->stats.conflicts-nConfPrev );
            ABC_PRT( "Time", Abc_Clock() - clk );
        }
        if ( status == l_Undef )
            break;
        if ( status == l_False )
        {
            RetValue = 1;
            break;
        }
        assert( status == l_True );
        // the problem is SAT - add more clauses
        if ( fVeryVerbose )
        {
            Vec_IntForEachEntry( vState, iReg, i )
            {
                if ( i && (i % Aig_ManRegNum(p)) == 0 )
                    printf( "\n" );
                if ( (i % Aig_ManRegNum(p)) == 0 )
                    printf( "       State %3d : ", i/Aig_ManRegNum(p) );
                printf( "%c", (iReg >= 0) ? ('0' + sat_solver_var_value(pSat, iReg)) : 'x' );
            }
            printf( "\n" );
        }
        if ( nFramesMax && f == nFramesMax - 1 )
        {
            // derive counter-example
            assert( status == l_True );
            if ( fGetCex )
            {
                int VarNum, iBit = 0;
                Abc_Cex_t * pCex = Abc_CexAlloc( Aig_ManRegNum(p)-1, Saig_ManPiNum(p), 1 );
                pCex->iFrame = 0;
                pCex->iPo = 0;
                Vec_IntForEachEntryStart( vTopVarIds, VarNum, i, 1 )
                {
                    if ( VarNum >= 0 && sat_solver_var_value( pSat, VarNum ) )
                        Abc_InfoSetBit( pCex->pData, iBit );
                    iBit++;
                }
                assert( iBit == pCex->nBits );
                Abc_CexFree( p->pSeqModel );
                p->pSeqModel = pCex;
            }
            break;
        }
        if ( fUnique )
        {
            for ( i = 1; i < iLast; i++ )
            {
                for ( k = i+1; k < iLast; k++ )
                {
                    if ( !Saig_ManStatesAreEqual( pSat, vState, Aig_ManRegNum(p), i, k ) )
                        continue;
                    nConstrs++;
                    fAdded = 1;
                    if ( fVeryVerbose )
                        printf( "Adding constaint for state %2d and state %2d.\n", i, k );
                    if ( Saig_ManAddUniqueness( pSat, vState, Aig_ManRegNum(p), i, k, &nSatVarNum, &nClauses, fVerbose ) )
                        break;
                }
                if ( k < iLast )
                    break;
            }
            if ( i < iLast )
            {
                RetValue = 1;
                break;
            }
        }
        if ( fAdded )
            goto nextrun;
    }
    if ( fVerbose )
    {
        if ( nTimeToStop && Abc_Clock() >= nTimeToStop )
            printf( "Timeout (%d sec) was reached during iteration %d.\n", nTimeOut, f+1 );
        else if ( status == l_Undef )
            printf( "Conflict limit (%d) was reached during iteration %d.\n", nConfMax, f+1 );
        else if ( fUnique || fUniqueAll )
            printf( "Completed %d interations and added %d uniqueness constraints.\n", f+1, nConstrs );
        else
            printf( "Completed %d interations.\n", f+1 );
    }
    // cleanup
    sat_solver_delete( pSat );
    Aig_ManStop( pAigPart );
    Cnf_DataFree( pCnfPart );
    Vec_IntFree( vTopVarNums );
    Vec_PtrFree( vTop );
    Vec_PtrFree( vBot );
    Vec_IntFree( vState );
    Vec_IntFreeP( &vTopVarIds );
    return RetValue;
}


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


ABC_NAMESPACE_IMPL_END