Improvements to LMS code.

4 files changed, 253 insertions, 23 deletions

diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h
index b6c04a89..e08e11d9 100644
--- a/src/base/abc/abc.h
+++ b/src/base/abc/abc.h
@@ -805,8 +805,7 @@ extern ABC_DLL void               Abc_NtkRecAdd3( Abc_Ntk_t * pNtk, int fUseSOPB
 extern ABC_DLL void               Abc_NtkRecPs3(int fPrintLib);
 extern ABC_DLL Gia_Man_t *        Abc_NtkRecGetGia3();
 extern ABC_DLL int                Abc_NtkRecIsRunning3();
-//extern ABC_DLL int                Abc_NtkRecIsInTrimMode3();
-//extern ABC_DLL void               Abc_NtkRecLibMerge3(Gia_Man_t * pGia);
+extern ABC_DLL void               Abc_NtkRecLibMerge3(Gia_Man_t * pGia);
 //extern ABC_DLL void               Abc_NtkRecFilter3(int nLimit);
 /*=== abcReconv.c ==========================================================*/
 extern ABC_DLL Abc_ManCut_t *     Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax, int nNodeFanStop, int nConeFanStop );
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 453be207..0da5cde6 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -220,6 +220,7 @@ static int Abc_CommandRecStop3               ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandRecPs3                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandRecAdd3                ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandRecDump3               ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandRecMerge3              ( Abc_Frame_t * pAbc, int argc, char ** argv );
 
 static int Abc_CommandMap                    ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAmap                   ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -659,22 +660,23 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_add",       Abc_CommandRecAdd,           0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_ps",        Abc_CommandRecPs,            0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_use",       Abc_CommandRecUse,           1 );
-    Cmd_CommandAdd( pAbc, "Choicing",     "rec_filter",    Abc_CommandRecFilter,        1 );
-    Cmd_CommandAdd( pAbc, "Choicing",     "rec_merge",     Abc_CommandRecMerge,         1 );
+    Cmd_CommandAdd( pAbc, "Choicing",     "rec_filter",    Abc_CommandRecFilter,        0 );
+    Cmd_CommandAdd( pAbc, "Choicing",     "rec_merge",     Abc_CommandRecMerge,         0 );
 
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_start2",    Abc_CommandRecStart2,        0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_stop2",     Abc_CommandRecStop2,         0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_ps2",       Abc_CommandRecPs2,           0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_add2",      Abc_CommandRecAdd2,          0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_dump2",     Abc_CommandRecDump2,         1 );
-    Cmd_CommandAdd( pAbc, "Choicing",     "rec_filter2",   Abc_CommandRecFilter2,       1 );
-    Cmd_CommandAdd( pAbc, "Choicing",     "rec_merge2",    Abc_CommandRecMerge2,        1 );
+    Cmd_CommandAdd( pAbc, "Choicing",     "rec_filter2",   Abc_CommandRecFilter2,       0 );
+    Cmd_CommandAdd( pAbc, "Choicing",     "rec_merge2",    Abc_CommandRecMerge2,        0 );
 
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_start3",    Abc_CommandRecStart3,        0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_stop3",     Abc_CommandRecStop3,         0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_ps3",       Abc_CommandRecPs3,           0 );
     Cmd_CommandAdd( pAbc, "Choicing",     "rec_add3",      Abc_CommandRecAdd3,          0 );
-    Cmd_CommandAdd( pAbc, "Choicing",     "rec_dump3",     Abc_CommandRecDump3,         1 );
+    Cmd_CommandAdd( pAbc, "Choicing",     "rec_dump3",     Abc_CommandRecDump3,         0 );
+    Cmd_CommandAdd( pAbc, "Choicing",     "rec_merge3",    Abc_CommandRecMerge3,        0 );
 
     Cmd_CommandAdd( pAbc, "SC mapping",   "map",           Abc_CommandMap,              1 );
     Cmd_CommandAdd( pAbc, "SC mapping",   "amap",          Abc_CommandAmap,             1 );
@@ -13110,7 +13112,7 @@ int Abc_CommandRecStart3( Abc_Frame_t * pAbc, int argc, char ** argv )
     pArgvNew = argv + globalUtilOptind;
     nArgcNew = argc - globalUtilOptind;
     if ( nArgcNew != 1 )
-        Abc_Print( 1, "File name is not given on the command line. Start a new record.\n" );
+        Abc_Print( 1, "File name is not given on the command line. Starting a new record.\n" );
     else
     {   
         // get the input file name
@@ -13139,7 +13141,7 @@ int Abc_CommandRecStart3( Abc_Frame_t * pAbc, int argc, char ** argv )
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: rec_start3 [-K num] [-C num] [-fvh]\n" );
+    Abc_Print( -2, "usage: rec_start3 [-K num] [-C num] [-fvh] <file>\n" );
     Abc_Print( -2, "\t         starts recording AIG subgraphs (should be called for\n" );
     Abc_Print( -2, "\t         an empty network or after reading in a previous record)\n" );
     Abc_Print( -2, "\t-K num : the largest number of inputs [default = %d]\n", nVars );
@@ -13147,6 +13149,7 @@ usage:
     Abc_Print( -2, "\t-f     : toggles recording functions without AIG subgraphs [default = %s]\n", fFuncOnly? "yes": "no" );
     Abc_Print( -2, "\t-v     : toggles additional verbose output [default = %s]\n", fVerbose? "yes": "no" );
     Abc_Print( -2, "\t-h     : print the command usage\n");
+    Abc_Print( -2, "\t<file> : AIGER file with the library\n");
     return 1;
 }
 
@@ -13348,6 +13351,87 @@ int Abc_CommandRecDump3( Abc_Frame_t * pAbc, int argc, char ** argv )
 usage:
     Abc_Print( -2, "usage: rec_dump3 [-h] <file>\n" );
     Abc_Print( -2, "\t-h     : print the command usage\n");
+    Abc_Print( -2, "\t<file> : AIGER file to write the library\n");
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_CommandRecMerge3( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    int c;
+    char * FileName, * pTemp;
+    char ** pArgvNew;
+    int nArgcNew;
+    FILE * pFile;
+    Gia_Man_t * pGia = NULL;
+
+    // set defaults
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "dh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'h':
+            goto usage;
+        default:
+            goto usage;
+        }
+    }
+    if ( !Abc_NtkRecIsRunning3() )
+    {
+        Abc_Print( -1, "This command works for AIGs only after calling \"rec_start3\".\n" );
+        return 0;
+    }
+    pArgvNew = argv + globalUtilOptind;
+    nArgcNew = argc - globalUtilOptind;
+    if ( nArgcNew != 1 )
+    {
+        Abc_Print( -1, "File name is not given on the command line.\n" );
+        return 1;
+    }
+    else
+    {   
+        // get the input file name
+        FileName = pArgvNew[0];
+        // fix the wrong symbol
+        for ( pTemp = FileName; *pTemp; pTemp++ )
+            if ( *pTemp == '>' )
+                *pTemp = '\\';
+        if ( (pFile = fopen( FileName, "r" )) == NULL )
+        {
+            Abc_Print( -1, "Cannot open input file \"%s\". ", FileName );
+            if ( (FileName = Extra_FileGetSimilarName( FileName, ".aig", NULL, NULL, NULL, NULL )) )
+                Abc_Print( 1, "Did you mean \"%s\"?", FileName );
+            Abc_Print( 1, "\n" );
+            return 1;
+        }
+        fclose( pFile );
+        pGia = Gia_ReadAiger( FileName, 1, 0 );
+        if ( pGia == NULL )
+        {
+            Abc_Print( -1, "Reading AIGER has failed.\n" );
+            return 0;
+        }
+    }
+    Abc_NtkRecLibMerge3(pGia);
+    Gia_ManStop( pGia );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: rec_merge3 [-h] <file>\n" );
+    Abc_Print( -2, "\t         merge libraries\n" );
+    Abc_Print( -2, "\t-h     : print the command usage\n");
+    Abc_Print( -2, "\t<file> : AIGER file with the library\n");
     return 1;
 }
 
diff --git a/src/base/abci/abcRec3.c b/src/base/abci/abcRec3.c
index 7007ab97..4e72b7ae 100644
--- a/src/base/abci/abcRec3.c
+++ b/src/base/abci/abcRec3.c
@@ -84,8 +84,6 @@ struct Lms_Man_t_
     clock_t           timeInsert;
     clock_t           timeOther;
     clock_t           timeTotal;
-
-    clock_t           timeDerive;
 };
 
 static Lms_Man_t * s_pMan3 = NULL;
@@ -174,7 +172,8 @@ void Lms_ManStop( Lms_Man_t * p )
 void Lms_ManPrint( Lms_Man_t * p )
 {
 //    Gia_ManPrintStats( p->pGia, 0, 0 );
-    printf( "The record has %d classes containing %d AIG subgraphs with %d AND nodes.\n", Vec_MemEntryNum(p->vTtMem), p->nAdded, Gia_ManAndNum(p->pGia) );
+    printf( "Library with %d vars has %d classes and %d AIG subgraphs with %d AND nodes.\n", 
+        Gia_ManCiNum(p->pGia), Vec_MemEntryNum(p->vTtMem), p->nAdded, Gia_ManAndNum(p->pGia) );
 
     p->nAddedFuncs = Vec_MemEntryNum(p->vTtMem);
     printf( "Subgraphs tried                             = %10d. (%6.2f %%)\n", p->nTried,         !p->nTried? 0 : 100.0*p->nTried/p->nTried );
@@ -186,6 +185,7 @@ void Lms_ManPrint( Lms_Man_t * p )
     printf( "Subgraphs filtered by isomorphism           = %10d. (%6.2f %%)\n", p->nFilterSame,    !p->nTried? 0 : 100.0*p->nFilterSame/p->nTried );
     printf( "Subgraphs added                             = %10d. (%6.2f %%)\n", p->nAdded,         !p->nTried? 0 : 100.0*p->nAdded/p->nTried );
     printf( "Functions added                             = %10d. (%6.2f %%)\n", p->nAddedFuncs,    !p->nTried? 0 : 100.0*p->nAddedFuncs/p->nTried );
+    if ( p->nHoleInTheWall )
     printf( "Cuts whose logic structure has a hole       = %10d. (%6.2f %%)\n", p->nHoleInTheWall, !p->nTried? 0 : 100.0*p->nHoleInTheWall/p->nTried );
 
     p->timeOther = p->timeTotal - p->timeCollect - p->timeCanon - p->timeBuild - p->timeCheck - p->timeInsert;
@@ -383,7 +383,7 @@ void Lms_GiaPrintSubgraph( Gia_Man_t * p, Gia_Obj_t * pObj )
   SeeAlso     []
 
 ***********************************************************************/
-Gia_Man_t * Lms_GiaProfilesPrint( Gia_Man_t * p )
+void Lms_GiaProfilesPrint( Gia_Man_t * p )
 {
     Gia_Obj_t * pObj;
     int i;
@@ -403,7 +403,6 @@ Gia_Man_t * Lms_GiaProfilesPrint( Gia_Man_t * p )
 
     Vec_WrdFree( vDelays );
     Vec_StrFree( vAreas );
-    return NULL;
 }
 
 /**Function*************************************************************
@@ -448,6 +447,156 @@ static void Abc_TtStretch6( word * pInOut, int nVarS, int nVarB )
             pInOut[w + i] = pInOut[i];              
 }
 
+/**Function*************************************************************
+
+  Synopsis    [Compute support sizes for each CO.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Str_t * Gia_ManSuppSizes( Gia_Man_t * p )
+{
+    Vec_Str_t * vResult;
+    Vec_Str_t * vSupps;
+    Gia_Obj_t * pObj;
+    int i;
+    vSupps = Vec_StrAlloc( Gia_ManObjNum(p) );
+    Vec_StrPush( vSupps, 0 );
+    Gia_ManForEachObj1( p, pObj, i )
+    {
+        if ( Gia_ObjIsAnd(pObj) )
+            Vec_StrPush( vSupps, (char)Abc_MaxInt( Vec_StrEntry(vSupps, Gia_ObjFaninId0(pObj, i)), Vec_StrEntry(vSupps, Gia_ObjFaninId1(pObj, i)) ) );
+        else if ( Gia_ObjIsCo(pObj) )
+            Vec_StrPush( vSupps, Vec_StrEntry(vSupps, Gia_ObjFaninId0(pObj, i)) );
+        else if ( Gia_ObjIsCi(pObj) )
+            Vec_StrPush( vSupps, (char)(Gia_ObjCioId(pObj)+1) );
+        else assert( 0 );
+    }
+    assert( Vec_StrSize(vSupps) == Gia_ManObjNum(p) );
+    vResult = Vec_StrAlloc( Gia_ManCoNum(p) );
+    Gia_ManForEachCo( p, pObj, i )
+        Vec_StrPush( vResult, Vec_StrEntry(vSupps, Gia_ObjId(p, pObj)) );
+    Vec_StrFree( vSupps );
+    return vResult;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Recanonicizes the library and add it to the current library.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkRecLibMerge3( Gia_Man_t * pLib )
+{
+    int fCheck = 0;
+    Lms_Man_t * p = s_pMan3;
+    Gia_Man_t * pGia = p->pGia;
+    Vec_Str_t * vSupps;
+    char pCanonPerm[16];
+    unsigned uCanonPhase;
+    unsigned * pTruth;
+    int i, k, Index, iFanin0, iFanin1, nLeaves;
+    Gia_Obj_t * pDriver, * pTemp, * pObjPo;
+    clock_t clk, clk2 = clock();
+
+    assert( Gia_ManCiNum(pLib) == Gia_ManCiNum(pGia) );
+
+    // create hash table if not available
+    if ( pGia->pHTable == NULL )
+        Gia_ManHashStart( pGia );
+
+    // add AIG subgraphs
+    vSupps = Gia_ManSuppSizes( pLib );
+    Gia_ManForEachCo( pLib, pObjPo, k )
+    {
+        // get support size
+        nLeaves = Vec_StrEntry(vSupps, k);
+        assert( nLeaves > 1 );
+        // compute the truth table
+clk = clock();
+        pTruth = Gia_ObjComputeTruthTable( pLib, Gia_ObjFanin0(pObjPo) );
+p->timeCollect += clock() - clk;
+        // semi-canonicize
+clk = clock();
+        memcpy( p->pTemp1, pTruth, p->nWords * sizeof(word) );
+    //    uCanonPhase = luckyCanonicizer_final_fast( p->pTemp1, nLeaves, pCanonPerm );
+        uCanonPhase = Kit_TruthSemiCanonicize( (unsigned *)p->pTemp1, (unsigned *)p->pTemp2, nLeaves, pCanonPerm );
+        Abc_TtStretch5( (unsigned *)p->pTemp1, nLeaves, p->nVars );
+p->timeCanon += clock() - clk;
+        // pCanonPerm and uCanonPhase show what was the variable corresponding to each var in the current truth
+
+clk = clock();
+        // map cut leaves into elementary variables of GIA
+        for ( i = 0; i < nLeaves; i++ )
+            Gia_ManCi( pLib, pCanonPerm[i] )->Value = Abc_Var2Lit( Gia_ObjId(pGia, Gia_ManPi(pGia, i)), (uCanonPhase >> i) & 1 );
+        // build internal nodes
+        assert( Vec_IntSize(pLib->vTtNodes) > 0 );
+        Gia_ManForEachObjVec( pLib->vTtNodes, pLib, pTemp, i )
+        {
+            iFanin0 = Abc_LitNotCond( Gia_ObjFanin0(pTemp)->Value, Gia_ObjFaninC0(pTemp) );
+            iFanin1 = Abc_LitNotCond( Gia_ObjFanin1(pTemp)->Value, Gia_ObjFaninC1(pTemp) );
+            pTemp->Value = Gia_ManHashAnd( pGia, iFanin0, iFanin1 );
+        }
+p->timeBuild += clock() - clk;
+
+        // check if this node is already driving a PO
+        assert( Gia_ObjIsAnd(pTemp) );
+        pDriver = Gia_ManObj(pGia, Abc_Lit2Var(pTemp->Value));
+        if ( pDriver->fMark1 )
+        {
+            p->nFilterSame++;
+            continue;
+        }
+        pDriver->fMark1 = 1;
+        // create output
+        Gia_ManAppendCo( pGia, Abc_LitNotCond( pTemp->Value, (uCanonPhase >> nLeaves) & 1 ) );
+
+        // verify truth table
+        if ( fCheck )
+        {
+clk = clock();
+        pTemp = Gia_ManCo(pGia, Gia_ManCoNum(pGia)-1);
+        pTruth = Gia_ObjComputeTruthTable( pGia, Gia_ManCo(pGia, Gia_ManCoNum(pGia)-1) );
+p->timeCheck += clock() - clk;
+        if ( memcmp( p->pTemp1, pTruth, p->nWords * sizeof(word) ) != 0 )
+        {
+    
+            Kit_DsdPrintFromTruth( pTruth, nLeaves ); printf( "\n" );
+            Kit_DsdPrintFromTruth( (unsigned *)p->pTemp1, nLeaves ); printf( "\n" );
+            printf( "Truth table verification has failed.\n" );
+    
+            // drive PO with constant
+            Gia_ManPatchCoDriver( pGia, Gia_ManCoNum(pGia)-1, 0 );
+            // save truth table ID
+            Vec_IntPush( p->vTruthIds, -1 );
+            p->nFilterTruth++;
+            continue;
+        }
+        }
+
+clk = clock();
+        // add the resulting truth table to the hash table 
+        Index = Vec_MemHashInsert( p->vTtMem, p->pTemp1 );
+        // save truth table ID
+        Vec_IntPush( p->vTruthIds, Index );
+        assert( Gia_ManCoNum(pGia) == Vec_IntSize(p->vTruthIds) );
+        p->nAdded++;
+p->timeInsert += clock() - clk;
+    }
+    Vec_StrFree( vSupps );
+p->timeTotal += clock() - clk2;
+}
+
 
 /**Function*************************************************************
 
@@ -490,8 +639,6 @@ p->timeCollect += clock() - clk;
 
     // semi-canonicize truth table
 clk = clock();
-    for ( i = 0; i < Abc_MaxInt(nLeaves, 6); i++ )
-        pCanonPerm[i] = i;
     memcpy( p->pTemp1, If_CutTruthW(pCut), p->nWords * sizeof(word) );
 //    uCanonPhase = luckyCanonicizer_final_fast( p->pTemp1, nLeaves, pCanonPerm );
     uCanonPhase = Kit_TruthSemiCanonicize( (unsigned *)p->pTemp1, (unsigned *)p->pTemp2, nLeaves, pCanonPerm );
@@ -522,24 +669,21 @@ clk = clock();
 p->timeBuild += clock() - clk;
 
     // check if this node is already driving a PO
+    assert( If_ObjIsAnd(pIfObj) );
     pDriver = Gia_ManObj(pGia, Abc_Lit2Var(pIfObj->iCopy));
     if ( pDriver->fMark1 )
     {
         p->nFilterSame++;
         return 1;
     }
-
+    pDriver->fMark1 = 1;
     // create output
-    assert( If_ObjIsAnd(pIfObj) );
     Gia_ManAppendCo( pGia, Abc_LitNotCond( pIfObj->iCopy, (uCanonPhase >> nLeaves) & 1 ) );
 
-    // mark the driver
-    pDriver = Gia_ManObj(pGia, Abc_Lit2Var(pIfObj->iCopy));
-    pDriver->fMark1 = 1;
-
     // verify truth table
 clk = clock();
     pTruth = Gia_ObjComputeTruthTable( pGia, Gia_ManCo(pGia, Gia_ManCoNum(pGia)-1) );
+p->timeCheck += clock() - clk;
     if ( memcmp( p->pTemp1, pTruth, p->nWords * sizeof(word) ) != 0 )
     {
 /*
@@ -554,7 +698,6 @@ clk = clock();
         p->nFilterTruth++;
         return 1;
     }
-p->timeCheck += clock() - clk;
 
 clk = clock();
     // add the resulting truth table to the hash table 
@@ -909,6 +1052,7 @@ void Lms_GiaNormalize( Lms_Man_t * p )
     Vec_Int_t * vRemain;
     Vec_Int_t * vTruthIdsNew;
     int i, Entry, Prev = -1, Next;
+    clock_t clk = clock();
     // collect non-redundant COs
     vRemain = Lms_GiaFindNonRedundantCos( p );
     // change these to be useful literals
@@ -940,6 +1084,7 @@ void Lms_GiaNormalize( Lms_Man_t * p )
     Vec_IntFree( p->vTruthIds );
     p->vTruthIds = vTruthIdsNew;
 //    Vec_IntPrint( vTruthIdsNew );
+    Abc_PrintTime( 1, "Normalization runtime", clock() - clk );
 }
 
 /**Function*************************************************************
diff --git a/src/bool/kit/kitTruth.c b/src/bool/kit/kitTruth.c
index a6951163..87b28135 100644
--- a/src/bool/kit/kitTruth.c
+++ b/src/bool/kit/kitTruth.c
@@ -1664,6 +1664,8 @@ unsigned Kit_TruthSemiCanonicize( unsigned * pInOut, unsigned * pAux, int nVars,
 
     // canonicize output
     uCanonPhase = 0;
+    for ( i = 0; i < nVars; i++ )
+        pCanonPerm[i] = i;
 
     nOnes = Kit_TruthCountOnes(pIn, nVars);
     //if(pIn[0] & 1)