Detecting properties of internal nodes.

3 files changed, 226 insertions, 0 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index c55a46ed..a5b96c24 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -134,6 +134,7 @@ static int Abc_CommandRr                     ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandCascade                ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandExtract                ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandVarMin                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandDetect                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
 
 static int Abc_CommandLogic                  ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandComb                   ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -770,6 +771,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "Synthesis",    "cascade",       Abc_CommandCascade,          1 );
     Cmd_CommandAdd( pAbc, "Synthesis",    "extract",       Abc_CommandExtract,          1 );
     Cmd_CommandAdd( pAbc, "Synthesis",    "varmin",        Abc_CommandVarMin,           0 );
+    Cmd_CommandAdd( pAbc, "Synthesis",    "detect",        Abc_CommandDetect,           0 );
 
     Cmd_CommandAdd( pAbc, "Various",      "logic",         Abc_CommandLogic,            1 );
     Cmd_CommandAdd( pAbc, "Various",      "comb",          Abc_CommandComb,             1 );
@@ -7201,6 +7203,57 @@ usage:
     return 1;
 }
 
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_CommandDetect( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern void Abc_NtkDetectClassesTest( Abc_Ntk_t * pNtk );
+    Abc_Ntk_t * pNtk;
+    int c, fVerbose = 0;
+    pNtk = Abc_FrameReadNtk(pAbc);
+    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 ( pNtk == NULL )
+    {
+        Abc_Print( -1, "Empty network.\n" );
+        return 1;
+    }
+    if ( Abc_NtkIsStrash(pNtk) )
+    {
+        Abc_Print( -1, "Only applicable to a logic network.\n" );
+        return 1;
+    }
+    Abc_NtkDetectClassesTest( pNtk );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: detect [-vh]\n" );
+    Abc_Print( -2, "\t           detects properties of internal nodes\n" );
+    Abc_Print( -2, "\t-v       : toggle verbose printout [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h       : print the command usage\n");
+    return 1;
+}
 
 /**Function*************************************************************
 
diff --git a/src/base/abci/abcDetect.c b/src/base/abci/abcDetect.c
new file mode 100644
index 00000000..31121516
--- /dev/null
+++ b/src/base/abci/abcDetect.c
@@ -0,0 +1,172 @@
+/**CFile****************************************************************
+
+  FileName    [abcDetect.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Network and node package.]
+
+  Synopsis    [Detect conditions.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 7, 2016.]
+
+  Revision    [$Id: abcDetect.c,v 1.00 2016/06/07 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "base/abc/abc.h"
+#include "misc/vec/vecHsh.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Detect equivalence classes of nodes in terms of their TFO.]
+
+  Description [Given is the logic network (pNtk) and the set of objects
+  (primary inputs or internal nodes) to be considered (vObjs), this function
+  returns a set of equivalence classes of these objects in terms of their 
+  transitive fanout (TFO). Two objects belong to the same class if the set 
+  of COs they feed into are the same.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NtkDetectClasses_rec( Abc_Obj_t * pObj, Vec_Int_t * vMap, Hsh_VecMan_t * pHash, Vec_Int_t * vTemp )
+{
+    Vec_Int_t * vArray, * vSet;
+    Abc_Obj_t * pNext; int i;
+    // get the CO set for this object
+    int Entry = Vec_IntEntry(vMap, Abc_ObjId(pObj));
+    if ( Entry != -1 ) // the set is already computed
+        return Entry;
+    // compute a new CO set
+    assert( Abc_ObjIsCi(pObj) || Abc_ObjIsNode(pObj) );
+    // if there is no fanouts, the set of COs is empty
+    if ( Abc_ObjFanoutNum(pObj) == 0 )
+    {
+        Vec_IntWriteEntry( vMap, Abc_ObjId(pObj), 0 );
+        return 0;
+    }
+    // compute the set for the first fanout
+    Entry = Abc_NtkDetectClasses_rec( Abc_ObjFanout0(pObj), vMap, pHash, vTemp );
+    if ( Abc_ObjFanoutNum(pObj) == 1 )
+        return Entry;
+    vSet = Vec_IntAlloc( 16 );
+    // initialize the set with that of first fanout
+    vArray = Hsh_VecReadEntry( pHash, Entry );
+    Vec_IntClear( vSet );
+    Vec_IntAppend( vSet, vArray );
+    // iteratively add sets of other fanouts
+    Abc_ObjForEachFanout( pObj, pNext, i )
+    {
+        if ( i == 0 ) 
+            continue;
+        Entry = Abc_NtkDetectClasses_rec( pNext, vMap, pHash, vTemp );
+        vArray = Hsh_VecReadEntry( pHash, Entry );
+        Vec_IntTwoMerge2( vSet, vArray, vTemp );
+        ABC_SWAP( Vec_Int_t, *vSet, *vTemp );
+    }
+    // create or find new set and map the object into it
+    Entry = Hsh_VecManAdd( pHash, vSet );
+    Vec_IntWriteEntry( vMap, Abc_ObjId(pObj), Entry );
+    Vec_IntFree( vSet );
+    return Entry;
+}
+Vec_Wec_t * Abc_NtkDetectClasses( Abc_Ntk_t * pNtk, Vec_Int_t * vObjs )
+{
+    Vec_Wec_t * vClasses;   // classes of equivalence objects from vObjs
+    Vec_Int_t * vClassMap;  // mapping of each CO set into its class in vClasses
+    Vec_Int_t * vClass;     // one equivalence class     
+    Abc_Obj_t * pObj; 
+    int i, iObj, SetId, ClassId;
+    // create hash table to hash sets of CO indexes
+    Hsh_VecMan_t * pHash = Hsh_VecManStart( 1000 );
+    // create elementary sets (each composed of one CO) and map COs into them
+    Vec_Int_t * vMap = Vec_IntStartFull( Abc_NtkObjNumMax(pNtk) );
+    Vec_Int_t * vSet = Vec_IntAlloc( 16 );
+    assert( Abc_NtkIsLogic(pNtk) );
+    // compute empty set
+    SetId = Hsh_VecManAdd( pHash, vSet );
+    assert( SetId == 0 );
+    Abc_NtkForEachCo( pNtk, pObj, i )
+    {
+        Vec_IntFill( vSet, 1, i );
+        SetId = Hsh_VecManAdd( pHash, vSet );
+        Vec_IntWriteEntry( vMap, Abc_ObjId(pObj), SetId );
+    }
+    // make sure the array of objects is sorted
+    Vec_IntSort( vObjs, 0 );
+    // begin from the objects and map their IDs into sets of COs
+    Abc_NtkForEachObjVec( vObjs, pNtk, pObj, i )
+        Abc_NtkDetectClasses_rec( pObj, vMap, pHash, vSet );
+    Vec_IntFree( vSet );
+    // create map for mapping CO set its their classes
+    vClassMap = Vec_IntStartFull( Hsh_VecSize(pHash) + 1 );
+    // collect classes of objects
+    vClasses = Vec_WecAlloc( 1000 );
+    Vec_IntForEachEntry( vObjs, iObj, i )
+    {
+        // for a given object (iObj), find the ID of its COs set
+        SetId = Vec_IntEntry( vMap, iObj );
+        assert( SetId >= 0 );
+        // for the given CO set, finds its equivalence class
+        ClassId = Vec_IntEntry( vClassMap, SetId );
+        if ( ClassId == -1 )  // there is no equivalence class
+        {
+            // map this CO set into a new equivalence class
+            Vec_IntWriteEntry( vClassMap, SetId, Vec_WecSize(vClasses) );
+            vClass = Vec_WecPushLevel( vClasses );
+        }
+        else // get hold of the equivalence class
+            vClass = Vec_WecEntry( vClasses, ClassId );
+        // add objects to the class
+        Vec_IntPush( vClass, iObj );
+        // print the set for this object
+        //printf( "Object %5d : ", iObj );
+        //Vec_IntPrint( Hsh_VecReadEntry(pHash, SetId) );
+    }
+    Hsh_VecManStop( pHash );
+    Vec_IntFree( vClassMap );
+    Vec_IntFree( vMap );
+    return vClasses;
+}
+void Abc_NtkDetectClassesTest( Abc_Ntk_t * pNtk )
+{
+    Vec_Int_t * vObjs;
+    Vec_Wec_t * vRes;
+    // for testing, create the set of object IDs for all combinational inputs (CIs)
+    Abc_Obj_t * pObj; int i;
+    vObjs = Vec_IntAlloc( Abc_NtkCiNum(pNtk) );
+    Abc_NtkForEachCi( pNtk, pObj, i )
+        Vec_IntPush( vObjs, Abc_ObjId(pObj) );
+    // compute equivalence classes of CIs and print them
+    vRes = Abc_NtkDetectClasses( pNtk, vObjs );
+    Vec_WecPrint( vRes, 0 );
+    // clean up
+    Vec_IntFree( vObjs );
+    Vec_WecFree( vRes );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/base/abci/module.make b/src/base/abci/module.make
index 201eafda..a3c343ee 100644
--- a/src/base/abci/module.make
+++ b/src/base/abci/module.make
@@ -12,6 +12,7 @@ SRC +=    src/base/abci/abc.c \
     src/base/abci/abcDar.c \
     src/base/abci/abcDebug.c \
     src/base/abci/abcDec.c \
+    src/base/abci/abcDetect.c \
     src/base/abci/abcDress.c \
     src/base/abci/abcDress2.c \
     src/base/abci/abcDsd.c \