1 /**CFile****************************************************************
2 
3   FileName    [bmcCexMin2.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [SAT-based bounded model checking.]
8 
9   Synopsis    [CEX minimization.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - June 20, 2005.]
16 
17   Revision    [$Id: bmcCexMin2.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "aig/gia/gia.h"
22 #include "bmc.h"
23 
24 ABC_NAMESPACE_IMPL_START
25 
26 
27 ////////////////////////////////////////////////////////////////////////
28 ///                        DECLARATIONS                              ///
29 ////////////////////////////////////////////////////////////////////////
30 
Abc_InfoGet2Bits(Vec_Int_t * vData,int nWords,int iFrame,int iObj)31 static inline int  Abc_InfoGet2Bits( Vec_Int_t * vData, int nWords, int iFrame, int iObj )
32 {
33     unsigned * pInfo = (unsigned *)Vec_IntEntryP( vData, nWords * iFrame );
34     return 3 & (pInfo[iObj >> 4] >> ((iObj & 15) << 1));
35 }
Abc_InfoSet2Bits(Vec_Int_t * vData,int nWords,int iFrame,int iObj,int Value)36 static inline void Abc_InfoSet2Bits( Vec_Int_t * vData, int nWords, int iFrame, int iObj, int Value )
37 {
38     unsigned * pInfo = (unsigned *)Vec_IntEntryP( vData, nWords * iFrame );
39     Value ^= (3 & (pInfo[iObj >> 4] >> ((iObj & 15) << 1)));
40     pInfo[iObj >> 4] ^= (Value << ((iObj & 15) << 1));
41 }
Abc_InfoAdd2Bits(Vec_Int_t * vData,int nWords,int iFrame,int iObj,int Value)42 static inline void Abc_InfoAdd2Bits( Vec_Int_t * vData, int nWords, int iFrame, int iObj, int Value )
43 {
44     unsigned * pInfo = (unsigned *)Vec_IntEntryP( vData, nWords * iFrame );
45     pInfo[iObj >> 4] |= (Value << ((iObj & 15) << 1));
46 }
47 
Gia_ManGetTwo(Gia_Man_t * p,int iFrame,Gia_Obj_t * pObj)48 static inline int  Gia_ManGetTwo( Gia_Man_t * p, int iFrame, Gia_Obj_t * pObj )              { return Abc_InfoGet2Bits( p->vTruths, p->nTtWords, iFrame, Gia_ObjId(p, pObj) ); }
Gia_ManSetTwo(Gia_Man_t * p,int iFrame,Gia_Obj_t * pObj,int Value)49 static inline void Gia_ManSetTwo( Gia_Man_t * p, int iFrame, Gia_Obj_t * pObj, int Value )   { Abc_InfoSet2Bits( p->vTruths, p->nTtWords, iFrame, Gia_ObjId(p, pObj), Value ); }
Gia_ManAddTwo(Gia_Man_t * p,int iFrame,Gia_Obj_t * pObj,int Value)50 static inline void Gia_ManAddTwo( Gia_Man_t * p, int iFrame, Gia_Obj_t * pObj, int Value )   { Abc_InfoAdd2Bits( p->vTruths, p->nTtWords, iFrame, Gia_ObjId(p, pObj), Value ); }
51 
52 /*
53     For CEX minimization, all terminals (const0, PI, RO in frame0) have equal priority.
54     For abstraction refinement, all terminals, except PPis, have higher priority.
55 */
56 
57 ////////////////////////////////////////////////////////////////////////
58 ///                     FUNCTION DEFINITIONS                         ///
59 ////////////////////////////////////////////////////////////////////////
60 
61 /**Function*************************************************************
62 
63   Synopsis    [Annotates the unrolling with CEX value/priority.]
64 
65   Description []
66 
67   SideEffects []
68 
69   SeeAlso     []
70 
71 ***********************************************************************/
Gia_ManAnnotateUnrolling(Gia_Man_t * p,Abc_Cex_t * pCex,int fJustMax)72 int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex, int fJustMax )
73 {
74     Gia_Obj_t * pObj, * pObjRi, * pObjRo;
75     int RetValue, f, k, Value, Value0, Value1, iBit;
76     // start storage for internal info
77     assert( p->vTruths == NULL );
78     p->nTtWords = Abc_BitWordNum( 2 * Gia_ManObjNum(p) );
79     p->vTruths  = Vec_IntStart( (pCex->iFrame + 1) * p->nTtWords );
80     // assign values to all objects (const0 and RO in frame0 are assigned 0)
81     Gia_ManCleanMark0(p);
82     for ( f = 0, iBit = pCex->nRegs; f <= pCex->iFrame; f++ )
83     {
84         Gia_ManForEachPi( p, pObj, k )
85             if ( (pObj->fMark0 = Abc_InfoHasBit(pCex->pData, iBit++)) )
86                 Gia_ManAddTwo( p, f, pObj, 1 );
87         Gia_ManForEachAnd( p, pObj, k )
88             if ( (pObj->fMark0 = (Gia_ObjFanin0(pObj)->fMark0 ^ Gia_ObjFaninC0(pObj)) & (Gia_ObjFanin1(pObj)->fMark0 ^ Gia_ObjFaninC1(pObj))) )
89                 Gia_ManAddTwo( p, f, pObj, 1 );
90         Gia_ManForEachCo( p, pObj, k )
91             if ( (pObj->fMark0 = Gia_ObjFanin0(pObj)->fMark0 ^ Gia_ObjFaninC0(pObj)) )
92                 Gia_ManAddTwo( p, f, pObj, 1 );
93         if ( f == pCex->iFrame )
94             break;
95         Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
96             if ( (pObjRo->fMark0 = pObjRi->fMark0) )
97                 Gia_ManAddTwo( p, f+1, pObjRo, 1 );
98     }
99     assert( iBit == pCex->nBits );
100     // check the output value
101     RetValue = Gia_ManPo(p, pCex->iPo)->fMark0;
102     if ( RetValue != 1 )
103         printf( "Counter-example is invalid.\n" );
104     // assign justification to nodes
105     Gia_ManCleanMark0(p);
106     pObj = Gia_ManPo(p, pCex->iPo);
107     pObj->fMark0 = 1;
108     Gia_ManAddTwo( p, pCex->iFrame, pObj, 2 );
109     for ( f = pCex->iFrame; f >= 0; f-- )
110     {
111         // transfer to CO drivers
112         Gia_ManForEachCo( p, pObj, k )
113             if ( (Gia_ObjFanin0(pObj)->fMark0 = pObj->fMark0) )
114             {
115                 pObj->fMark0 = 0;
116                 Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
117             }
118         // compute justification
119         Gia_ManForEachAndReverse( p, pObj, k )
120         {
121             if ( !pObj->fMark0 )
122                 continue;
123             pObj->fMark0 = 0;
124             Value = (1 & Gia_ManGetTwo(p, f, pObj));
125             Value0 = (1 & Gia_ManGetTwo(p, f, Gia_ObjFanin0(pObj))) ^ Gia_ObjFaninC0(pObj);
126             Value1 = (1 & Gia_ManGetTwo(p, f, Gia_ObjFanin1(pObj))) ^ Gia_ObjFaninC1(pObj);
127             if ( Value0 == Value1 )
128             {
129                 assert( Value == (Value0 & Value1) );
130                 if ( fJustMax || Value == 1 )
131                 {
132                     Gia_ObjFanin0(pObj)->fMark0 = Gia_ObjFanin1(pObj)->fMark0 = 1;
133                     Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
134                     Gia_ManAddTwo( p, f, Gia_ObjFanin1(pObj), 2 );
135                 }
136                 else
137                 {
138                     Gia_ObjFanin0(pObj)->fMark0 = 1;
139                     Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
140                 }
141             }
142             else if ( Value0 == 0 )
143             {
144                 assert( Value == 0 );
145                 Gia_ObjFanin0(pObj)->fMark0 = 1;
146                 Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
147             }
148             else if ( Value1 == 0 )
149             {
150                 assert( Value == 0 );
151                 Gia_ObjFanin1(pObj)->fMark0 = 1;
152                 Gia_ManAddTwo( p, f, Gia_ObjFanin1(pObj), 2 );
153             }
154             else assert( 0 );
155         }
156         if ( f == 0 )
157             break;
158         // transfer to RIs
159         Gia_ManForEachPi( p, pObj, k )
160             pObj->fMark0 = 0;
161         Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
162             if ( (pObjRi->fMark0 = pObjRo->fMark0) )
163             {
164                 pObjRo->fMark0 = 0;
165                 Gia_ManAddTwo( p, f-1, pObjRi, 2 );
166             }
167     }
168     Gia_ManCleanMark0(p);
169     return RetValue;
170 }
171 
172 /**Function*************************************************************
173 
174   Synopsis    [Computing AIG characterizing all justifying assignments.]
175 
176   Description [Used in CEX minimization.]
177 
178   SideEffects []
179 
180   SeeAlso     []
181 
182 ***********************************************************************/
Gia_ManCreateUnate(Gia_Man_t * p,Abc_Cex_t * pCex,int iFrame,int nRealPis,int fUseAllObjects)183 Gia_Man_t * Gia_ManCreateUnate( Gia_Man_t * p, Abc_Cex_t * pCex, int iFrame, int nRealPis, int fUseAllObjects )
184 {
185     Gia_Man_t * pNew, * pTemp;
186     Gia_Obj_t * pObj, * pObjRo, * pObjRi;
187     int f, k, Value;
188     assert( iFrame >= 0 && iFrame <= pCex->iFrame );
189     pNew = Gia_ManStart( 1000 );
190     pNew->pName = Abc_UtilStrsav( "unate" );
191     Gia_ManCleanValue( p );
192     // set flop outputs
193     if ( nRealPis < 0 ) // CEX min
194     {
195         Gia_ManForEachRo( p, pObj, k )
196         {
197             if ( fUseAllObjects )
198             {
199                 int Value = Gia_ManAppendCi(pNew);
200                 if ( (Gia_ManGetTwo(p, iFrame, pObj) >> 1) ) // in the path
201                     pObj->Value = Value;
202             }
203             else if ( (Gia_ManGetTwo(p, iFrame, pObj) >> 1) ) // in the path
204                 pObj->Value = Gia_ManAppendCi(pNew);
205         }
206     }
207     else
208     {
209         Gia_ManForEachRo( p, pObj, k )
210             pObj->Value = (Gia_ManGetTwo(p, iFrame, pObj) >> 1);
211     }
212     Gia_ManHashAlloc( pNew );
213     for ( f = iFrame; f <= pCex->iFrame; f++ )
214     {
215 /*
216         printf( "  F%03d ", f );
217         Gia_ManForEachRo( p, pObj, k )
218             printf( "%d", pObj->Value > 0 );
219         printf( "\n" );
220 */
221         // set const0 to const1 if present
222         pObj = Gia_ManConst0(p);
223         pObj->Value = (Gia_ManGetTwo(p, f, pObj) >> 1);
224         // set primary inputs
225         if ( nRealPis < 0 ) // CEX min
226         {
227             Gia_ManForEachPi( p, pObj, k )
228                 pObj->Value = (Gia_ManGetTwo(p, f, pObj) >> 1);
229         }
230         else
231         {
232             Gia_ManForEachPi( p, pObj, k )
233             {
234                 pObj->Value = (Gia_ManGetTwo(p, f, pObj) >> 1);
235                 if ( k >= nRealPis )
236                 {
237                     if ( fUseAllObjects )
238                     {
239                         int Value = Gia_ManAppendCi(pNew);
240                         if ( (Gia_ManGetTwo(p, f, pObj) >> 1) ) // in the path
241                             pObj->Value = Value;
242                     }
243                     else if ( (Gia_ManGetTwo(p, f, pObj) >> 1) ) // in the path
244                         pObj->Value = Gia_ManAppendCi(pNew);
245                 }
246             }
247         }
248         // traverse internal nodes
249         Gia_ManForEachAnd( p, pObj, k )
250         {
251             pObj->Value = 0;
252             Value = Gia_ManGetTwo(p, f, pObj);
253             if ( !(Value >> 1) ) // not in the path
254                 continue;
255             if ( Gia_ObjFanin0(pObj)->Value && Gia_ObjFanin1(pObj)->Value )
256             {
257                 if ( 1 & Gia_ManGetTwo(p, f, pObj) ) // value 1
258                 {
259                     if ( Gia_ObjFanin0(pObj)->Value > 1 && Gia_ObjFanin1(pObj)->Value > 1 )
260                         pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0(pObj)->Value, Gia_ObjFanin1(pObj)->Value );
261                     else if ( Gia_ObjFanin0(pObj)->Value > 1 )
262                         pObj->Value = Gia_ObjFanin0(pObj)->Value;
263                     else if ( Gia_ObjFanin1(pObj)->Value > 1 )
264                         pObj->Value = Gia_ObjFanin1(pObj)->Value;
265                     else
266                         pObj->Value = 1;
267                 }
268                 else // value 0
269                 {
270                     if ( Gia_ObjFanin0(pObj)->Value > 1 && Gia_ObjFanin1(pObj)->Value > 1 )
271                         pObj->Value = Gia_ManHashOr( pNew, Gia_ObjFanin0(pObj)->Value, Gia_ObjFanin1(pObj)->Value );
272                     else if ( Gia_ObjFanin0(pObj)->Value > 1 )
273                         pObj->Value = Gia_ObjFanin0(pObj)->Value;
274                     else if ( Gia_ObjFanin1(pObj)->Value > 1 )
275                         pObj->Value = Gia_ObjFanin1(pObj)->Value;
276                     else
277                         pObj->Value = 1;
278                 }
279             }
280             else if ( Gia_ObjFanin0(pObj)->Value )
281                 pObj->Value = Gia_ObjFanin0(pObj)->Value;
282             else if ( Gia_ObjFanin1(pObj)->Value )
283                 pObj->Value = Gia_ObjFanin1(pObj)->Value;
284             else assert( 0 );
285         }
286         Gia_ManForEachCo( p, pObj, k )
287             pObj->Value = Gia_ObjFanin0(pObj)->Value;
288         if ( f == pCex->iFrame )
289             break;
290         Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
291             pObjRo->Value = pObjRi->Value;
292     }
293     Gia_ManHashStop( pNew );
294     // create primary output
295     pObj = Gia_ManPo(p, pCex->iPo);
296     assert( (Gia_ManGetTwo(p, pCex->iFrame, pObj) >> 1) );
297     assert( pObj->Value );
298     Gia_ManAppendCo( pNew, pObj->Value );
299     // cleanup
300     pNew = Gia_ManCleanup( pTemp = pNew );
301     Gia_ManStop( pTemp );
302     return pNew;
303 }
304 
305 
306 /**Function*************************************************************
307 
308   Synopsis    []
309 
310   Description []
311 
312   SideEffects []
313 
314   SeeAlso     []
315 
316 ***********************************************************************/
Gia_ManCexMin(Gia_Man_t * p,Abc_Cex_t * pCex,int iFrameStart,int nRealPis,int fJustMax,int fUseAll,int fVerbose)317 Abc_Cex_t * Gia_ManCexMin( Gia_Man_t * p, Abc_Cex_t * pCex, int iFrameStart, int nRealPis, int fJustMax, int fUseAll, int fVerbose )
318 {
319     Gia_Man_t * pNew;
320     int f, RetValue;
321     // check CEX
322     assert( pCex->nPis == Gia_ManPiNum(p) );
323 //    assert( pCex->nRegs == Gia_ManRegNum(p) );
324     assert( pCex->iPo < Gia_ManPoNum(p) );
325     // check frames
326     assert( iFrameStart >= 0 && iFrameStart <= pCex->iFrame );
327     // check primary inputs
328     assert( nRealPis < Gia_ManPiNum(p) );
329     // prepare
330     RetValue = Gia_ManAnnotateUnrolling( p, pCex, fJustMax );
331     if ( nRealPis >= 0 ) // refinement
332     {
333         pNew = Gia_ManCreateUnate( p, pCex, iFrameStart, nRealPis, fUseAll );
334         printf( "%3d : ", iFrameStart );
335         Gia_ManPrintStats( pNew, NULL );
336         if ( fVerbose )
337             Gia_AigerWrite( pNew, "temp.aig", 0, 0, 0 );
338         Gia_ManStop( pNew );
339     }
340     else // CEX min
341     {
342         for ( f = pCex->iFrame; f >= iFrameStart; f-- )
343         {
344             pNew = Gia_ManCreateUnate( p, pCex, f, -1, fUseAll );
345             printf( "%3d : ", f );
346             Gia_ManPrintStats( pNew, NULL );
347             if ( fVerbose )
348                 Gia_AigerWrite( pNew, "temp.aig", 0, 0, 0 );
349             Gia_ManStop( pNew );
350         }
351     }
352     Vec_IntFreeP( &p->vTruths );
353     p->nTtWords = 0;
354     return NULL;
355 }
356 
357 ////////////////////////////////////////////////////////////////////////
358 ///                       END OF FILE                                ///
359 ////////////////////////////////////////////////////////////////////////
360 
361 
362 ABC_NAMESPACE_IMPL_END
363 
364