From 4efbd7b3ca360ba35c48e9306c92ad93c4c47af1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 7 Jun 2016 14:32:38 -0700 Subject: Detecting properties of internal nodes. --- src/base/abci/abc.c | 53 ++++++++++++++ src/base/abci/abcDetect.c | 172 ++++++++++++++++++++++++++++++++++++++++++++++ src/base/abci/module.make | 1 + 3 files changed, 226 insertions(+) create mode 100644 src/base/abci/abcDetect.c (limited to 'src/base') 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 \ -- cgit v1.2.3