From 6ae4ddec0001b7bc7a66798c8887f1d761c2e59d Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 11 Aug 2015 08:04:25 -0700 Subject: New command 'isonpn'. --- src/aig/gia/giaTruth.c | 61 ++++++++++++++++++++++++++++++++++++++++++++ src/base/abci/abc.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 130 insertions(+) (limited to 'src') diff --git a/src/aig/gia/giaTruth.c b/src/aig/gia/giaTruth.c index c596048a..3c8e7626 100644 --- a/src/aig/gia/giaTruth.c +++ b/src/aig/gia/giaTruth.c @@ -19,6 +19,9 @@ ***********************************************************************/ #include "gia.h" +#include "misc/vec/vecMem.h" +#include "misc/util/utilTruth.h" +#include "opt/dau/dau.h" ABC_NAMESPACE_IMPL_START @@ -402,6 +405,64 @@ 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, int fVerbose ) +{ + char pCanonPerm[16]; + int i, iObj, uCanonPhase, nVars, lastId, truthId; + 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 * vCone = Vec_IntAlloc( Gia_ManCoNum(p) ); + for ( i = 0; i < 17; i++ ) + { + vTtMem[i] = Vec_MemAlloc( Abc_TtWordNum(i), 10 ); + Vec_MemHashAlloc( vTtMem[i], 1000 ); + } + 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( vCone, i ); + continue; + } + if ( !Gia_ObjIsAnd(Gia_ObjFanin0(pObj)) ) + continue; + pTruth = Gia_ObjComputeTruthTableCut( p, Gia_ObjFanin0(pObj), vLeaves ); + Abc_TtMinimumBase( pTruth, NULL, Vec_IntSize(vLeaves), &nVars ); + 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 + Vec_IntPush( vCone, i ); + } + Vec_IntFree( vLeaves ); + for ( i = 0; i < 17; i++ ) + { + Vec_MemHashFree( vTtMem[i] ); + Vec_MemFree( vTtMem[i] ); + } + Gia_ObjComputeTruthTableStop( p ); + pNew = Gia_ManDupSelectedOutputs( p, vCone ); + Vec_IntFree( vCone ); + return pNew; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 315d926b..c88e95eb 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 ); @@ -35135,6 +35137,73 @@ usage: return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_CommandAbc9IsoNpn( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + extern Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, 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, 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 [] -- cgit v1.2.3 From 8ad20616690eb2208f0e893018499b9fc6cf1bc0 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 11 Aug 2015 14:07:04 -0700 Subject: New command 'isonpn'. --- src/aig/gia/giaTruth.c | 82 ++++++++++++++++++++++++++++++++++++++++++++------ src/base/abci/abc.c | 8 ++--- 2 files changed, 77 insertions(+), 13 deletions(-) (limited to 'src') diff --git a/src/aig/gia/giaTruth.c b/src/aig/gia/giaTruth.c index 3c8e7626..f05e2f68 100644 --- a/src/aig/gia/giaTruth.c +++ b/src/aig/gia/giaTruth.c @@ -20,6 +20,7 @@ #include "gia.h" #include "misc/vec/vecMem.h" +#include "misc/vec/vecWec.h" #include "misc/util/utilTruth.h" #include "opt/dau/dau.h" @@ -416,20 +417,24 @@ word * Gia_ObjComputeTruthTableCut( Gia_Man_t * p, Gia_Obj_t * pRoot, Vec_Int_t SeeAlso [] ***********************************************************************/ -Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, int fVerbose ) +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 * vCone = Vec_IntAlloc( Gia_ManCoNum(p) ); + 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 ) @@ -438,28 +443,87 @@ Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, int fVerbose ) Gia_ManCollectCis( p, &iObj, 1, vLeaves ); if ( Vec_IntSize(vLeaves) > 16 ) { - Vec_IntPush( vCone, i ); + Vec_IntPush( Vec_WecPushLevel(vPosEquivs), i ); continue; } - if ( !Gia_ObjIsAnd(Gia_ObjFanin0(pObj)) ) + pObj = Gia_ObjFanin0(pObj); + if ( Gia_ObjIsConst0(pObj) ) + { + if ( IndexCon == -1 ) + { + IndexCon = Vec_WecSize(vPosEquivs); + Vec_WecPushLevel(vPosEquivs); + } + Vec_WecPush( vPosEquivs, IndexCon, i ); continue; - pTruth = Gia_ObjComputeTruthTableCut( p, Gia_ObjFanin0(pObj), vLeaves ); + } + 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 - Vec_IntPush( vCone, i ); + { + 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] ); } - Gia_ObjComputeTruthTableStop( p ); - pNew = Gia_ManDupSelectedOutputs( p, vCone ); - Vec_IntFree( vCone ); + + // 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; } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index c88e95eb..9ab23c9d 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -35150,9 +35150,9 @@ usage: ***********************************************************************/ int Abc_CommandAbc9IsoNpn( Abc_Frame_t * pAbc, int argc, char ** argv ) { - extern Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, int fVerbose ); + extern Gia_Man_t * Gia_ManIsoNpnReduce( Gia_Man_t * p, Vec_Ptr_t ** pvPosEquivs, int fVerbose ); Gia_Man_t * pAig; - //Vec_Ptr_t * vPosEquivs; + Vec_Ptr_t * vPosEquivs; int c, fVerbose = 0; Extra_UtilGetoptReset(); while ( ( c = Extra_UtilGetopt( argc, argv, "vh" ) ) != EOF ) @@ -35183,14 +35183,14 @@ int Abc_CommandAbc9IsoNpn( Abc_Frame_t * pAbc, int argc, char ** argv ) Abc_Print( -1, "Abc_CommandAbc9IsoNpn(): ISO-NPN does not work with sequential AIGs.\n" ); return 1; } - pAig = Gia_ManIsoNpnReduce( pAbc->pGia, fVerbose ); + 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 ); + Abc_FrameReplacePoEquivs( pAbc, &vPosEquivs ); // update the AIG Abc_FrameUpdateGia( pAbc, pAig ); return 0; -- cgit v1.2.3