Merging recent changes.

2 files changed, 194 insertions, 0 deletions

diff --git a/src/aig/gia/giaTruth.c b/src/aig/gia/giaTruth.c
index c596048a..f05e2f68 100644
--- a/src/aig/gia/giaTruth.c
+++ b/src/aig/gia/giaTruth.c
@@ -19,6 +19,10 @@
 ***********************************************************************/
 
 #include "gia.h"
+#include "misc/vec/vecMem.h"
+#include "misc/vec/vecWec.h"
+#include "misc/util/utilTruth.h"
+#include "opt/dau/dau.h"
 
 ABC_NAMESPACE_IMPL_START
 
@@ -402,6 +406,127 @@ word * Gia_ObjComputeTruthTableCut( Gia_Man_t * p, Gia_Obj_t * pRoot, Vec_Int_t
     return pTruth;
 }
 
+/**Function*************************************************************
+
+  Synopsis    [Reduces GIA to contain isomorphic POs.]
+
+  Description [The root cannot be one of the leaves.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, Vec_Ptr_t ** pvPosEquivs, int fVerbose )
+{
+    char pCanonPerm[16];
+    int i, iObj, uCanonPhase, nVars, lastId, truthId;
+    int IndexCon = -1, IndexVar = -1;
+    Vec_Wec_t * vPosEquivs = Vec_WecAlloc( 100 );
+    word * pTruth;
+    Gia_Obj_t * pObj;
+    Vec_Mem_t * vTtMem[17];   // truth table memory and hash table
+    Gia_Man_t * pNew = NULL;
+    Vec_Int_t * vLeaves = Vec_IntAlloc( 16 );
+    Vec_Int_t * vFirsts;
+    Vec_Int_t * vTt2Class[17];
+    for ( i = 0; i < 17; i++ )
+    {
+        vTtMem[i] = Vec_MemAlloc( Abc_TtWordNum(i), 10 );
+        Vec_MemHashAlloc( vTtMem[i], 1000 );
+        vTt2Class[i] = Vec_IntStartFull( Gia_ManCoNum(p)+1 );
+    }
+    Gia_ObjComputeTruthTableStart( p, 16 );
+    Gia_ManForEachPo( p, pObj, i )
+    {
+        iObj = Gia_ObjId(p, pObj);
+        Gia_ManCollectCis( p, &iObj, 1, vLeaves );
+        if ( Vec_IntSize(vLeaves) > 16 )
+        {
+            Vec_IntPush( Vec_WecPushLevel(vPosEquivs), i );
+            continue;
+        }
+        pObj = Gia_ObjFanin0(pObj);
+        if ( Gia_ObjIsConst0(pObj) )
+        {
+            if ( IndexCon == -1 )
+            {
+                IndexCon = Vec_WecSize(vPosEquivs);
+                Vec_WecPushLevel(vPosEquivs);
+            }
+            Vec_WecPush( vPosEquivs, IndexCon, i );
+            continue;
+        }
+        if ( Gia_ObjIsCi(pObj) )
+        {
+            if ( IndexVar == -1 )
+            {
+                IndexVar = Vec_WecSize(vPosEquivs);
+                Vec_WecPushLevel(vPosEquivs);
+            }
+            Vec_WecPush( vPosEquivs, IndexVar, i );
+            continue;
+        }
+        assert( Gia_ObjIsAnd(pObj) );
+        pTruth = Gia_ObjComputeTruthTableCut( p, pObj, vLeaves );
+        Abc_TtMinimumBase( pTruth, NULL, Vec_IntSize(vLeaves), &nVars );
+        if ( nVars == 0 )
+        {
+            if ( IndexCon == -1 )
+            {
+                IndexCon = Vec_WecSize(vPosEquivs);
+                Vec_WecPushLevel(vPosEquivs);
+            }
+            Vec_WecPush( vPosEquivs, IndexCon, i );
+            continue;
+        }
+        if ( nVars == 1 )
+        {
+            if ( IndexVar == -1 )
+            {
+                IndexVar = Vec_WecSize(vPosEquivs);
+                Vec_WecPushLevel(vPosEquivs);
+            }
+            Vec_WecPush( vPosEquivs, IndexVar, i );
+            continue;
+        }
+        uCanonPhase = Abc_TtCanonicize( pTruth, nVars, pCanonPerm );
+        lastId = Vec_MemEntryNum( vTtMem[nVars] );
+        truthId = Vec_MemHashInsert( vTtMem[nVars], pTruth );
+        if ( lastId != Vec_MemEntryNum( vTtMem[nVars] ) ) // new one
+        {
+            assert( Vec_IntEntry(vTt2Class[nVars], truthId) == -1 );
+            Vec_IntWriteEntry( vTt2Class[nVars], truthId, Vec_WecSize(vPosEquivs) );
+            Vec_WecPushLevel(vPosEquivs);
+        }
+        assert( Vec_IntEntry(vTt2Class[nVars], truthId) >= 0 );
+        Vec_WecPush( vPosEquivs, Vec_IntEntry(vTt2Class[nVars], truthId), i );
+    }
+    Gia_ObjComputeTruthTableStop( p );
+    Vec_IntFree( vLeaves );
+    for ( i = 0; i < 17; i++ )
+    {
+        Vec_MemHashFree( vTtMem[i] );
+        Vec_MemFree( vTtMem[i] );
+        Vec_IntFree( vTt2Class[i] );
+    }
+
+    // find the first outputs and derive GIA
+    vFirsts = Vec_WecCollectFirsts( vPosEquivs );
+    pNew = Gia_ManDupCones( p, Vec_IntArray(vFirsts), Vec_IntSize(vFirsts), 0 );
+    Vec_IntFree( vFirsts );
+    // report and return    
+    if ( fVerbose )
+    { 
+        printf( "Nontrivial classes:\n" );
+        Vec_WecPrint( vPosEquivs, 1 );
+    }
+    if ( pvPosEquivs )
+        *pvPosEquivs = Vec_WecConvertToVecPtr( vPosEquivs );
+    Vec_WecFree( vPosEquivs );
+    return pNew;
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index ce649652..ef08b09d 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -423,6 +423,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_CommandAbc9IsoNpn             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9CexInfo            ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Cycle              ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Cone               ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -1032,6 +1033,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",         "&isonpn",       Abc_CommandAbc9IsoNpn,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&cexinfo",      Abc_CommandAbc9CexInfo,      0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&cycle",        Abc_CommandAbc9Cycle,        0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&cone",         Abc_CommandAbc9Cone,         0 );
@@ -35153,6 +35155,73 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandAbc9IsoNpn( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, Vec_Ptr_t ** pvPosEquivs, int fVerbose );
+    Gia_Man_t * pAig;
+    Vec_Ptr_t * vPosEquivs;
+    int c, fVerbose = 0;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "vh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'v':
+            fVerbose ^= 1;
+            break;
+        case 'h':
+            goto usage;
+        default:
+            goto usage;
+        }
+    }
+    if ( pAbc->pGia == NULL )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9IsoNpn(): There is no AIG.\n" );
+        return 1;
+    }
+    if ( Gia_ManPoNum(pAbc->pGia) == 1 )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9IsoNpn(): The AIG has only one PO. Isomorphism detection is not performed.\n" );
+        return 1;
+    }
+    if ( Gia_ManRegNum(pAbc->pGia) )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9IsoNpn(): ISO-NPN does not work with sequential AIGs.\n" );
+        return 1;
+    }
+    pAig = Gia_ManIsoNpnReduce( pAbc->pGia, &vPosEquivs, fVerbose );
+    if ( pAig == NULL )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9IsoNpn(): Transformation has failed.\n" );
+        return 1;
+    }
+    // update the internal storage of PO equivalences
+    Abc_FrameReplacePoEquivs( pAbc, &vPosEquivs );
+    // update the AIG
+    Abc_FrameUpdateGia( pAbc, pAig );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: &isonpn [-vh]\n" );
+    Abc_Print( -2, "\t         removes POs with functionally isomorphic combinational COI\n" );
+    Abc_Print( -2, "\t         (currently ignores POs whose structural support is more than 16)\n" );
+    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_CommandAbc9CexInfo( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     extern void Bmc_CexTest( Gia_Man_t * p, Abc_Cex_t * pCex, int fVerbose );