mfsSat.c 5.74 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8
/**CFile****************************************************************

  FileName    [mfsSat.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [The good old minimization with complete don't-cares.]

Alan Mishchenko committed
9
  Synopsis    [Procedures to compute don't-cares using SAT.]
Alan Mishchenko committed
10 11 12 13 14 15 16 17 18 19 20 21 22

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "mfsInt.h"

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

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

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

  Synopsis    [Enumerates through the SAT assignments.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkMfsSolveSat_iter( Mfs_Man_t * p )
{
    int Lits[MFS_FANIN_MAX];
Alan Mishchenko committed
48
    int RetValue, nBTLimit, iVar, b, Mint;
Alan Mishchenko committed
49
//    int nConfs = p->pSat->stats.conflicts;
Alan Mishchenko committed
50 51 52
    if ( p->nTotConfLim && p->nTotConfLim <= p->pSat->stats.conflicts )
        return -1;
    nBTLimit = p->nTotConfLim? p->nTotConfLim - p->pSat->stats.conflicts : 0;
Alan Mishchenko committed
53
    RetValue = sat_solver_solve( p->pSat, NULL, NULL, (ABC_INT64_T)nBTLimit, (ABC_INT64_T)0, (ABC_INT64_T)0, (ABC_INT64_T)0 );
Alan Mishchenko committed
54
    assert( RetValue == l_Undef || RetValue == l_True || RetValue == l_False );
Alan Mishchenko committed
55 56 57 58
//printf( "%c", RetValue==l_Undef ? '?' : (RetValue==l_False ? '-' : '+') );
//printf( "%d ", p->pSat->stats.conflicts-nConfs );
//if ( RetValue==l_False )
//printf( "\n" );
Alan Mishchenko committed
59 60
    if ( RetValue == l_Undef )
        return -1;
Alan Mishchenko committed
61
    if ( RetValue == l_False )
Alan Mishchenko committed
62
        return 0;
Alan Mishchenko committed
63
    p->nCares++;
Alan Mishchenko committed
64 65
    // add SAT assignment to the solver
    Mint = 0;
66
    Vec_IntForEachEntry( p->vProjVarsSat, iVar, b )
Alan Mishchenko committed
67 68 69 70 71 72 73 74
    {
        Lits[b] = toLit( iVar );
        if ( sat_solver_var_value( p->pSat, iVar ) )
        {
            Mint |= (1 << b);
            Lits[b] = lit_neg( Lits[b] );
        }
    }
75 76
    assert( !Abc_InfoHasBit(p->uCare, Mint) );
    Abc_InfoSetBit( p->uCare, Mint );
Alan Mishchenko committed
77
    // add the blocking clause
78
    RetValue = sat_solver_addclause( p->pSat, Lits, Lits + Vec_IntSize(p->vProjVarsSat) );
Alan Mishchenko committed
79 80 81 82 83 84 85 86 87 88 89 90 91 92
    if ( RetValue == 0 )
        return 0;
    return 1;
}

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

  Synopsis    [Enumerates through the SAT assignments.]

  Description []
               
  SideEffects []

  SeeAlso     []
Alan Mishchenko committed
93
 
Alan Mishchenko committed
94
***********************************************************************/
Alan Mishchenko committed
95
int Abc_NtkMfsSolveSat( Mfs_Man_t * p, Abc_Obj_t * pNode )
Alan Mishchenko committed
96 97
{
    Aig_Obj_t * pObjPo;
Alan Mishchenko committed
98
    int RetValue, i;
Alan Mishchenko committed
99
    // collect projection variables
100
    Vec_IntClear( p->vProjVarsSat );
101
    Vec_PtrForEachEntryStart( Aig_Obj_t *, p->pAigWin->vCos, pObjPo, i, Aig_ManCoNum(p->pAigWin) - Abc_ObjFaninNum(pNode) )
Alan Mishchenko committed
102 103
    {
        assert( p->pCnf->pVarNums[pObjPo->Id] >= 0 );
104
        Vec_IntPush( p->vProjVarsSat, p->pCnf->pVarNums[pObjPo->Id] );
Alan Mishchenko committed
105 106 107
    }

    // prepare the truth table of care set
108
    p->nFanins = Vec_IntSize( p->vProjVarsSat );
109
    p->nWords = Abc_TruthWordNum( p->nFanins );
Alan Mishchenko committed
110 111 112 113
    memset( p->uCare, 0, sizeof(unsigned) * p->nWords );

    // iterate through the SAT assignments
    p->nCares = 0;
Alan Mishchenko committed
114 115 116 117
    p->nTotConfLim = p->pPars->nBTLimit;
    while ( (RetValue = Abc_NtkMfsSolveSat_iter(p)) == 1 );
    if ( RetValue == -1 )
        return 0;
Alan Mishchenko committed
118

Alan Mishchenko committed
119
    // write statistics
Alan Mishchenko committed
120
    p->nMintsCare  += p->nCares;
Alan Mishchenko committed
121 122 123 124 125 126 127 128
    p->nMintsTotal += (1<<p->nFanins);

    if ( p->pPars->fVeryVerbose )
    {
        printf( "Node %4d : Care = %2d. Total = %2d.  ", pNode->Id, p->nCares, (1<<p->nFanins) );
        Extra_PrintBinary( stdout, p->uCare, (1<<p->nFanins) );
        printf( "\n" );
    }
Alan Mishchenko committed
129 130 131

    // map the care 
    if ( p->nFanins > 4 )
Alan Mishchenko committed
132
        return 1;
Alan Mishchenko committed
133 134 135 136 137 138 139 140
    if ( p->nFanins == 4 )
        p->uCare[0] = p->uCare[0] | (p->uCare[0] << 16);
    if ( p->nFanins == 3 )
        p->uCare[0] = p->uCare[0] | (p->uCare[0] << 8) | (p->uCare[0] << 16) | (p->uCare[0] << 24);
    if ( p->nFanins == 2 )
        p->uCare[0] = p->uCare[0] | (p->uCare[0] <<  4) | (p->uCare[0] <<  8) | (p->uCare[0] << 12) |
              (p->uCare[0] << 16) | (p->uCare[0] << 20) | (p->uCare[0] << 24) | (p->uCare[0] << 28);
    assert( p->nFanins != 1 );
Alan Mishchenko committed
141
    return 1;
Alan Mishchenko committed
142 143
}

Alan Mishchenko committed
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
/**Function*************************************************************

  Synopsis    [Adds one-hotness constraints for the window inputs.]

  Description []
               
  SideEffects []

  SeeAlso     []
 
***********************************************************************/
int Abc_NtkAddOneHotness( Mfs_Man_t * p )
{
    Aig_Obj_t * pObj1, * pObj2;
    int i, k, Lits[2];
159 160
    for ( i = 0; i < Vec_PtrSize(p->pAigWin->vCis); i++ )
    for ( k = i+1; k < Vec_PtrSize(p->pAigWin->vCis); k++ )
Alan Mishchenko committed
161
    {
162 163
        pObj1 = Aig_ManCi( p->pAigWin, i );
        pObj2 = Aig_ManCi( p->pAigWin, k );
Alan Mishchenko committed
164 165 166 167 168 169 170 171 172 173 174 175
        Lits[0] = toLitCond( p->pCnf->pVarNums[pObj1->Id], 1 );
        Lits[1] = toLitCond( p->pCnf->pVarNums[pObj2->Id], 1 );
        if ( !sat_solver_addclause( p->pSat, Lits, Lits+2 ) )
        {
            sat_solver_delete( p->pSat );
            p->pSat = NULL;
            return 0;
        }
    }
    return 1;
}

Alan Mishchenko committed
176 177 178 179 180
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


181 182
ABC_NAMESPACE_IMPL_END