abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
mfsSat.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [mfsSat.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [The good old minimization with complete don't-cares.]
8 
9  Synopsis [Procedures to compute don't-cares using SAT.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: mfsSat.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "mfsInt.h"
22 
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 /**Function*************************************************************
35 
36  Synopsis [Enumerates through the SAT assignments.]
37 
38  Description []
39 
40  SideEffects []
41 
42  SeeAlso []
43 
44 ***********************************************************************/
46 {
47  int Lits[MFS_FANIN_MAX];
48  int RetValue, nBTLimit, iVar, b, Mint;
49 // int nConfs = p->pSat->stats.conflicts;
50  if ( p->nTotConfLim && p->nTotConfLim <= p->pSat->stats.conflicts )
51  return -1;
52  nBTLimit = p->nTotConfLim? p->nTotConfLim - p->pSat->stats.conflicts : 0;
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 );
54  assert( RetValue == l_Undef || RetValue == l_True || RetValue == l_False );
55 //printf( "%c", RetValue==l_Undef ? '?' : (RetValue==l_False ? '-' : '+') );
56 //printf( "%d ", p->pSat->stats.conflicts-nConfs );
57 //if ( RetValue==l_False )
58 //printf( "\n" );
59  if ( RetValue == l_Undef )
60  return -1;
61  if ( RetValue == l_False )
62  return 0;
63  p->nCares++;
64  // add SAT assignment to the solver
65  Mint = 0;
66  Vec_IntForEachEntry( p->vProjVarsSat, iVar, b )
67  {
68  Lits[b] = toLit( iVar );
69  if ( sat_solver_var_value( p->pSat, iVar ) )
70  {
71  Mint |= (1 << b);
72  Lits[b] = lit_neg( Lits[b] );
73  }
74  }
75  assert( !Abc_InfoHasBit(p->uCare, Mint) );
76  Abc_InfoSetBit( p->uCare, Mint );
77  // add the blocking clause
78  RetValue = sat_solver_addclause( p->pSat, Lits, Lits + Vec_IntSize(p->vProjVarsSat) );
79  if ( RetValue == 0 )
80  return 0;
81  return 1;
82 }
83 
84 /**Function*************************************************************
85 
86  Synopsis [Enumerates through the SAT assignments.]
87 
88  Description []
89 
90  SideEffects []
91 
92  SeeAlso []
93 
94 ***********************************************************************/
96 {
97  Aig_Obj_t * pObjPo;
98  int RetValue, i;
99  // collect projection variables
101  Vec_PtrForEachEntryStart( Aig_Obj_t *, p->pAigWin->vCos, pObjPo, i, Aig_ManCoNum(p->pAigWin) - Abc_ObjFaninNum(pNode) )
102  {
103  assert( p->pCnf->pVarNums[pObjPo->Id] >= 0 );
104  Vec_IntPush( p->vProjVarsSat, p->pCnf->pVarNums[pObjPo->Id] );
105  }
106 
107  // prepare the truth table of care set
108  p->nFanins = Vec_IntSize( p->vProjVarsSat );
109  p->nWords = Abc_TruthWordNum( p->nFanins );
110  memset( p->uCare, 0, sizeof(unsigned) * p->nWords );
111 
112  // iterate through the SAT assignments
113  p->nCares = 0;
114  p->nTotConfLim = p->pPars->nBTLimit;
115  while ( (RetValue = Abc_NtkMfsSolveSat_iter(p)) == 1 );
116  if ( RetValue == -1 )
117  return 0;
118 
119  // write statistics
120  p->nMintsCare += p->nCares;
121  p->nMintsTotal += (1<<p->nFanins);
122 
123  if ( p->pPars->fVeryVerbose )
124  {
125  printf( "Node %4d : Care = %2d. Total = %2d. ", pNode->Id, p->nCares, (1<<p->nFanins) );
126  Extra_PrintBinary( stdout, p->uCare, (1<<p->nFanins) );
127  printf( "\n" );
128  }
129 
130  // map the care
131  if ( p->nFanins > 4 )
132  return 1;
133  if ( p->nFanins == 4 )
134  p->uCare[0] = p->uCare[0] | (p->uCare[0] << 16);
135  if ( p->nFanins == 3 )
136  p->uCare[0] = p->uCare[0] | (p->uCare[0] << 8) | (p->uCare[0] << 16) | (p->uCare[0] << 24);
137  if ( p->nFanins == 2 )
138  p->uCare[0] = p->uCare[0] | (p->uCare[0] << 4) | (p->uCare[0] << 8) | (p->uCare[0] << 12) |
139  (p->uCare[0] << 16) | (p->uCare[0] << 20) | (p->uCare[0] << 24) | (p->uCare[0] << 28);
140  assert( p->nFanins != 1 );
141  return 1;
142 }
143 
144 /**Function*************************************************************
145 
146  Synopsis [Adds one-hotness constraints for the window inputs.]
147 
148  Description []
149 
150  SideEffects []
151 
152  SeeAlso []
153 
154 ***********************************************************************/
156 {
157  Aig_Obj_t * pObj1, * pObj2;
158  int i, k, Lits[2];
159  for ( i = 0; i < Vec_PtrSize(p->pAigWin->vCis); i++ )
160  for ( k = i+1; k < Vec_PtrSize(p->pAigWin->vCis); k++ )
161  {
162  pObj1 = Aig_ManCi( p->pAigWin, i );
163  pObj2 = Aig_ManCi( p->pAigWin, k );
164  Lits[0] = toLitCond( p->pCnf->pVarNums[pObj1->Id], 1 );
165  Lits[1] = toLitCond( p->pCnf->pVarNums[pObj2->Id], 1 );
166  if ( !sat_solver_addclause( p->pSat, Lits, Lits+2 ) )
167  {
168  sat_solver_delete( p->pSat );
169  p->pSat = NULL;
170  return 0;
171  }
172  }
173  return 1;
174 }
175 
176 ////////////////////////////////////////////////////////////////////////
177 /// END OF FILE ///
178 ////////////////////////////////////////////////////////////////////////
179 
180 
182 
char * memset()
#define Vec_PtrForEachEntryStart(Type, vVec, pEntry, i, Start)
Definition: vecPtr.h:57
Vec_Int_t * vProjVarsSat
Definition: mfsInt.h:65
static Llb_Mgr_t * p
Definition: llb3Image.c:950
int sat_solver_addclause(sat_solver *s, lit *begin, lit *end)
Definition: satSolver.c:1492
static int Abc_InfoHasBit(unsigned *p, int i)
Definition: abc_global.h:258
#define l_Undef
Definition: SolverTypes.h:86
int sat_solver_solve(sat_solver *s, lit *begin, lit *end, ABC_INT64_T nConfLimit, ABC_INT64_T nInsLimit, ABC_INT64_T nConfLimitGlobal, ABC_INT64_T nInsLimitGlobal)
Definition: satSolver.c:1700
Mfs_Par_t * pPars
Definition: mfsInt.h:53
void sat_solver_delete(sat_solver *s)
Definition: satSolver.c:1141
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
int * pVarNums
Definition: cnf.h:63
int nMintsCare
Definition: mfsInt.h:110
#define l_True
Definition: SolverTypes.h:84
int nTotConfLim
Definition: mfsInt.h:94
static int Abc_TruthWordNum(int nVars)
Definition: abc_global.h:256
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
stats_t stats
Definition: satSolver.h:156
static int sat_solver_var_value(sat_solver *s, int v)
Definition: satSolver.h:200
Aig_Man_t * pAigWin
Definition: mfsInt.h:87
static lit lit_neg(lit l)
Definition: satVec.h:144
static int Aig_ManCoNum(Aig_Man_t *p)
Definition: aig.h:252
static lit toLit(int v)
Definition: satVec.h:142
ABC_NAMESPACE_IMPL_START int Abc_NtkMfsSolveSat_iter(Mfs_Man_t *p)
DECLARATIONS ///.
Definition: mfsSat.c:45
static Aig_Obj_t * Aig_ManCi(Aig_Man_t *p, int i)
Definition: aig.h:266
unsigned uCare[(MFS_FANIN_MAX<=5)?1:1<<(MFS_FANIN_MAX-5)]
Definition: mfsInt.h:102
static lit toLitCond(int v, int c)
Definition: satVec.h:143
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Definition: aig.h:69
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
int nFanins
Definition: mfsInt.h:99
int Abc_NtkAddOneHotness(Mfs_Man_t *p)
Definition: mfsSat.c:155
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
static void Abc_InfoSetBit(unsigned *p, int i)
Definition: abc_global.h:259
ABC_INT64_T conflicts
Definition: satVec.h:154
int nWords
Definition: mfsInt.h:100
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
void Extra_PrintBinary(FILE *pFile, unsigned Sign[], int nBits)
int Id
Definition: abc.h:132
#define l_False
Definition: SolverTypes.h:85
int Abc_NtkMfsSolveSat(Mfs_Man_t *p, Abc_Obj_t *pNode)
Definition: mfsSat.c:95
#define assert(ex)
Definition: util_old.h:213
sat_solver * pSat
Definition: mfsInt.h:89
int nCares
Definition: mfsInt.h:101
Cnf_Dat_t * pCnf
Definition: mfsInt.h:88
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
int Id
Definition: aig.h:85
int nMintsTotal
Definition: mfsInt.h:111
#define MFS_FANIN_MAX
INCLUDES ///.
Definition: mfsInt.h:47