From a1fa224d61ca8ba9d7eb6c1aec0092e6e4bf2f8c Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 9 Dec 2014 23:30:46 -0800 Subject: New flavor of DSD-friendly 'eliminate'. --- src/aig/gia/giaDup.c | 4 +- src/aig/gia/giaMuxes.c | 4 ++ src/base/abc/abc.h | 2 +- src/base/abc/abcMinBase.c | 141 ++++++++++++++++++++++++++++++++++++++++++++++ src/base/abci/abc.c | 15 ++++- 5 files changed, 161 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/aig/gia/giaDup.c b/src/aig/gia/giaDup.c index b374ad49..8454eca7 100644 --- a/src/aig/gia/giaDup.c +++ b/src/aig/gia/giaDup.c @@ -562,7 +562,9 @@ Gia_Man_t * Gia_ManDup( Gia_Man_t * p ) Gia_ManConst0(p)->Value = 0; Gia_ManForEachObj1( p, pObj, i ) { - if ( Gia_ObjIsAnd(pObj) ) + if ( Gia_ObjIsBarBuf(pObj) ) + pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) ); + else if ( Gia_ObjIsAnd(pObj) ) { pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); if ( Gia_ObjSibl(p, Gia_ObjId(p, pObj)) ) diff --git a/src/aig/gia/giaMuxes.c b/src/aig/gia/giaMuxes.c index f7d96b3f..b59f51f7 100644 --- a/src/aig/gia/giaMuxes.c +++ b/src/aig/gia/giaMuxes.c @@ -117,6 +117,8 @@ Gia_Man_t * Gia_ManDupMuxes( Gia_Man_t * p, int Limit ) pObj->Value = Gia_ManAppendCi( pNew ); else if ( Gia_ObjIsCo(pObj) ) pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + else if ( Gia_ObjIsBarBuf(pObj) ) + pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) ); else if ( !Gia_ObjIsMuxType(pObj) || Gia_ObjSibl(p, Gia_ObjFaninId0(pObj, i)) || Gia_ObjSibl(p, Gia_ObjFaninId1(pObj, i)) ) pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) @@ -172,6 +174,8 @@ Gia_Man_t * Gia_ManDupNoMuxes( Gia_Man_t * p ) pObj->Value = Gia_ManAppendCi( pNew ); else if ( Gia_ObjIsCo(pObj) ) pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + else if ( Gia_ObjIsBarBuf(pObj) ) + pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) ); else if ( Gia_ObjIsMuxId(p, i) ) pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) ); else if ( Gia_ObjIsXor(pObj) ) diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index 6acdedad..e0c4a5cf 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -357,7 +357,7 @@ static inline int Abc_ObjIsLatch( Abc_Obj_t * pObj ) { return pO static inline int Abc_ObjIsBox( Abc_Obj_t * pObj ) { return pObj->Type == ABC_OBJ_LATCH || pObj->Type == ABC_OBJ_WHITEBOX || pObj->Type == ABC_OBJ_BLACKBOX; } static inline int Abc_ObjIsWhitebox( Abc_Obj_t * pObj ) { return pObj->Type == ABC_OBJ_WHITEBOX;} static inline int Abc_ObjIsBlackbox( Abc_Obj_t * pObj ) { return pObj->Type == ABC_OBJ_BLACKBOX;} -static inline int Abc_ObjIsBarBuf( Abc_Obj_t * pObj ) { assert( Abc_NtkIsLogic(pObj->pNtk) ); return Vec_IntSize(&pObj->vFanins) == 1 && pObj->pData == NULL; } +static inline int Abc_ObjIsBarBuf( Abc_Obj_t * pObj ) { return Abc_NtkIsLogic(pObj->pNtk) && Vec_IntSize(&pObj->vFanins) == 1 && pObj->pData == NULL; } static inline void Abc_ObjBlackboxToWhitebox( Abc_Obj_t * pObj ) { assert( Abc_ObjIsBlackbox(pObj) ); pObj->Type = ABC_OBJ_WHITEBOX; pObj->pNtk->nObjCounts[ABC_OBJ_BLACKBOX]--; pObj->pNtk->nObjCounts[ABC_OBJ_WHITEBOX]++; } // working with fanin/fanout edges diff --git a/src/base/abc/abcMinBase.c b/src/base/abc/abcMinBase.c index 84cf5cb3..75bcfa03 100644 --- a/src/base/abc/abcMinBase.c +++ b/src/base/abc/abcMinBase.c @@ -675,6 +675,147 @@ int Abc_NtkEliminate1( Abc_Ntk_t * pNtk, int ElimValue, int nMaxSize, int nIterM return 1; } +/**Function************************************************************* + + Synopsis [Sort nodes in the reverse topo order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_ObjCompareByNumber( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 ) +{ + return Abc_ObjRegular(*pp1)->iTemp - Abc_ObjRegular(*pp2)->iTemp; +} +void Abc_ObjSortInReverseOrder( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes ) +{ + Vec_Ptr_t * vOrder; + Abc_Obj_t * pNode; + int i; + vOrder = Abc_NtkDfsReverse( pNtk ); + Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pNode, i ) + pNode->iTemp = i; + Vec_PtrSort( vNodes, (int (*)())Abc_ObjCompareByNumber ); + Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pNode, i ) + pNode->iTemp = 0; + Vec_PtrFree( vOrder ); +} + + +/**Function************************************************************* + + Synopsis [Performs traditional eliminate -1.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkEliminateSpecial( Abc_Ntk_t * pNtk, int nMaxSize, int fVerbose ) +{ + extern void Abc_NtkBddReorder( Abc_Ntk_t * pNtk, int fVerbose ); + Vec_Ptr_t * vFanouts, * vFanins, * vNodes; + Abc_Obj_t * pNode, * pFanout; + int * pPermFanin, * pPermFanout; + int RetValue, i, k; + assert( nMaxSize > 0 ); + assert( Abc_NtkIsLogic(pNtk) ); + + + // convert network to BDD representation + if ( !Abc_NtkToBdd(pNtk) ) + { + fprintf( stdout, "Converting to BDD has failed.\n" ); + return 0; + } + + // prepare nodes for sweeping + Abc_NtkRemoveDupFanins( pNtk ); + Abc_NtkMinimumBase( pNtk ); + Abc_NtkCleanup( pNtk, 0 ); + + // convert network to SOPs + if ( !Abc_NtkToSop(pNtk, 0) ) + { + fprintf( stdout, "Converting to SOP has failed.\n" ); + return 0; + } + + // collect info about the nodes to be eliminated + vNodes = Vec_PtrAlloc( 1000 ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { + if ( Abc_ObjFanoutNum(pNode) != 1 ) + continue; + pFanout = Abc_ObjFanout0(pNode); + if ( !Abc_ObjIsNode(pFanout) ) + continue; + if ( Abc_SopGetCubeNum((char *)pNode->pData) != 1 ) + continue; + if ( Abc_SopGetCubeNum((char *)pFanout->pData) != 1 ) + continue; + // find the fanout's fanin + RetValue = Abc_NodeFindFanin( pFanout, pNode ); + assert( RetValue >= 0 && RetValue < Abc_ObjFaninNum(pFanout) ); + // both pNode and pFanout are AND/OR type nodes + if ( Abc_SopIsComplement((char *)pNode->pData) == Abc_SopGetIthCareLit((char *)pFanout->pData, RetValue) ) + continue; + Vec_PtrPush( vNodes, pNode ); + } + if ( Vec_PtrSize(vNodes) == 0 ) + { + Vec_PtrFree( vNodes ); + return 1; + } + Abc_ObjSortInReverseOrder( pNtk, vNodes ); + + // convert network to BDD representation + if ( !Abc_NtkToBdd(pNtk) ) + { + fprintf( stdout, "Converting to BDD has failed.\n" ); + return 0; + } + + // go through the nodes and decide is they can be eliminated + pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 ); + pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 ); + vFanins = Vec_PtrAlloc( 1000 ); + vFanouts = Vec_PtrAlloc( 1000 ); + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) + { + assert( Abc_ObjIsNode(pNode) ); + assert( Abc_NodeFindCoFanout(pNode) == NULL ); + // perform elimination + Abc_NodeCollectFanouts( pNode, vFanouts ); + Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k ) + { + if ( fVerbose ) + printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ", + Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) ); + RetValue = Abc_NodeCollapse( pNode, pFanout, vFanins, pPermFanin, pPermFanout ); + assert( RetValue ); + if ( fVerbose ) + { + Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 ); + if ( pNodeNew ) + printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) ); + } + } + } + Abc_NtkBddReorder( pNtk, 0 ); + Vec_PtrFree( vFanins ); + Vec_PtrFree( vFanouts ); + Vec_PtrFree( vNodes ); + ABC_FREE( pPermFanin ); + ABC_FREE( pPermFanout ); + return 1; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 9939a54e..ba207359 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -3909,10 +3909,12 @@ int Abc_CommandEliminate( Abc_Frame_t * pAbc, int argc, char ** argv ) int nIterMax; int fGreedy; int fReverse; + int fSpecial; int fVerbose; int c; extern int Abc_NtkEliminate( Abc_Ntk_t * pNtk, int nMaxSize, int fReverse, int fVerbose ); extern int Abc_NtkEliminate1( Abc_Ntk_t * pNtk, int ElimValue, int nMaxSize, int nIterMax, int fReverse, int fVerbose ); + extern int Abc_NtkEliminateSpecial( Abc_Ntk_t * pNtk, int nMaxSize, int fVerbose ); // set the defaults ElimValue = -1; @@ -3920,9 +3922,10 @@ int Abc_CommandEliminate( Abc_Frame_t * pAbc, int argc, char ** argv ) nIterMax = 1; fGreedy = 0; fReverse = 0; + fSpecial = 0; fVerbose = 0; Extra_UtilGetoptReset(); - while ( (c = Extra_UtilGetopt(argc, argv, "VNIgrvh")) != EOF ) + while ( (c = Extra_UtilGetopt(argc, argv, "VNIgrsvh")) != EOF ) { switch (c) { @@ -3965,6 +3968,9 @@ int Abc_CommandEliminate( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'r': fReverse ^= 1; break; + case 's': + fSpecial ^= 1; + break; case 'v': fVerbose ^= 1; break; @@ -3994,14 +4000,16 @@ int Abc_CommandEliminate( Abc_Frame_t * pAbc, int argc, char ** argv ) return 1; } - if ( fGreedy ) + if ( fSpecial ) + Abc_NtkEliminateSpecial( pNtk, 1000, fVerbose ); + else if ( fGreedy ) Abc_NtkEliminate( pNtk, nMaxSize, fReverse, fVerbose ); else Abc_NtkEliminate1( pNtk, ElimValue, nMaxSize, nIterMax, fReverse, fVerbose ); return 0; usage: - Abc_Print( -2, "usage: eliminate [-VNI ] [-grvh]\n"); + Abc_Print( -2, "usage: eliminate [-VNI ] [-grsvh]\n"); Abc_Print( -2, "\t traditional \"eliminate -1\", which collapses the node into its fanout\n"); Abc_Print( -2, "\t if the node's variable appears in the fanout's factored form only once\n"); Abc_Print( -2, "\t-V : the \"value\" parameter used by \"eliminate\" in SIS [default = %d]\n", ElimValue ); @@ -4009,6 +4017,7 @@ usage: Abc_Print( -2, "\t-I : the maximum number of iterations [default = %d]\n", nIterMax ); Abc_Print( -2, "\t-g : toggle using greedy eliminate (without \"value\") [default = %s]\n", fGreedy? "yes": "no" ); Abc_Print( -2, "\t-r : use the reverse topological order [default = %s]\n", fReverse? "yes": "no" ); + Abc_Print( -2, "\t-s : toggle eliminating similar nodes [default = %s]\n", fSpecial? "yes": "no" ); Abc_Print( -2, "\t-v : print verbose information [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); return 1; -- cgit v1.2.3