Started CEX minimization procedure.

2 files changed, 306 insertions, 26 deletions

diff --git a/src/aig/gia/giaCexMin.c b/src/aig/gia/giaCexMin.c
index d460c1e7..4c949d11 100644
--- a/src/aig/gia/giaCexMin.c
+++ b/src/aig/gia/giaCexMin.c
@@ -44,9 +44,9 @@ static inline void Abc_InfoAdd2Bits( Vec_Int_t * vData, int nWords, int iFrame,
     pInfo[iObj >> 4] |= (Value << ((iObj & 15) << 1));
 }
 
-static inline int  Gia_ManGetTwo( Gia_Man_t * p, int iFrame, int iObj )              { return Abc_InfoGet2Bits( p->vTruths, p->nTtWords, iFrame, iObj ); }
-static inline void Gia_ManSetTwo( Gia_Man_t * p, int iFrame, int iObj, int Value )   { Abc_InfoSet2Bits( p->vTruths, p->nTtWords, iFrame, iObj, Value ); }
-static inline void Gia_ManAddTwo( Gia_Man_t * p, int iFrame, int iObj, int Value )   { Abc_InfoAdd2Bits( p->vTruths, p->nTtWords, iFrame, iObj, Value ); }
+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) ); }
+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 ); }
+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 ); }
 
 /*
     For CEX minimization, all terminals (const0, PI, RO in frame0) have equal priority.
@@ -68,10 +68,10 @@ static inline void Gia_ManAddTwo( Gia_Man_t * p, int iFrame, int iObj, int Value
   SeeAlso     []
 
 ***********************************************************************/
-int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex )
+int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex, int fJustMax )
 {
     Gia_Obj_t * pObj, * pObjRi, * pObjRo;
-    int RetValue, f, k, Value0, Value1, iBit;
+    int RetValue, f, k, Value, Value0, Value1, iBit;
     // start storage for internal info
     assert( p->vTruths == NULL );
     p->nTtWords = Abc_BitWordNum( 2 * Gia_ManObjNum(p) );
@@ -82,18 +82,18 @@ int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex )
     {
         Gia_ManForEachPi( p, pObj, k )
             if ( (pObj->fMark0 = Abc_InfoHasBit(pCex->pData, iBit++)) )
-                Gia_ManAddTwo( p, f, Gia_ObjId(p, pObj), 1 );
+                Gia_ManAddTwo( p, f, pObj, 1 );
         Gia_ManForEachAnd( p, pObj, k )
             if ( (pObj->fMark0 = (Gia_ObjFanin0(pObj)->fMark0 ^ Gia_ObjFaninC0(pObj)) & (Gia_ObjFanin1(pObj)->fMark0 ^ Gia_ObjFaninC1(pObj))) )
-                Gia_ManAddTwo( p, f, k, 1 );
+                Gia_ManAddTwo( p, f, pObj, 1 );
         Gia_ManForEachCo( p, pObj, k )
             if ( (pObj->fMark0 = Gia_ObjFanin0(pObj)->fMark0 ^ Gia_ObjFaninC0(pObj)) )
-                Gia_ManAddTwo( p, f, Gia_ObjId(p, pObj), 1 );
+                Gia_ManAddTwo( p, f, pObj, 1 );
         if ( f == pCex->iFrame )
             break;
         Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
             if ( (pObjRo->fMark0 = pObjRi->fMark0) )
-                Gia_ManAddTwo( p, f+1, Gia_ObjId(p, pObjRo), 1 );
+                Gia_ManAddTwo( p, f+1, pObjRo, 1 );
     }
     assert( iBit == pCex->nBits );
     // check the output value
@@ -104,46 +104,65 @@ int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex )
     Gia_ManCleanMark0(p);
     pObj = Gia_ManPo(p, pCex->iPo);
     pObj->fMark0 = 1;
-    Gia_ManAddTwo( p, pCex->iFrame, Gia_ObjFaninId0(pObj, k), 2 );
+    Gia_ManAddTwo( p, pCex->iFrame, pObj, 2 );
     for ( f = pCex->iFrame; f >= 0; f-- )
     {
         // transfer to CO drivers
         Gia_ManForEachCo( p, pObj, k )
             if ( (Gia_ObjFanin0(pObj)->fMark0 = pObj->fMark0) )
-                Gia_ManAddTwo( p, f, Gia_ObjFaninId0p(p, Gia_ObjFanin0(pObj)), 2 );
+            {
+                pObj->fMark0 = 0;
+                Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
+            }
         // compute justification
         Gia_ManForEachAndReverse( p, pObj, k )
         {
-            if ( !pObj->fMark0 ) continue;
-            Value0 = (1 & Gia_ManGetTwo(p, f, Gia_ObjFaninId0(pObj, k))) ^ Gia_ObjFaninC0(pObj);
-            Value1 = (1 & Gia_ManGetTwo(p, f, Gia_ObjFaninId1(pObj, k))) ^ Gia_ObjFaninC1(pObj);
+            if ( !pObj->fMark0 ) 
+                continue;
+            pObj->fMark0 = 0;
+            Value = (1 & Gia_ManGetTwo(p, f, pObj));
+            Value0 = (1 & Gia_ManGetTwo(p, f, Gia_ObjFanin0(pObj))) ^ Gia_ObjFaninC0(pObj);
+            Value1 = (1 & Gia_ManGetTwo(p, f, Gia_ObjFanin1(pObj))) ^ Gia_ObjFaninC1(pObj);
             if ( Value0 == Value1 )
             {
-                Gia_ObjFanin0(pObj)->fMark0 = Gia_ObjFanin1(pObj)->fMark0 = 1;
-                Gia_ManAddTwo( p, f, Gia_ObjFaninId0(pObj, k), 2 );
-                Gia_ManAddTwo( p, f, Gia_ObjFaninId1(pObj, k), 2 );
+                assert( Value == (Value0 & Value1) );
+                if ( fJustMax || Value == 1 )
+                {
+                    Gia_ObjFanin0(pObj)->fMark0 = Gia_ObjFanin1(pObj)->fMark0 = 1;
+                    Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
+                    Gia_ManAddTwo( p, f, Gia_ObjFanin1(pObj), 2 );
+                }
+                else
+                {
+                    Gia_ObjFanin0(pObj)->fMark0 = 1;
+                    Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
+                }
             }
             else if ( Value0 == 0 )
             {
+                assert( Value == 0 );
                 Gia_ObjFanin0(pObj)->fMark0 = 1;
-                Gia_ManAddTwo( p, f, Gia_ObjFaninId0(pObj, k), 2 );
+                Gia_ManAddTwo( p, f, Gia_ObjFanin0(pObj), 2 );
             }
             else if ( Value1 == 0 )
             {
+                assert( Value == 0 );
                 Gia_ObjFanin1(pObj)->fMark0 = 1;
-                Gia_ManAddTwo( p, f, Gia_ObjFaninId1(pObj, k), 2 );
+                Gia_ManAddTwo( p, f, Gia_ObjFanin1(pObj), 2 );
             }
             else assert( 0 );
         }
         if ( f == 0 )
             break;
-        // clean COs
-        Gia_ManForEachCo( p, pObj, k )
-            pObj->fMark0 = 0;
         // transfer to RIs
+        Gia_ManForEachPi( p, pObj, k )
+            pObj->fMark0 = 0;
         Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
             if ( (pObjRi->fMark0 = pObjRo->fMark0) )
-                Gia_ManAddTwo( p, f-1, Gia_ObjId(p, pObjRi), 2 );
+            {
+                pObjRo->fMark0 = 0;
+                Gia_ManAddTwo( p, f-1, pObjRi, 2 );
+            }
     }
     Gia_ManCleanMark0(p);
     return RetValue;
@@ -151,6 +170,140 @@ int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex )
 
 /**Function*************************************************************
 
+  Synopsis    [Computing AIG characterizing all justifying assignments.]
+
+  Description [Used in CEX minimization.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManCreateUnate( Gia_Man_t * p, Abc_Cex_t * pCex, int iFrame, int nRealPis, int fUseAllObjects )
+{
+    Gia_Man_t * pNew, * pTemp;
+    Gia_Obj_t * pObj, * pObjRo, * pObjRi;
+    int f, k, Value;
+    assert( iFrame >= 0 && iFrame <= pCex->iFrame );
+    pNew = Gia_ManStart( 1000 );
+    pNew->pName = Abc_UtilStrsav( "unate" );
+    Gia_ManCleanValue( p );
+    // set flop outputs
+    if ( nRealPis < 0 ) // CEX min
+    {
+        Gia_ManForEachRo( p, pObj, k )
+        {
+            if ( fUseAllObjects )
+            {
+                int Value = Gia_ManAppendCi(pNew);
+                if ( (Gia_ManGetTwo(p, iFrame, pObj) >> 1) ) // in the path
+                    pObj->Value = Value;
+            }
+            else if ( (Gia_ManGetTwo(p, iFrame, pObj) >> 1) ) // in the path
+                pObj->Value = Gia_ManAppendCi(pNew);
+        }
+    }
+    else
+    {
+        Gia_ManForEachRo( p, pObj, k )
+            pObj->Value = (Gia_ManGetTwo(p, iFrame, pObj) >> 1);
+    }
+    Gia_ManHashAlloc( pNew );
+    for ( f = iFrame; f <= pCex->iFrame; f++ )
+    {
+/*
+        printf( "  F%03d ", f );
+        Gia_ManForEachRo( p, pObj, k )
+            printf( "%d", pObj->Value > 0 );
+        printf( "\n" );
+*/
+        // set const0 to const1 if present
+        pObj = Gia_ManConst0(p);
+        pObj->Value = (Gia_ManGetTwo(p, f, pObj) >> 1);
+        // set primary inputs 
+        if ( nRealPis < 0 ) // CEX min
+        {
+            Gia_ManForEachPi( p, pObj, k )
+                pObj->Value = (Gia_ManGetTwo(p, f, pObj) >> 1);
+        }
+        else
+        {
+            Gia_ManForEachPi( p, pObj, k )
+            {
+                pObj->Value = (Gia_ManGetTwo(p, f, pObj) >> 1);
+                if ( k >= nRealPis )
+                {
+                    if ( fUseAllObjects )
+                    {
+                        int Value = Gia_ManAppendCi(pNew);
+                        if ( (Gia_ManGetTwo(p, f, pObj) >> 1) ) // in the path
+                            pObj->Value = Value;
+                    }
+                    else if ( (Gia_ManGetTwo(p, f, pObj) >> 1) ) // in the path
+                        pObj->Value = Gia_ManAppendCi(pNew);
+                }
+            }
+        }
+        // traverse internal nodes
+        Gia_ManForEachAnd( p, pObj, k )
+        { 
+            pObj->Value = 0;
+            Value = Gia_ManGetTwo(p, f, pObj);
+            if ( !(Value >> 1) ) // not in the path
+                continue;
+            if ( Gia_ObjFanin0(pObj)->Value && Gia_ObjFanin1(pObj)->Value )
+            {
+                if ( 1 & Gia_ManGetTwo(p, f, pObj) ) // value 1
+                {
+                    if ( Gia_ObjFanin0(pObj)->Value > 1 && Gia_ObjFanin1(pObj)->Value > 1 )
+                        pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0(pObj)->Value, Gia_ObjFanin1(pObj)->Value );
+                    else if ( Gia_ObjFanin0(pObj)->Value > 1 )
+                        pObj->Value = Gia_ObjFanin0(pObj)->Value;
+                    else if ( Gia_ObjFanin1(pObj)->Value > 1 )
+                        pObj->Value = Gia_ObjFanin1(pObj)->Value;
+                    else 
+                        pObj->Value = 1;
+                }
+                else // value 0
+                {
+                    if ( Gia_ObjFanin0(pObj)->Value > 1 && Gia_ObjFanin1(pObj)->Value > 1 )
+                        pObj->Value = Gia_ManHashOr( pNew, Gia_ObjFanin0(pObj)->Value, Gia_ObjFanin1(pObj)->Value );
+                    else if ( Gia_ObjFanin0(pObj)->Value > 1 )
+                        pObj->Value = Gia_ObjFanin0(pObj)->Value;
+                    else if ( Gia_ObjFanin1(pObj)->Value > 1 )
+                        pObj->Value = Gia_ObjFanin1(pObj)->Value;
+                    else 
+                        pObj->Value = 1;
+                }
+            }
+            else if ( Gia_ObjFanin0(pObj)->Value )
+                pObj->Value = Gia_ObjFanin0(pObj)->Value;
+            else if ( Gia_ObjFanin1(pObj)->Value )
+                pObj->Value = Gia_ObjFanin1(pObj)->Value;
+            else assert( 0 );
+        }
+        Gia_ManForEachCo( p, pObj, k )
+            pObj->Value = Gia_ObjFanin0(pObj)->Value;
+        if ( f == pCex->iFrame )
+            break;
+        Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
+            pObjRo->Value = pObjRi->Value;
+    }
+    Gia_ManHashStop( pNew );
+    // create primary output
+    pObj = Gia_ManPo(p, pCex->iPo);
+    assert( (Gia_ManGetTwo(p, pCex->iFrame, pObj) >> 1) );
+    assert( pObj->Value );
+    Gia_ManAppendCo( pNew, pObj->Value );
+    // cleanup
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    return pNew;
+}
+
+
+/**Function*************************************************************
+
   Synopsis    []
 
   Description []
@@ -160,12 +313,43 @@ int Gia_ManAnnotateUnrolling( Gia_Man_t * p, Abc_Cex_t * pCex )
   SeeAlso     []
 
 ***********************************************************************/
-Abc_Cex_t * Gia_ManCexMin( Gia_Man_t * p, Abc_Cex_t * pCex )
+Abc_Cex_t * Gia_ManCexMin( Gia_Man_t * p, Abc_Cex_t * pCex, int iFrameStart, int nRealPis, int fJustMax, int fUseAll, int fVerbose )
 {
+    Gia_Man_t * pNew;
+    int f, RetValue;
+    // check CEX
     assert( pCex->nPis == Gia_ManPiNum(p) );
-    assert( pCex->nRegs == Gia_ManRegNum(p) );
+//    assert( pCex->nRegs == Gia_ManRegNum(p) );
     assert( pCex->iPo < Gia_ManPoNum(p) );
-
+    // check frames
+    assert( iFrameStart >= 0 && iFrameStart <= pCex->iFrame );
+    // check primary inputs
+    assert( nRealPis < Gia_ManPiNum(p) );
+    // prepare
+    RetValue = Gia_ManAnnotateUnrolling( p, pCex, fJustMax );
+    if ( nRealPis >= 0 ) // refinement
+    {
+        pNew = Gia_ManCreateUnate( p, pCex, iFrameStart, nRealPis, fUseAll );
+        printf( "%3d : ", iFrameStart );
+        Gia_ManPrintStats( pNew, 0, 0 );
+        if ( fVerbose )
+            Gia_WriteAiger( pNew, "temp.aig", 0, 0 );
+        Gia_ManStop( pNew );
+    }
+    else // CEX min
+    {
+        for ( f = pCex->iFrame; f >= iFrameStart; f-- )
+        {
+            pNew = Gia_ManCreateUnate( p, pCex, f, -1, fUseAll );
+            printf( "%3d : ", f );
+            Gia_ManPrintStats( pNew, 0, 0 );
+            if ( fVerbose )
+                Gia_WriteAiger( pNew, "temp.aig", 0, 0 );
+            Gia_ManStop( pNew );
+        }
+    }
+    Vec_IntFreeP( &p->vTruths );
+    p->nTtWords = 0;
     return NULL;
 }
 
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 3d293ba5..2eafd917 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -376,6 +376,7 @@ static int Abc_CommandAbc9ReachN             ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandAbc9ReachY             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Undo               ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Iso                ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandAbc9CexMin             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Test               ( Abc_Frame_t * pAbc, int argc, char ** argv );
 
 static int Abc_CommandAbcTestNew             ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -836,6 +837,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "ABC9",         "&reachy",       Abc_CommandAbc9ReachY,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&undo",         Abc_CommandAbc9Undo,         0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&iso",          Abc_CommandAbc9Iso,          0 );
+    Cmd_CommandAdd( pAbc, "ABC9",         "&cexmin",       Abc_CommandAbc9CexMin,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&test",         Abc_CommandAbc9Test,         0 );
 
     Cmd_CommandAdd( pAbc, "Liveness",     "l2s",           Abc_CommandAbcLivenessToSafety,    0 );
@@ -29926,6 +29928,100 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandAbc9CexMin( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern Abc_Cex_t * Gia_ManCexMin( Gia_Man_t * p, Abc_Cex_t * pCex, int iFrameStart, int nRealPis, int fJustMax, int fUseAll, int fVerbose );
+    Abc_Cex_t * pCexNew;
+    int iFrameStart = 0;
+    int nRealPis = -1;
+    int fJustMax = 1;
+    int fUseAll = 0;
+    int c, fVerbose = 0;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "FNjavh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'F':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-F\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            iFrameStart = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( iFrameStart < 0 ) 
+                goto usage;
+            break;
+        case 'N':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-N\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nRealPis = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nRealPis < 0 ) 
+                goto usage;
+            break;
+        case 'j':
+            fJustMax ^= 1;
+            break;
+        case 'a':
+            fUseAll ^= 1;
+            break;
+        case 'v':
+            fVerbose ^= 1;
+            break;
+        case 'h':
+            goto usage;
+        default:
+            goto usage;
+        }
+    }
+    if ( pAbc->pGia == NULL )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9CexMin(): There is no AIG.\n" );
+        return 1;
+    } 
+    if ( Gia_ManRegNum(pAbc->pGia) == 0 )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9CexMin(): The network is combinational.\n" );
+        return 0;
+    }
+    if ( pAbc->pCex == NULL )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9CexMin(): There is no counter-example.\n" );
+        return 1;
+    } 
+    pCexNew = Gia_ManCexMin( pAbc->pGia, pAbc->pCex, iFrameStart, nRealPis, fJustMax, fUseAll, fVerbose );
+    if ( pCexNew )
+        Abc_FrameReplaceCex( pAbc, &pCexNew );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: &cexmin [-FN num] [-javh]\n" );
+    Abc_Print( -2, "\t         minimizes a deep counter-example\n" );
+    Abc_Print( -2, "\t-F num : starting timeframe for minimization [default = %d]\n", iFrameStart );
+    Abc_Print( -2, "\t-N num : the number of real primary inputs [default = %d]\n", nRealPis );
+    Abc_Print( -2, "\t-j     : toggle computing all justifying assignments [default = %s]\n", fJustMax? "yes": "no" );
+    Abc_Print( -2, "\t-a     : toggle using all terminal objects [default = %s]\n", fUseAll? "yes": "no" );
+    Abc_Print( -2, "\t-v     : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h     : print the command usage\n");
+    return 1;
+} 
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
 //    Gia_Man_t * pTemp = NULL;