cecCec.c 13.8 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6
/**CFile****************************************************************

  FileName    [cecCec.c]

  SystemName  [ABC: Logic synthesis and verification system.]

Alan Mishchenko committed
7
  PackageName [Combinational equivalence checking.]
Alan Mishchenko committed
8 9 10 11 12 13 14 15 16 17 18 19 20 21

  Synopsis    [Integrated combinatinal equivalence checker.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "cecInt.h"
22 23
#include "proof/fra/fra.h"
#include "aig/gia/giaAig.h"
Alan Mishchenko committed
24

25 26 27
ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    [Saves the input pattern with the given number.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cec_ManTransformPattern( Gia_Man_t * p, int iOut, int * pValues )
{
    int i;
    assert( p->pCexComb == NULL );
51
    p->pCexComb = Abc_CexAlloc( 0, Gia_ManCiNum(p), 1 );
Alan Mishchenko committed
52 53
    p->pCexComb->iPo = iOut;
    for ( i = 0; i < Gia_ManCiNum(p); i++ )
54
        if ( pValues && pValues[i] )
55
            Abc_InfoSetBit( p->pCexComb->pData, i );
Alan Mishchenko committed
56 57 58 59 60 61 62 63 64 65 66 67 68
}

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

  Synopsis    [Interface to the old CEC engine]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
69
int Cec_ManVerifyOld( Gia_Man_t * pMiter, int fVerbose, int * piOutFail )
Alan Mishchenko committed
70
{
71
//    extern int Fra_FraigCec( Aig_Man_t ** ppAig, int nConfLimit, int fVerbose );
Alan Mishchenko committed
72 73
    extern int Ssw_SecCexResimulate( Aig_Man_t * p, int * pModel, int * pnOutputs );
    Gia_Man_t * pTemp = Gia_ManTransformMiter( pMiter );
Alan Mishchenko committed
74
    Aig_Man_t * pMiterCec = Gia_ManToAig( pTemp, 0 );
75 76
    int RetValue, iOut, nOuts;
    clock_t clkTotal = clock();
77 78
    if ( piOutFail )
        *piOutFail = -1;
Alan Mishchenko committed
79 80
    Gia_ManStop( pTemp );
    // run CEC on this miter
81
    RetValue = Fra_FraigCec( &pMiterCec, 10000000, fVerbose );
Alan Mishchenko committed
82 83 84
    // report the miter
    if ( RetValue == 1 )
    {
85 86
        Abc_Print( 1, "Networks are equivalent.   " );
Abc_PrintTime( 1, "Time", clock() - clkTotal );
Alan Mishchenko committed
87 88 89
    }
    else if ( RetValue == 0 )
    {
90 91
        Abc_Print( 1, "Networks are NOT EQUIVALENT.   " );
Abc_PrintTime( 1, "Time", clock() - clkTotal );
Alan Mishchenko committed
92
        if ( pMiterCec->pData == NULL )
93
            Abc_Print( 1, "Counter-example is not available.\n" );
Alan Mishchenko committed
94 95
        else
        {
96
            iOut = Ssw_SecCexResimulate( pMiterCec, (int *)pMiterCec->pData, &nOuts );
Alan Mishchenko committed
97
            if ( iOut == -1 )
98
                Abc_Print( 1, "Counter-example verification has failed.\n" );
Alan Mishchenko committed
99 100
            else 
            {
101
//                Aig_Obj_t * pObj = Aig_ManCo(pMiterCec, iOut);
102 103 104 105 106 107 108
//                Aig_Obj_t * pFan = Aig_ObjFanin0(pObj);
                Abc_Print( 1, "Primary output %d has failed", iOut );
                if ( nOuts-1 >= 0 )
                    Abc_Print( 1, ", along with other %d incorrect outputs", nOuts-1 );
                Abc_Print( 1, ".\n" );
                if ( piOutFail )
                    *piOutFail = iOut;
Alan Mishchenko committed
109
            }
110
            Cec_ManTransformPattern( pMiter, iOut, (int *)pMiterCec->pData );
Alan Mishchenko committed
111 112 113 114
        }
    }
    else
    {
115 116
        Abc_Print( 1, "Networks are UNDECIDED.   " );
Abc_PrintTime( 1, "Time", clock() - clkTotal );
Alan Mishchenko committed
117 118 119 120 121 122 123 124
    }
    fflush( stdout );
    Aig_ManStop( pMiterCec );
    return RetValue;
}

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

125 126 127 128 129 130 131 132 133 134 135 136 137
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cec_ManHandleSpecialCases( Gia_Man_t * p, Cec_ParCec_t * pPars )
{
    Gia_Obj_t * pObj1, * pObj2;
    Gia_Obj_t * pDri1, * pDri2;
138 139
    int i;
    clock_t clk = clock();
140 141 142 143 144 145 146 147
    Gia_ManSetPhase( p );
    Gia_ManForEachPo( p, pObj1, i )
    {
        pObj2 = Gia_ManPo( p, ++i );
        // check if they different on all-0 pattern
        // (for example, when they have the same driver but complemented)
        if ( Gia_ObjPhase(pObj1) != Gia_ObjPhase(pObj2) )
        {
Alan Mishchenko committed
148
            Abc_Print( 1, "Networks are NOT EQUIVALENT. Outputs %d trivially differ (different phase).  ", i/2 );
149 150 151 152 153 154 155 156 157 158 159
            Abc_PrintTime( 1, "Time", clock() - clk );
            pPars->iOutFail = i/2;
            Cec_ManTransformPattern( p, i/2, NULL );
            return 0;
        }
        // get the drivers
        pDri1 = Gia_ObjFanin0(pObj1);
        pDri2 = Gia_ObjFanin0(pObj2);
        // drivers are different PIs
        if ( Gia_ObjIsPi(p, pDri1) && Gia_ObjIsPi(p, pDri2) && pDri1 != pDri2 )
        {
Alan Mishchenko committed
160
            Abc_Print( 1, "Networks are NOT EQUIVALENT. Outputs %d trivially differ (different PIs).  ", i/2 );
161 162 163 164 165 166 167 168 169 170 171 172
            Abc_PrintTime( 1, "Time", clock() - clk );
            pPars->iOutFail = i/2;
            Cec_ManTransformPattern( p, i/2, NULL );
            // if their compl attributes are the same - one should be complemented
            assert( Gia_ObjFaninC0(pObj1) == Gia_ObjFaninC0(pObj2) );
            Abc_InfoSetBit( p->pCexComb->pData, Gia_ObjCioId(pDri1) );
            return 0;
        }
        // one of the drivers is a PI; another is a constant 0
        if ( (Gia_ObjIsPi(p, pDri1) && Gia_ObjIsConst0(pDri2)) || 
             (Gia_ObjIsPi(p, pDri2) && Gia_ObjIsConst0(pDri1)) )
        {
Alan Mishchenko committed
173
            Abc_Print( 1, "Networks are NOT EQUIVALENT. Outputs %d trivially differ (PI vs. constant).  ", i/2 );
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
            Abc_PrintTime( 1, "Time", clock() - clk );
            pPars->iOutFail = i/2;
            Cec_ManTransformPattern( p, i/2, NULL );
            // the compl attributes are the same - the PI should be complemented
            assert( Gia_ObjFaninC0(pObj1) == Gia_ObjFaninC0(pObj2) );
            if ( Gia_ObjIsPi(p, pDri1) )
                Abc_InfoSetBit( p->pCexComb->pData, Gia_ObjCioId(pDri1) );
            else
                Abc_InfoSetBit( p->pCexComb->pData, Gia_ObjCioId(pDri2) );
            return 0;
        }
    }
    if ( Gia_ManAndNum(p) == 0 )
    {
        Abc_Print( 1, "Networks are equivalent.  " );
        Abc_PrintTime( 1, "Time", clock() - clk );
        return 1;
    }
    return -1;
}

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

Alan Mishchenko committed
197 198 199 200 201 202 203 204 205
  Synopsis    [New CEC engine.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
206
int Cec_ManVerify( Gia_Man_t * pInit, Cec_ParCec_t * pPars )
Alan Mishchenko committed
207
{
208
    int fDumpUndecided = 0;
Alan Mishchenko committed
209
    Cec_ParFra_t ParsFra, * pParsFra = &ParsFra;
210
    Gia_Man_t * p, * pNew;
211 212 213
    int RetValue;
    clock_t clk = clock();
    clock_t clkTotal = clock();
214 215 216 217 218 219 220
    // consider special cases:
    // 1) (SAT) a pair of POs have different value under all-0 pattern
    // 2) (SAT) a pair of POs has different PI/Const drivers
    // 3) (UNSAT) 1-2 do not hold and there is no nodes
    RetValue = Cec_ManHandleSpecialCases( pInit, pPars );
    if ( RetValue == 0 || RetValue == 1 )
        return RetValue;
221 222 223 224 225
    // preprocess 
    p = Gia_ManDup( pInit );
    Gia_ManEquivFixOutputPairs( p );
    p = Gia_ManCleanup( pNew = p );
    Gia_ManStop( pNew );
Alan Mishchenko committed
226 227
    // sweep for equivalences
    Cec_ManFraSetDefaultParams( pParsFra );
Alan Mishchenko committed
228
    pParsFra->nItersMax    = 1000;
Alan Mishchenko committed
229 230 231 232
    pParsFra->nBTLimit     = pPars->nBTLimit;
    pParsFra->TimeLimit    = pPars->TimeLimit;
    pParsFra->fVerbose     = pPars->fVerbose;
    pParsFra->fCheckMiter  = 1;
Alan Mishchenko committed
233
    pParsFra->fDualOut     = 1;
Alan Mishchenko committed
234
    pNew = Cec_ManSatSweeping( p, pParsFra );
235 236 237 238 239 240
    pPars->iOutFail = pParsFra->iOutFail;
    // update
    pInit->pCexComb = p->pCexComb; p->pCexComb = NULL;
    Gia_ManStop( p );
    p = pInit;
    // continue
Alan Mishchenko committed
241 242
    if ( pNew == NULL )
    {
243 244
        if ( p->pCexComb != NULL )
        {
245
            if ( p->pCexComb && !Gia_ManVerifyCex( p, p->pCexComb, 1 ) )
246 247 248 249 250 251 252 253 254 255
                Abc_Print( 1, "Counter-example simulation has failed.\n" );
            Abc_Print( 1, "Networks are NOT EQUIVALENT.  " );
            Abc_PrintTime( 1, "Time", clock() - clk );
            return 0;
        }
        p = Gia_ManDup( pInit );
        Gia_ManEquivFixOutputPairs( p );
        p = Gia_ManCleanup( pNew = p );
        Gia_ManStop( pNew );
        pNew = p;
Alan Mishchenko committed
256
    }
257 258
    if ( pPars->fVerbose )
    {
259 260
        Abc_Print( 1, "Networks are UNDECIDED after the new CEC engine.  " );
        Abc_PrintTime( 1, "Time", clock() - clk );
261
    }
Alan Mishchenko committed
262 263
    if ( fDumpUndecided )
    {
264 265
        ABC_FREE( pNew->pReprs );
        ABC_FREE( pNew->pNexts );
Alan Mishchenko committed
266
        Gia_WriteAiger( pNew, "gia_cec_undecided.aig", 0, 0 );
267
        Abc_Print( 1, "The result is written into file \"%s\".\n", "gia_cec_undecided.aig" );
Alan Mishchenko committed
268
    }
269
    if ( pPars->TimeLimit && (clock() - clkTotal)/CLOCKS_PER_SEC >= pPars->TimeLimit )
Alan Mishchenko committed
270 271 272 273 274
    {
        Gia_ManStop( pNew );
        return -1;
    }
    // call other solver
275
    if ( pPars->fVerbose )
276
        Abc_Print( 1, "Calling the old CEC engine.\n" );
Alan Mishchenko committed
277
    fflush( stdout );
278
    RetValue = Cec_ManVerifyOld( pNew, pPars->fVerbose, &pPars->iOutFail );
Alan Mishchenko committed
279
    p->pCexComb = pNew->pCexComb; pNew->pCexComb = NULL;
280
    if ( p->pCexComb && !Gia_ManVerifyCex( p, p->pCexComb, 1 ) )
281
        Abc_Print( 1, "Counter-example simulation has failed.\n" );
Alan Mishchenko committed
282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303
    Gia_ManStop( pNew );
    return RetValue;
}

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

  Synopsis    [New CEC engine applied to two circuits.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cec_ManVerifyTwo( Gia_Man_t * p0, Gia_Man_t * p1, int fVerbose )
{
    Cec_ParCec_t ParsCec, * pPars = &ParsCec;
    Gia_Man_t * pMiter;
    int RetValue;
    Cec_ManCecSetDefaultParams( pPars );
    pPars->fVerbose = fVerbose;
Alan Mishchenko committed
304
    pMiter = Gia_ManMiter( p0, p1, 1, 0, pPars->fVerbose );
Alan Mishchenko committed
305 306 307 308 309 310 311 312 313 314 315 316 317 318
    if ( pMiter == NULL )
        return -1;
    RetValue = Cec_ManVerify( pMiter, pPars );
    p0->pCexComb = pMiter->pCexComb; pMiter->pCexComb = NULL;
    Gia_ManStop( pMiter );
    return RetValue;
}

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

  Synopsis    [New CEC engine applied to two circuits.]

  Description [Returns 1 if equivalent, 0 if counter-example, -1 if undecided.
  Counter-example is returned in the first manager as pAig0->pSeqModel.
319
  The format is given in Abc_Cex_t (file "abc\src\aig\gia\gia.h").]
Alan Mishchenko committed
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cec_ManVerifyTwoAigs( Aig_Man_t * pAig0, Aig_Man_t * pAig1, int fVerbose )
{
    Gia_Man_t * p0, * p1, * pTemp;
    int RetValue;

    p0 = Gia_ManFromAig( pAig0 );
    p0 = Gia_ManCleanup( pTemp = p0 );
    Gia_ManStop( pTemp );

    p1 = Gia_ManFromAig( pAig1 );
    p1 = Gia_ManCleanup( pTemp = p1 );
    Gia_ManStop( pTemp );

    RetValue = Cec_ManVerifyTwo( p0, p1, fVerbose );
    pAig0->pSeqModel = p0->pCexComb; p0->pCexComb = NULL;
    Gia_ManStop( p0 );
    Gia_ManStop( p1 );
    return RetValue;
}

Alan Mishchenko committed
346 347 348 349 350 351 352 353 354 355 356
/**Function*************************************************************

  Synopsis    [Implementation of new signal correspodence.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382
Aig_Man_t * Cec_LatchCorrespondence( Aig_Man_t * pAig, int nConfs, int fUseCSat )
{
    Gia_Man_t * pGia;
    Cec_ParCor_t CorPars, * pCorPars = &CorPars;
    Cec_ManCorSetDefaultParams( pCorPars );
    pCorPars->fLatchCorr = 1;
    pCorPars->fUseCSat   = fUseCSat;
    pCorPars->nBTLimit   = nConfs;
    pGia = Gia_ManFromAigSimple( pAig );
    Cec_ManLSCorrespondenceClasses( pGia, pCorPars );
    Gia_ManReprToAigRepr( pAig, pGia );
    Gia_ManStop( pGia );
    return Aig_ManDupSimple( pAig );
}

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

  Synopsis    [Implementation of new signal correspodence.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
383 384 385 386 387 388 389 390 391 392 393 394 395 396
Aig_Man_t * Cec_SignalCorrespondence( Aig_Man_t * pAig, int nConfs, int fUseCSat )
{
    Gia_Man_t * pGia;
    Cec_ParCor_t CorPars, * pCorPars = &CorPars;
    Cec_ManCorSetDefaultParams( pCorPars );
    pCorPars->fUseCSat  = fUseCSat;
    pCorPars->nBTLimit  = nConfs;
    pGia = Gia_ManFromAigSimple( pAig );
    Cec_ManLSCorrespondenceClasses( pGia, pCorPars );
    Gia_ManReprToAigRepr( pAig, pGia );
    Gia_ManStop( pGia );
    return Aig_ManDupSimple( pAig );
}

Alan Mishchenko committed
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412
/**Function*************************************************************

  Synopsis    [Implementation of fraiging.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Aig_Man_t * Cec_FraigCombinational( Aig_Man_t * pAig, int nConfs, int fVerbose )
{
    Gia_Man_t * pGia;
    Cec_ParFra_t FraPars, * pFraPars = &FraPars;
    Cec_ManFraSetDefaultParams( pFraPars );
413
    pFraPars->fSatSweeping = 1;
Alan Mishchenko committed
414 415 416 417 418 419 420 421 422
    pFraPars->nBTLimit  = nConfs;
    pFraPars->nItersMax = 20;
    pFraPars->fVerbose  = fVerbose;
    pGia = Gia_ManFromAigSimple( pAig );
    Cec_ManSatSweeping( pGia, pFraPars );
    Gia_ManReprToAigRepr( pAig, pGia );
    Gia_ManStop( pGia );
    return Aig_ManDupSimple( pAig );
}
Alan Mishchenko committed
423

Alan Mishchenko committed
424 425 426 427 428
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


429 430
ABC_NAMESPACE_IMPL_END