abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
abcMinBase.c File Reference
#include "abc.h"
#include "misc/extra/extraBdd.h"

Go to the source code of this file.

Functions

static ABC_NAMESPACE_IMPL_START int Abc_NodeSupport (DdNode *bFunc, Vec_Str_t *vSupport, int nVars)
 DECLARATIONS ///. More...
 
int Abc_NtkMinimumBase (Abc_Ntk_t *pNtk)
 FUNCTION DEFINITIONS ///. More...
 
int Abc_NodeMinimumBase (Abc_Obj_t *pNode)
 
int Abc_NtkRemoveDupFanins (Abc_Ntk_t *pNtk)
 
int Abc_NodeRemoveDupFanins_int (Abc_Obj_t *pNode)
 
int Abc_NodeRemoveDupFanins (Abc_Obj_t *pNode)
 
void Abc_NodeSupport_rec (DdNode *bFunc, Vec_Str_t *vSupport)
 
void Abc_NodeSupportClear_rec (DdNode *bFunc)
 
int Abc_NodeCheckDupFanin (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, int *piFanin)
 
int Abc_NodeCollapseSuppSize (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins)
 
int Abc_ObjFaninNumberNew (Vec_Ptr_t *vFanins, Abc_Obj_t *pFanin)
 
int Abc_NodeCollapsePermMap (Abc_Obj_t *pNode, Abc_Obj_t *pSkip, Vec_Ptr_t *vFanins, int *pPerm)
 
DdNode * Abc_NodeCollapseFunc (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
 
int Abc_NodeCollapse (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
 
int Abc_NtkEliminate (Abc_Ntk_t *pNtk, int nMaxSize, int fReverse, int fVerbose)
 
int Abc_NodeCountAppearances (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout)
 
int Abc_NodeCountAppearancesAll (Abc_Obj_t *pNode)
 
Hop_Obj_t * Abc_NodeCollapseFunc1 (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
 
int Abc_NodeCollapse1 (Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
 
int Abc_NodeIsExor (Abc_Obj_t *pNode)
 
int Abc_NtkEliminate1One (Abc_Ntk_t *pNtk, int ElimValue, int nMaxSize, int fReverse, int fVerbose)
 
int Abc_NtkEliminate1 (Abc_Ntk_t *pNtk, int ElimValue, int nMaxSize, int nIterMax, int fReverse, int fVerbose)
 
int Abc_ObjCompareByNumber (Abc_Obj_t **pp1, Abc_Obj_t **pp2)
 
void Abc_ObjSortInReverseOrder (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes)
 
int Abc_NtkEliminateSpecial (Abc_Ntk_t *pNtk, int nMaxSize, int fVerbose)
 

Function Documentation

int Abc_NodeCheckDupFanin ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout,
int *  piFanin 
)

Function*************************************************************

Synopsis [Find the number of unique variables after collapsing.]

Description []

SideEffects []

SeeAlso []

Definition at line 269 of file abcMinBase.c.

270 {
271  Abc_Obj_t * pObj;
272  int i, Counter = 0;
273  Abc_ObjForEachFanin( pFanout, pObj, i )
274  if ( pObj == pFanin )
275  {
276  if ( piFanin )
277  *piFanin = i;
278  Counter++;
279  }
280  return Counter;
281 }
Abc_Obj_t_
Definition: abc.h:128
if
if(last==0)
Definition: sparse_int.h:34
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
int Abc_NodeCollapse ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout,
Vec_Ptr_t *  vFanins,
int *  pPermFanin,
int *  pPermFanout 
)

Definition at line 404 of file abcMinBase.c.

405 {
406  Abc_Obj_t * pFanoutNew, * pObj;
407  DdNode * bFanoutNew;
408  int i;
409  assert( Abc_NtkIsBddLogic(pFanin->pNtk) );
410  assert( Abc_ObjIsNode(pFanin) );
411  assert( Abc_ObjIsNode(pFanout) );
412  bFanoutNew = Abc_NodeCollapseFunc( pFanin, pFanout, vFanins, pPermFanin, pPermFanout );
413  if ( bFanoutNew == NULL )
414  return 0;
415  Cudd_Ref( bFanoutNew );
416  // create the new node
417  pFanoutNew = Abc_NtkCreateNode( pFanin->pNtk );
418  Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i )
419  Abc_ObjAddFanin( pFanoutNew, pObj );
420  pFanoutNew->pData = bFanoutNew;
421  // minimize the node
422  Abc_NodeMinimumBase( pFanoutNew );
423  // transfer the fanout
424  Abc_ObjTransferFanout( pFanout, pFanoutNew );
425  assert( Abc_ObjFanoutNum( pFanout ) == 0 );
426  Abc_NtkDeleteObj_rec( pFanout, 1 );
427  return 1;
428 }
DdNode
Definition: cudd.h:278
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_NtkDeleteObj_rec
ABC_DLL void Abc_NtkDeleteObj_rec(Abc_Obj_t *pObj, int fOnlyNodes)
Definition: abcObj.c:273
Abc_ObjAddFanin
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
Abc_Obj_t_
Definition: abc.h:128
Abc_NodeCollapseFunc
DdNode * Abc_NodeCollapseFunc(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
Definition: abcMinBase.c:369
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_ObjTransferFanout
ABC_DLL void Abc_ObjTransferFanout(Abc_Obj_t *pObjOld, Abc_Obj_t *pObjNew)
Definition: abcFanio.c:264
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_NtkIsBddLogic
static int Abc_NtkIsBddLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:265
Abc_NtkCreateNode
static Abc_Obj_t * Abc_NtkCreateNode(Abc_Ntk_t *pNtk)
Definition: abc.h:308
Abc_NodeMinimumBase
int Abc_NodeMinimumBase(Abc_Obj_t *pNode)
Definition: abcMinBase.c:70
assert
#define assert(ex)
Definition: util_old.h:213
Cudd_Ref
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
int Abc_NodeCollapse1 ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout,
Vec_Ptr_t *  vFanins,
int *  pPermFanin,
int *  pPermFanout 
)

Definition at line 559 of file abcMinBase.c.

560 {
561  Abc_Obj_t * pFanoutNew, * pObj;
562  Hop_Obj_t * bFanoutNew;
563  int i;
564  assert( Abc_NtkIsAigLogic(pFanin->pNtk) );
565  assert( Abc_ObjIsNode(pFanin) );
566  assert( Abc_ObjIsNode(pFanout) );
567  bFanoutNew = Abc_NodeCollapseFunc1( pFanin, pFanout, vFanins, pPermFanin, pPermFanout );
568  if ( bFanoutNew == NULL )
569  return 0;
570  // create the new node
571  pFanoutNew = Abc_NtkCreateNode( pFanin->pNtk );
572  Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i )
573  Abc_ObjAddFanin( pFanoutNew, pObj );
574  pFanoutNew->pData = bFanoutNew;
575  // transfer the fanout
576  Abc_ObjTransferFanout( pFanout, pFanoutNew );
577  assert( Abc_ObjFanoutNum( pFanout ) == 0 );
578  Abc_NtkDeleteObj_rec( pFanout, 1 );
579  return 1;
580 }
Abc_NodeCollapseFunc1
Hop_Obj_t * Abc_NodeCollapseFunc1(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
Definition: abcMinBase.c:534
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_NtkDeleteObj_rec
ABC_DLL void Abc_NtkDeleteObj_rec(Abc_Obj_t *pObj, int fOnlyNodes)
Definition: abcObj.c:273
Abc_NtkIsAigLogic
static int Abc_NtkIsAigLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:266
Hop_Obj_t_
Definition: hop.h:65
Abc_ObjAddFanin
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_ObjTransferFanout
ABC_DLL void Abc_ObjTransferFanout(Abc_Obj_t *pObjOld, Abc_Obj_t *pObjNew)
Definition: abcFanio.c:264
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_NtkCreateNode
static Abc_Obj_t * Abc_NtkCreateNode(Abc_Ntk_t *pNtk)
Definition: abc.h:308
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
DdNode* Abc_NodeCollapseFunc ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout,
Vec_Ptr_t *  vFanins,
int *  pPermFanin,
int *  pPermFanout 
)

Function*************************************************************

Synopsis [Eliminates the nodes into their fanouts if the node size does not exceed this number.]

Description []

SideEffects []

SeeAlso []

Definition at line 369 of file abcMinBase.c.

370 {
371  DdManager * dd = (DdManager *)pFanin->pNtk->pManFunc;
372  DdNode * bVar, * bFunc0, * bFunc1, * bTemp, * bFanin, * bFanout;
373  int RetValue, nSize, iFanin;
374  // can only eliminate if fanin occurs in the fanin list of the fanout exactly once
375  if ( Abc_NodeCheckDupFanin( pFanin, pFanout, &iFanin ) != 1 )
376  return NULL;
377  // find the new number of fanins after collapsing
378  nSize = Abc_NodeCollapseSuppSize( pFanin, pFanout, vFanins );
379  bVar = Cudd_bddIthVar( dd, nSize - 1 );
380  assert( nSize <= dd->size );
381  // find the permutation after collapsing
382  RetValue = Abc_NodeCollapsePermMap( pFanin, NULL, vFanins, pPermFanin );
383  assert( RetValue );
384  RetValue = Abc_NodeCollapsePermMap( pFanout, pFanin, vFanins, pPermFanout );
385  assert( RetValue );
386  // cofactor the local function of the node
387  bVar = Cudd_bddIthVar( dd, iFanin );
388  bFunc0 = Cudd_Cofactor( dd, (DdNode *)pFanout->pData, Cudd_Not(bVar) ); Cudd_Ref( bFunc0 );
389  bFunc1 = Cudd_Cofactor( dd, (DdNode *)pFanout->pData, bVar ); Cudd_Ref( bFunc1 );
390  // find the permutation after collapsing
391  bFunc0 = Cudd_bddPermute( dd, bTemp = bFunc0, pPermFanout ); Cudd_Ref( bFunc0 );
392  Cudd_RecursiveDeref( dd, bTemp );
393  bFunc1 = Cudd_bddPermute( dd, bTemp = bFunc1, pPermFanout ); Cudd_Ref( bFunc1 );
394  Cudd_RecursiveDeref( dd, bTemp );
395  bFanin = Cudd_bddPermute( dd, (DdNode *)pFanin->pData, pPermFanin ); Cudd_Ref( bFanin );
396  // create the new function
397  bFanout = Cudd_bddIte( dd, bFanin, bFunc1, bFunc0 ); Cudd_Ref( bFanout );
398  Cudd_RecursiveDeref( dd, bFanin );
399  Cudd_RecursiveDeref( dd, bFunc1 );
400  Cudd_RecursiveDeref( dd, bFunc0 );
401  Cudd_Deref( bFanout );
402  return bFanout;
403 }
Cudd_RecursiveDeref
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
DdNode
Definition: cudd.h:278
Cudd_Not
#define Cudd_Not(node)
Definition: cudd.h:367
Cudd_Deref
void Cudd_Deref(DdNode *node)
Definition: cuddRef.c:438
Cudd_bddIte
DdNode * Cudd_bddIte(DdManager *dd, DdNode *f, DdNode *g, DdNode *h)
Definition: cuddBddIte.c:143
Abc_NodeCollapseSuppSize
int Abc_NodeCollapseSuppSize(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins)
Definition: abcMinBase.c:294
Abc_NodeCollapsePermMap
int Abc_NodeCollapsePermMap(Abc_Obj_t *pNode, Abc_Obj_t *pSkip, Vec_Ptr_t *vFanins, int *pPerm)
Definition: abcMinBase.c:339
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Cudd_Cofactor
DdNode * Cudd_Cofactor(DdManager *dd, DdNode *f, DdNode *g)
Definition: cuddCof.c:123
Cudd_bddPermute
DdNode * Cudd_bddPermute(DdManager *manager, DdNode *node, int *permut)
Definition: cuddCompose.c:332
if
if(last==0)
Definition: sparse_int.h:34
size
static int size
Definition: cuddSign.c:86
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_NodeCheckDupFanin
int Abc_NodeCheckDupFanin(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, int *piFanin)
Definition: abcMinBase.c:269
Cudd_bddIthVar
DdNode * Cudd_bddIthVar(DdManager *dd, int i)
Definition: cuddAPI.c:416
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Cudd_Ref
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
Hop_Obj_t* Abc_NodeCollapseFunc1 ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout,
Vec_Ptr_t *  vFanins,
int *  pPermFanin,
int *  pPermFanout 
)

Function*************************************************************

Synopsis [Performs traditional eliminate -1.]

Description []

SideEffects []

SeeAlso []

Definition at line 534 of file abcMinBase.c.

535 {
536  Hop_Man_t * pMan = (Hop_Man_t *)pFanin->pNtk->pManFunc;
537  Hop_Obj_t * bFanin, * bFanout;
538  int RetValue, nSize, iFanin;
539  // can only eliminate if fanin occurs in the fanin list of the fanout exactly once
540  if ( Abc_NodeCheckDupFanin( pFanin, pFanout, &iFanin ) != 1 )
541  return NULL;
542  // find the new number of fanins after collapsing
543  nSize = Abc_NodeCollapseSuppSize( pFanin, pFanout, vFanins );
544  Hop_IthVar( pMan, nSize ); // use additional var for fanin variable
545  assert( nSize + 1 <= Hop_ManPiNum(pMan) );
546  // find the permutation after collapsing
547  RetValue = Abc_NodeCollapsePermMap( pFanin, NULL, vFanins, pPermFanin );
548  assert( RetValue );
549  RetValue = Abc_NodeCollapsePermMap( pFanout, pFanin, vFanins, pPermFanout );
550  assert( RetValue );
551  // include fanin's variable
552  pPermFanout[iFanin] = nSize;
553  // create new function of fanin and fanout
554  bFanin = Hop_Permute( pMan, (Hop_Obj_t *)pFanin->pData, Abc_ObjFaninNum(pFanin), pPermFanin );
555  bFanout = Hop_Permute( pMan, (Hop_Obj_t *)pFanout->pData, Abc_ObjFaninNum(pFanout), pPermFanout );
556  // compose fanin into fanout
557  return Hop_Compose( pMan, bFanout, bFanin, nSize );
558 }
Hop_Compose
Hop_Obj_t * Hop_Compose(Hop_Man_t *p, Hop_Obj_t *pRoot, Hop_Obj_t *pFunc, int iVar)
Definition: hopDfs.c:415
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Abc_NodeCollapseSuppSize
int Abc_NodeCollapseSuppSize(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins)
Definition: abcMinBase.c:294
Abc_NodeCollapsePermMap
int Abc_NodeCollapsePermMap(Abc_Obj_t *pNode, Abc_Obj_t *pSkip, Vec_Ptr_t *vFanins, int *pPerm)
Definition: abcMinBase.c:339
Hop_Obj_t_
Definition: hop.h:65
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Hop_Permute
Hop_Obj_t * Hop_Permute(Hop_Man_t *p, Hop_Obj_t *pRoot, int nRootVars, int *pPermute)
Definition: hopDfs.c:563
if
if(last==0)
Definition: sparse_int.h:34
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_NodeCheckDupFanin
int Abc_NodeCheckDupFanin(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, int *piFanin)
Definition: abcMinBase.c:269
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Hop_Man_t
typedefABC_NAMESPACE_HEADER_START struct Hop_Man_t_ Hop_Man_t
INCLUDES ///.
Definition: hop.h:49
Hop_IthVar
Hop_Obj_t * Hop_IthVar(Hop_Man_t *p, int i)
FUNCTION DEFINITIONS ///.
Definition: hopOper.c:63
Hop_ManPiNum
static int Hop_ManPiNum(Hop_Man_t *p)
Definition: hop.h:145
int Abc_NodeCollapsePermMap ( Abc_Obj_t *  pNode,
Abc_Obj_t *  pSkip,
Vec_Ptr_t *  vFanins,
int *  pPerm 
)

Function*************************************************************

Synopsis [Find the permutation map for the given node into the new order.]

Description []

SideEffects []

SeeAlso []

Definition at line 339 of file abcMinBase.c.

340 {
341  Abc_Obj_t * pFanin;
342  int i;
343  for ( i = 0; i < Vec_PtrSize(vFanins); i++ )
344  pPerm[i] = i;
345  Abc_ObjForEachFanin( pNode, pFanin, i )
346  {
347  if ( pFanin == pSkip )
348  continue;
349  pPerm[i] = Abc_ObjFaninNumberNew( vFanins, pFanin );
350  if ( pPerm[i] == -1 )
351  return 0;
352  }
353  return 1;
354 }
Abc_ObjFaninNumberNew
int Abc_ObjFaninNumberNew(Vec_Ptr_t *vFanins, Abc_Obj_t *pFanin)
Definition: abcMinBase.c:318
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Abc_Obj_t_
Definition: abc.h:128
pPerm
static int pPerm[13719]
Definition: rwrTemp.c:32
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
int Abc_NodeCollapseSuppSize ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout,
Vec_Ptr_t *  vFanins 
)

Function*************************************************************

Synopsis [Find the number of unique variables after collapsing.]

Description []

SideEffects []

SeeAlso []

Definition at line 294 of file abcMinBase.c.

295 {
296  Abc_Obj_t * pObj;
297  int i;
298  Vec_PtrClear( vFanins );
299  Abc_ObjForEachFanin( pFanout, pObj, i )
300  if ( pObj != pFanin )
301  Vec_PtrPushUnique( vFanins, pObj );
302  Abc_ObjForEachFanin( pFanin, pObj, i )
303  Vec_PtrPushUnique( vFanins, pObj );
304  return Vec_PtrSize( vFanins );
305 }
Vec_PtrPushUnique
static int Vec_PtrPushUnique(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:656
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Abc_Obj_t_
Definition: abc.h:128
if
if(last==0)
Definition: sparse_int.h:34
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
int Abc_NodeCountAppearances ( Abc_Obj_t *  pFanin,
Abc_Obj_t *  pFanout 
)

Function*************************************************************

Synopsis [Check how many times fanin appears in the FF of the fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 507 of file abcMinBase.c.

508 {
509  Hop_Man_t * pMan = (Hop_Man_t *)pFanin->pNtk->pManFunc;
510  int iFanin = Abc_NodeFindFanin( pFanout, pFanin );
511  assert( iFanin >= 0 && iFanin < Hop_ManPiNum(pMan) );
512  return Hop_ObjFanoutCount( (Hop_Obj_t *)pFanout->pData, Hop_IthVar(pMan, iFanin) );
513 }
Hop_ObjFanoutCount
int Hop_ObjFanoutCount(Hop_Obj_t *pObj, Hop_Obj_t *pPivot)
Definition: hopDfs.c:310
Abc_NodeFindFanin
ABC_DLL int Abc_NodeFindFanin(Abc_Obj_t *pNode, Abc_Obj_t *pFanin)
Definition: abcUtil.c:758
Hop_Obj_t_
Definition: hop.h:65
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Hop_Man_t
typedefABC_NAMESPACE_HEADER_START struct Hop_Man_t_ Hop_Man_t
INCLUDES ///.
Definition: hop.h:49
Hop_IthVar
Hop_Obj_t * Hop_IthVar(Hop_Man_t *p, int i)
FUNCTION DEFINITIONS ///.
Definition: hopOper.c:63
Hop_ManPiNum
static int Hop_ManPiNum(Hop_Man_t *p)
Definition: hop.h:145
int Abc_NodeCountAppearancesAll ( Abc_Obj_t *  pNode)

Definition at line 514 of file abcMinBase.c.

515 {
516  Abc_Obj_t * pFanout;
517  int i, Count = 0;
518  Abc_ObjForEachFanout( pNode, pFanout, i )
519  Count += Abc_NodeCountAppearances( pNode, pFanout );
520  return Count;
521 }
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Abc_NodeCountAppearances
int Abc_NodeCountAppearances(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout)
Definition: abcMinBase.c:507
int Abc_NodeIsExor ( Abc_Obj_t *  pNode)

Definition at line 581 of file abcMinBase.c.

582 {
583  Hop_Man_t * pMan;
584  word Truth;
585  if ( Abc_ObjFaninNum(pNode) < 3 || Abc_ObjFaninNum(pNode) > 6 )
586  return 0;
587  pMan = (Hop_Man_t *)pNode->pNtk->pManFunc;
588  Truth = Hop_ManComputeTruth6( pMan, (Hop_Obj_t *)pNode->pData, Abc_ObjFaninNum(pNode) );
589  if ( Truth == 0x6666666666666666 || Truth == 0x9999999999999999 ||
590  Truth == 0x9696969696969696 || Truth == 0x6969696969696969 ||
591  Truth == 0x6996699669966996 || Truth == 0x9669966996699669 ||
592  Truth == 0x9669699696696996 || Truth == 0x6996966969969669 ||
593  Truth == 0x6996966996696996 || Truth == 0x9669699669969669 )
594  return 1;
595  return 0;
596 }
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Hop_ManComputeTruth6
word Hop_ManComputeTruth6(Hop_Man_t *p, Hop_Obj_t *pObj, int nVars)
Definition: hopTruth.c:256
Hop_Obj_t_
Definition: hop.h:65
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
Truth
static ABC_NAMESPACE_IMPL_START word Truth[8]
DECLARATIONS ///.
Definition: giaShrink6.c:32
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Hop_Man_t
typedefABC_NAMESPACE_HEADER_START struct Hop_Man_t_ Hop_Man_t
INCLUDES ///.
Definition: hop.h:49
int Abc_NodeMinimumBase ( Abc_Obj_t *  pNode)

Function*************************************************************

Synopsis [Makes one node minimum base.]

Description [Returns 1 if the node is changed.]

SideEffects []

SeeAlso []

Definition at line 70 of file abcMinBase.c.

71 {
72  Vec_Str_t * vSupport;
73  Vec_Ptr_t * vFanins;
74  DdNode * bTemp;
75  int i, nVars;
76 
77  assert( Abc_NtkIsBddLogic(pNode->pNtk) );
78  assert( Abc_ObjIsNode(pNode) );
79 
80  // compute support
81  vSupport = Vec_StrAlloc( 10 );
82  nVars = Abc_NodeSupport( Cudd_Regular(pNode->pData), vSupport, Abc_ObjFaninNum(pNode) );
83  if ( nVars == Abc_ObjFaninNum(pNode) )
84  {
85  Vec_StrFree( vSupport );
86  return 0;
87  }
88 
89  // remove unused fanins
90  vFanins = Vec_PtrAlloc( Abc_ObjFaninNum(pNode) );
91  Abc_NodeCollectFanins( pNode, vFanins );
92  for ( i = 0; i < vFanins->nSize; i++ )
93  if ( vSupport->pArray[i] == 0 )
94  Abc_ObjDeleteFanin( pNode, (Abc_Obj_t *)vFanins->pArray[i] );
95  assert( nVars == Abc_ObjFaninNum(pNode) );
96 
97  // update the function of the node
98  pNode->pData = Extra_bddRemapUp( (DdManager *)pNode->pNtk->pManFunc, bTemp = (DdNode *)pNode->pData ); Cudd_Ref( (DdNode *)pNode->pData );
99  Cudd_RecursiveDeref( (DdManager *)pNode->pNtk->pManFunc, bTemp );
100  Vec_PtrFree( vFanins );
101  Vec_StrFree( vSupport );
102  return 1;
103 }
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Cudd_RecursiveDeref
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
DdNode
Definition: cudd.h:278
Cudd_Regular
#define Cudd_Regular(node)
Definition: cudd.h:397
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Vec_StrAlloc
static Vec_Str_t * Vec_StrAlloc(int nCap)
Definition: bblif.c:495
Abc_Obj_t_
Definition: abc.h:128
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NodeSupport
static ABC_NAMESPACE_IMPL_START int Abc_NodeSupport(DdNode *bFunc, Vec_Str_t *vSupport, int nVars)
DECLARATIONS ///.
Definition: abcMinBase.c:241
Vec_Str_t_::pArray
char * pArray
Definition: bblif.c:51
Vec_StrFree
static void Vec_StrFree(Vec_Str_t *p)
Definition: bblif.c:616
Extra_bddRemapUp
DdNode * Extra_bddRemapUp(DdManager *dd, DdNode *bF)
Definition: extraBddMisc.c:145
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Vec_Str_t_
Definition: bblif.c:47
Abc_NtkIsBddLogic
static int Abc_NtkIsBddLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:265
Abc_NodeCollectFanins
ABC_DLL void Abc_NodeCollectFanins(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
Definition: abcUtil.c:1587
Abc_ObjDeleteFanin
ABC_DLL void Abc_ObjDeleteFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:111
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Cudd_Ref
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
int Abc_NodeRemoveDupFanins ( Abc_Obj_t *  pNode)

Function*************************************************************

Synopsis [Removes duplicated fanins if present.]

Description [Returns the number of fanins removed.]

SideEffects []

SeeAlso []

Definition at line 180 of file abcMinBase.c.

181 {
182  int Counter = 0;
183  while ( Abc_NodeRemoveDupFanins_int(pNode) )
184  Counter++;
185  return Counter;
186 }
Abc_NodeRemoveDupFanins_int
int Abc_NodeRemoveDupFanins_int(Abc_Obj_t *pNode)
Definition: abcMinBase.c:138
Counter
static int Counter
Definition: extraBddMisc.c:1877
int Abc_NodeRemoveDupFanins_int ( Abc_Obj_t *  pNode)

Function*************************************************************

Synopsis [Removes one pair of duplicated fanins if present.]

Description [Returns 1 if the node is changed.]

SideEffects []

SeeAlso []

Definition at line 138 of file abcMinBase.c.

139 {
140  Abc_Obj_t * pFanin1, * pFanin2;
141  int i, k;
142  assert( Abc_NtkIsBddLogic(pNode->pNtk) );
143  assert( Abc_ObjIsNode(pNode) );
144  // make sure fanins are not duplicated
145  Abc_ObjForEachFanin( pNode, pFanin2, i )
146  {
147  Abc_ObjForEachFanin( pNode, pFanin1, k )
148  {
149  if ( k >= i )
150  break;
151  if ( pFanin1 == pFanin2 )
152  {
153  DdManager * dd = (DdManager *)pNode->pNtk->pManFunc;
154  DdNode * bVar1 = Cudd_bddIthVar( dd, i );
155  DdNode * bVar2 = Cudd_bddIthVar( dd, k );
156  DdNode * bTrans, * bTemp;
157  bTrans = Cudd_bddXnor( dd, bVar1, bVar2 ); Cudd_Ref( bTrans );
158  pNode->pData = Cudd_bddAndAbstract( dd, bTemp = (DdNode *)pNode->pData, bTrans, bVar2 ); Cudd_Ref( (DdNode *)pNode->pData );
159  Cudd_RecursiveDeref( dd, bTemp );
160  Cudd_RecursiveDeref( dd, bTrans );
161  Abc_NodeMinimumBase( pNode );
162  return 1;
163  }
164  }
165  }
166  return 0;
167 }
Cudd_RecursiveDeref
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
DdNode
Definition: cudd.h:278
Abc_Obj_t_
Definition: abc.h:128
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Cudd_bddAndAbstract
DdNode * Cudd_bddAndAbstract(DdManager *manager, DdNode *f, DdNode *g, DdNode *cube)
Definition: cuddAndAbs.c:124
Cudd_bddXnor
DdNode * Cudd_bddXnor(DdManager *dd, DdNode *f, DdNode *g)
Definition: cuddBddIte.c:507
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Abc_NtkIsBddLogic
static int Abc_NtkIsBddLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:265
Cudd_bddIthVar
DdNode * Cudd_bddIthVar(DdManager *dd, int i)
Definition: cuddAPI.c:416
Abc_NodeMinimumBase
int Abc_NodeMinimumBase(Abc_Obj_t *pNode)
Definition: abcMinBase.c:70
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Cudd_Ref
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
int Abc_NodeSupport ( DdNode *  bFunc,
Vec_Str_t *  vSupport,
int  nVars 
)
static

DECLARATIONS ///.

CFile****************************************************************

FileName [abcMinBase.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Makes nodes of the network minimum base.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:
abcMinBase.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Function*************************************************************

Synopsis [Computes support of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 241 of file abcMinBase.c.

242 {
243  int Counter, i;
244  // compute the support by marking the BDD
245  Vec_StrFill( vSupport, nVars, 0 );
246  Abc_NodeSupport_rec( bFunc, vSupport );
247  // clear the marak
248  Abc_NodeSupportClear_rec( bFunc );
249  // get the number of support variables
250  Counter = 0;
251  for ( i = 0; i < nVars; i++ )
252  Counter += vSupport->pArray[i];
253  return Counter;
254 }
Abc_NodeSupportClear_rec
void Abc_NodeSupportClear_rec(DdNode *bFunc)
Definition: abcMinBase.c:219
Vec_Str_t_::pArray
char * pArray
Definition: bblif.c:51
Vec_StrFill
static void Vec_StrFill(Vec_Str_t *p, int nSize, char Fill)
Definition: vecStr.h:423
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_NodeSupport_rec
void Abc_NodeSupport_rec(DdNode *bFunc, Vec_Str_t *vSupport)
Definition: abcMinBase.c:198
void Abc_NodeSupport_rec ( DdNode *  bFunc,
Vec_Str_t *  vSupport 
)

Function*************************************************************

Synopsis [Computes support of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 198 of file abcMinBase.c.

199 {
200  if ( cuddIsConstant(bFunc) || Cudd_IsComplement(bFunc->next) )
201  return;
202  vSupport->pArray[ bFunc->index ] = 1;
203  Abc_NodeSupport_rec( cuddT(bFunc), vSupport );
204  Abc_NodeSupport_rec( Cudd_Regular(cuddE(bFunc)), vSupport );
205  bFunc->next = Cudd_Not(bFunc->next);
206 }
Cudd_Not
#define Cudd_Not(node)
Definition: cudd.h:367
Cudd_Regular
#define Cudd_Regular(node)
Definition: cudd.h:397
Cudd_IsComplement
#define Cudd_IsComplement(node)
Definition: cudd.h:425
Vec_Str_t_::pArray
char * pArray
Definition: bblif.c:51
DdNode::next
DdNode * next
Definition: cudd.h:281
cuddIsConstant
#define cuddIsConstant(node)
Definition: cuddInt.h:620
cuddT
#define cuddT(node)
Definition: cuddInt.h:636
Abc_NodeSupport_rec
void Abc_NodeSupport_rec(DdNode *bFunc, Vec_Str_t *vSupport)
Definition: abcMinBase.c:198
DdNode::index
DdHalfWord index
Definition: cudd.h:279
cuddE
#define cuddE(node)
Definition: cuddInt.h:652
void Abc_NodeSupportClear_rec ( DdNode *  bFunc)

Function*************************************************************

Synopsis [Computes support of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 219 of file abcMinBase.c.

220 {
221  if ( !Cudd_IsComplement(bFunc->next) )
222  return;
223  bFunc->next = Cudd_Regular(bFunc->next);
224  if ( cuddIsConstant(bFunc) )
225  return;
226  Abc_NodeSupportClear_rec( cuddT(bFunc) );
227  Abc_NodeSupportClear_rec( Cudd_Regular(cuddE(bFunc)) );
228 }
Abc_NodeSupportClear_rec
void Abc_NodeSupportClear_rec(DdNode *bFunc)
Definition: abcMinBase.c:219
Cudd_Regular
#define Cudd_Regular(node)
Definition: cudd.h:397
Cudd_IsComplement
#define Cudd_IsComplement(node)
Definition: cudd.h:425
DdNode::next
DdNode * next
Definition: cudd.h:281
cuddIsConstant
#define cuddIsConstant(node)
Definition: cuddInt.h:620
cuddT
#define cuddT(node)
Definition: cuddInt.h:636
cuddE
#define cuddE(node)
Definition: cuddInt.h:652
int Abc_NtkEliminate ( Abc_Ntk_t *  pNtk,
int  nMaxSize,
int  fReverse,
int  fVerbose 
)

Definition at line 429 of file abcMinBase.c.

430 {
431  extern void Abc_NtkBddReorder( Abc_Ntk_t * pNtk, int fVerbose );
432  Vec_Ptr_t * vFanouts, * vFanins, * vNodes;
433  Abc_Obj_t * pNode, * pFanout;
434  int * pPermFanin, * pPermFanout;
435  int RetValue, i, k;
436  assert( nMaxSize > 0 );
437  assert( Abc_NtkIsLogic(pNtk) );
438  // convert network to BDD representation
439  if ( !Abc_NtkToBdd(pNtk) )
440  {
441  fprintf( stdout, "Converting to BDD has failed.\n" );
442  return 0;
443  }
444  // prepare nodes for sweeping
445  Abc_NtkRemoveDupFanins( pNtk );
446  Abc_NtkMinimumBase( pNtk );
447  Abc_NtkCleanup( pNtk, 0 );
448  // get the nodes in the given order
449  vNodes = fReverse? Abc_NtkDfsReverse( pNtk ) : Abc_NtkDfs( pNtk, 0 );
450  // go through the nodes and decide is they can be eliminated
451  pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 );
452  pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 );
453  vFanins = Vec_PtrAlloc( 1000 );
454  vFanouts = Vec_PtrAlloc( 1000 );
455  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
456  {
457  if ( !Abc_ObjIsNode(pNode) ) // skip deleted nodes
458  continue;
459  if ( Abc_NodeFindCoFanout(pNode) != NULL )
460  continue;
461  if ( Abc_ObjFaninNum(pNode) > nMaxSize )
462  continue;
463  Abc_ObjForEachFanout( pNode, pFanout, k )
464  if ( Abc_NodeCollapseSuppSize(pNode, pFanout, vFanins) > nMaxSize )
465  break;
466  if ( k < Abc_ObjFanoutNum(pNode) )
467  continue;
468  // perform elimination
469  Abc_NodeCollectFanouts( pNode, vFanouts );
470  Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k )
471  {
472  if ( fVerbose )
473  printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ",
474  Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) );
475  RetValue = Abc_NodeCollapse( pNode, pFanout, vFanins, pPermFanin, pPermFanout );
476  assert( RetValue );
477  if ( fVerbose )
478  {
479  Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 );
480  if ( pNodeNew )
481  printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) );
482  }
483  }
484  }
485  Abc_NtkBddReorder( pNtk, 0 );
486  Vec_PtrFree( vFanins );
487  Vec_PtrFree( vFanouts );
488  Vec_PtrFree( vNodes );
489  ABC_FREE( pPermFanin );
490  ABC_FREE( pPermFanout );
491  return 1;
492 }
Abc_ObjId
static unsigned Abc_ObjId(Abc_Obj_t *pObj)
Definition: abc.h:329
Abc_NtkIsLogic
static int Abc_NtkIsLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:250
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_NtkObjNumMax
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
Abc_Ntk_t_
Definition: abc.h:153
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_NtkDfs
ABC_DLL Vec_Ptr_t * Abc_NtkDfs(Abc_Ntk_t *pNtk, int fCollectAll)
Definition: abcDfs.c:81
Abc_NtkCleanup
ABC_DLL int Abc_NtkCleanup(Abc_Ntk_t *pNtk, int fVerbose)
Definition: abcSweep.c:476
Abc_NtkObj
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
Abc_NodeCollapseSuppSize
int Abc_NodeCollapseSuppSize(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins)
Definition: abcMinBase.c:294
Abc_NtkDfsReverse
ABC_DLL Vec_Ptr_t * Abc_NtkDfsReverse(Abc_Ntk_t *pNtk)
Definition: abcDfs.c:190
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NtkMinimumBase
int Abc_NtkMinimumBase(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcMinBase.c:48
Abc_NtkRemoveDupFanins
int Abc_NtkRemoveDupFanins(Abc_Ntk_t *pNtk)
Definition: abcMinBase.c:116
if
if(last==0)
Definition: sparse_int.h:34
Abc_NtkToBdd
ABC_DLL int Abc_NtkToBdd(Abc_Ntk_t *pNtk)
Definition: abcFunc.c:1160
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Abc_NodeFindCoFanout
ABC_DLL Abc_Obj_t * Abc_NodeFindCoFanout(Abc_Obj_t *pNode)
Definition: abcUtil.c:779
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_NodeCollapse
int Abc_NodeCollapse(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
Definition: abcMinBase.c:404
assert
#define assert(ex)
Definition: util_old.h:213
Abc_NodeCollectFanouts
ABC_DLL void Abc_NodeCollectFanouts(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
Definition: abcUtil.c:1607
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Abc_NtkBddReorder
void Abc_NtkBddReorder(Abc_Ntk_t *pNtk, int fVerbose)
Definition: abcReorder.c:77
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
int Abc_NtkEliminate1 ( Abc_Ntk_t *  pNtk,
int  ElimValue,
int  nMaxSize,
int  nIterMax,
int  fReverse,
int  fVerbose 
)

Definition at line 663 of file abcMinBase.c.

664 {
665  int i;
666  for ( i = 0; i < nIterMax; i++ )
667  {
668  int nNodes = Abc_NtkNodeNum(pNtk);
669 // printf( "%d ", nNodes );
670  if ( !Abc_NtkEliminate1One(pNtk, ElimValue, nMaxSize, fReverse, fVerbose) )
671  return 0;
672  if ( nNodes == Abc_NtkNodeNum(pNtk) )
673  break;
674  }
675  return 1;
676 }
Abc_NtkNodeNum
static int Abc_NtkNodeNum(Abc_Ntk_t *pNtk)
Definition: abc.h:293
Abc_NtkEliminate1One
int Abc_NtkEliminate1One(Abc_Ntk_t *pNtk, int ElimValue, int nMaxSize, int fReverse, int fVerbose)
Definition: abcMinBase.c:597
int Abc_NtkEliminate1One ( Abc_Ntk_t *  pNtk,
int  ElimValue,
int  nMaxSize,
int  fReverse,
int  fVerbose 
)

Definition at line 597 of file abcMinBase.c.

598 {
599  Vec_Ptr_t * vFanouts, * vFanins, * vNodes;
600  Abc_Obj_t * pNode, * pFanout;
601  int * pPermFanin, * pPermFanout;
602  int RetValue, i, k;
603  assert( nMaxSize > 0 );
604  assert( Abc_NtkIsLogic(pNtk) );
605  // convert network to BDD representation
606  if ( !Abc_NtkToAig(pNtk) )
607  {
608  fprintf( stdout, "Converting to AIG has failed.\n" );
609  return 0;
610  }
611  // get the nodes in the given order
612  vNodes = fReverse? Abc_NtkDfsReverse( pNtk ) : Abc_NtkDfs( pNtk, 0 );
613  // go through the nodes and decide is they can be eliminated
614  pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 );
615  pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 );
616  vFanins = Vec_PtrAlloc( 1000 );
617  vFanouts = Vec_PtrAlloc( 1000 );
618  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
619  {
620  if ( !Abc_ObjIsNode(pNode) ) // skip deleted nodes
621  continue;
622  if ( Abc_NodeFindCoFanout(pNode) != NULL )
623  continue;
624  if ( Abc_ObjFaninNum(pNode) > nMaxSize )
625  continue;
626  if ( Abc_NodeIsExor(pNode) )
627  continue;
628  // skip nodes with more than one fanout
629 // if ( Abc_ObjFanoutNum(pNode) != 1 )
630 // continue;
631  // skip nodes that appear in the FF of their fanout more than once
632  if ( Abc_NodeCountAppearancesAll( pNode ) > ElimValue + 2 )
633  continue;
634  Abc_ObjForEachFanout( pNode, pFanout, k )
635  if ( Abc_NodeCollapseSuppSize(pNode, pFanout, vFanins) > nMaxSize )
636  break;
637  if ( k < Abc_ObjFanoutNum(pNode) )
638  continue;
639  // perform elimination
640  Abc_NodeCollectFanouts( pNode, vFanouts );
641  Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k )
642  {
643  if ( fVerbose )
644  printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ",
645  Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) );
646  RetValue = Abc_NodeCollapse1( pNode, pFanout, vFanins, pPermFanin, pPermFanout );
647  assert( RetValue );
648  if ( fVerbose )
649  {
650  Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 );
651  if ( pNodeNew )
652  printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) );
653  }
654  }
655  }
656  Vec_PtrFree( vFanins );
657  Vec_PtrFree( vFanouts );
658  Vec_PtrFree( vNodes );
659  ABC_FREE( pPermFanin );
660  ABC_FREE( pPermFanout );
661  return 1;
662 }
Abc_ObjId
static unsigned Abc_ObjId(Abc_Obj_t *pObj)
Definition: abc.h:329
Abc_NtkIsLogic
static int Abc_NtkIsLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:250
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_NtkObjNumMax
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Abc_NodeCountAppearancesAll
int Abc_NodeCountAppearancesAll(Abc_Obj_t *pNode)
Definition: abcMinBase.c:514
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_NtkDfs
ABC_DLL Vec_Ptr_t * Abc_NtkDfs(Abc_Ntk_t *pNtk, int fCollectAll)
Definition: abcDfs.c:81
Abc_NtkObj
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
Abc_NodeCollapseSuppSize
int Abc_NodeCollapseSuppSize(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins)
Definition: abcMinBase.c:294
Abc_NtkDfsReverse
ABC_DLL Vec_Ptr_t * Abc_NtkDfsReverse(Abc_Ntk_t *pNtk)
Definition: abcDfs.c:190
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
if
if(last==0)
Definition: sparse_int.h:34
Abc_NodeCollapse1
int Abc_NodeCollapse1(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
Definition: abcMinBase.c:559
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Abc_NodeFindCoFanout
ABC_DLL Abc_Obj_t * Abc_NodeFindCoFanout(Abc_Obj_t *pNode)
Definition: abcUtil.c:779
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_NodeIsExor
int Abc_NodeIsExor(Abc_Obj_t *pNode)
Definition: abcMinBase.c:581
Abc_NtkToAig
ABC_DLL int Abc_NtkToAig(Abc_Ntk_t *pNtk)
Definition: abcFunc.c:1192
assert
#define assert(ex)
Definition: util_old.h:213
Abc_NodeCollectFanouts
ABC_DLL void Abc_NodeCollectFanouts(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
Definition: abcUtil.c:1607
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
int Abc_NtkEliminateSpecial ( Abc_Ntk_t *  pNtk,
int  nMaxSize,
int  fVerbose 
)

Function*************************************************************

Synopsis [Performs traditional eliminate -1.]

Description []

SideEffects []

SeeAlso []

Definition at line 719 of file abcMinBase.c.

720 {
721  extern void Abc_NtkBddReorder( Abc_Ntk_t * pNtk, int fVerbose );
722  Vec_Ptr_t * vFanouts, * vFanins, * vNodes;
723  Abc_Obj_t * pNode, * pFanout;
724  int * pPermFanin, * pPermFanout;
725  int RetValue, i, k;
726  assert( nMaxSize > 0 );
727  assert( Abc_NtkIsLogic(pNtk) );
728 
729 
730  // convert network to BDD representation
731  if ( !Abc_NtkToBdd(pNtk) )
732  {
733  fprintf( stdout, "Converting to BDD has failed.\n" );
734  return 0;
735  }
736 
737  // prepare nodes for sweeping
738  Abc_NtkRemoveDupFanins( pNtk );
739  Abc_NtkMinimumBase( pNtk );
740  Abc_NtkCleanup( pNtk, 0 );
741 
742  // convert network to SOPs
743  if ( !Abc_NtkToSop(pNtk, 0) )
744  {
745  fprintf( stdout, "Converting to SOP has failed.\n" );
746  return 0;
747  }
748 
749  // collect info about the nodes to be eliminated
750  vNodes = Vec_PtrAlloc( 1000 );
751  Abc_NtkForEachNode( pNtk, pNode, i )
752  {
753  if ( Abc_ObjFanoutNum(pNode) != 1 )
754  continue;
755  pFanout = Abc_ObjFanout0(pNode);
756  if ( !Abc_ObjIsNode(pFanout) )
757  continue;
758  if ( Abc_SopGetCubeNum((char *)pNode->pData) != 1 )
759  continue;
760  if ( Abc_SopGetCubeNum((char *)pFanout->pData) != 1 )
761  continue;
762  // find the fanout's fanin
763  RetValue = Abc_NodeFindFanin( pFanout, pNode );
764  assert( RetValue >= 0 && RetValue < Abc_ObjFaninNum(pFanout) );
765  // both pNode and pFanout are AND/OR type nodes
766  if ( Abc_SopIsComplement((char *)pNode->pData) == Abc_SopGetIthCareLit((char *)pFanout->pData, RetValue) )
767  continue;
768  Vec_PtrPush( vNodes, pNode );
769  }
770  if ( Vec_PtrSize(vNodes) == 0 )
771  {
772  Vec_PtrFree( vNodes );
773  return 1;
774  }
775  Abc_ObjSortInReverseOrder( pNtk, vNodes );
776 
777  // convert network to BDD representation
778  if ( !Abc_NtkToBdd(pNtk) )
779  {
780  fprintf( stdout, "Converting to BDD has failed.\n" );
781  return 0;
782  }
783 
784  // go through the nodes and decide is they can be eliminated
785  pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 );
786  pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 );
787  vFanins = Vec_PtrAlloc( 1000 );
788  vFanouts = Vec_PtrAlloc( 1000 );
789  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
790  {
791  assert( Abc_ObjIsNode(pNode) );
792  assert( Abc_NodeFindCoFanout(pNode) == NULL );
793  // perform elimination
794  Abc_NodeCollectFanouts( pNode, vFanouts );
795  Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k )
796  {
797  if ( fVerbose )
798  printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ",
799  Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) );
800  RetValue = Abc_NodeCollapse( pNode, pFanout, vFanins, pPermFanin, pPermFanout );
801  assert( RetValue );
802  if ( fVerbose )
803  {
804  Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 );
805  if ( pNodeNew )
806  printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) );
807  }
808  }
809  }
810  Abc_NtkBddReorder( pNtk, 0 );
811  Vec_PtrFree( vFanins );
812  Vec_PtrFree( vFanouts );
813  Vec_PtrFree( vNodes );
814  ABC_FREE( pPermFanin );
815  ABC_FREE( pPermFanout );
816  return 1;
817 }
Abc_ObjId
static unsigned Abc_ObjId(Abc_Obj_t *pObj)
Definition: abc.h:329
Abc_NtkIsLogic
static int Abc_NtkIsLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:250
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_NtkObjNumMax
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
Abc_Ntk_t_
Definition: abc.h:153
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_SopGetCubeNum
ABC_DLL int Abc_SopGetCubeNum(char *pSop)
Definition: abcSop.c:489
Abc_NodeFindFanin
ABC_DLL int Abc_NodeFindFanin(Abc_Obj_t *pNode, Abc_Obj_t *pFanin)
Definition: abcUtil.c:758
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_NtkCleanup
ABC_DLL int Abc_NtkCleanup(Abc_Ntk_t *pNtk, int fVerbose)
Definition: abcSweep.c:476
Abc_NtkObj
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_ObjSortInReverseOrder
void Abc_ObjSortInReverseOrder(Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes)
Definition: abcMinBase.c:693
Abc_NtkToSop
ABC_DLL int Abc_NtkToSop(Abc_Ntk_t *pNtk, int fDirect)
Definition: abcFunc.c:1124
Abc_NtkMinimumBase
int Abc_NtkMinimumBase(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcMinBase.c:48
Abc_NtkRemoveDupFanins
int Abc_NtkRemoveDupFanins(Abc_Ntk_t *pNtk)
Definition: abcMinBase.c:116
Abc_NtkToBdd
ABC_DLL int Abc_NtkToBdd(Abc_Ntk_t *pNtk)
Definition: abcFunc.c:1160
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
Abc_SopGetIthCareLit
ABC_DLL int Abc_SopGetIthCareLit(char *pSop, int i)
Definition: abcSop.c:578
Abc_NodeFindCoFanout
ABC_DLL Abc_Obj_t * Abc_NodeFindCoFanout(Abc_Obj_t *pNode)
Definition: abcUtil.c:779
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_NodeCollapse
int Abc_NodeCollapse(Abc_Obj_t *pFanin, Abc_Obj_t *pFanout, Vec_Ptr_t *vFanins, int *pPermFanin, int *pPermFanout)
Definition: abcMinBase.c:404
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Abc_NodeCollectFanouts
ABC_DLL void Abc_NodeCollectFanouts(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
Definition: abcUtil.c:1607
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Abc_SopIsComplement
ABC_DLL int Abc_SopIsComplement(char *pSop)
Definition: abcSop.c:655
Abc_ObjFanout0
static Abc_Obj_t * Abc_ObjFanout0(Abc_Obj_t *pObj)
Definition: abc.h:371
Abc_NtkBddReorder
void Abc_NtkBddReorder(Abc_Ntk_t *pNtk, int fVerbose)
Definition: abcReorder.c:77
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
int Abc_NtkMinimumBase ( Abc_Ntk_t *  pNtk)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Makes nodes minimum base.]

Description [Returns the number of changed nodes.]

SideEffects []

SeeAlso []

Definition at line 48 of file abcMinBase.c.

49 {
50  Abc_Obj_t * pNode;
51  int i, Counter;
52  assert( Abc_NtkIsBddLogic(pNtk) );
53  Counter = 0;
54  Abc_NtkForEachNode( pNtk, pNode, i )
55  Counter += Abc_NodeMinimumBase( pNode );
56  return Counter;
57 }
Abc_Obj_t_
Definition: abc.h:128
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
Abc_NtkIsBddLogic
static int Abc_NtkIsBddLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:265
Abc_NodeMinimumBase
int Abc_NodeMinimumBase(Abc_Obj_t *pNode)
Definition: abcMinBase.c:70
assert
#define assert(ex)
Definition: util_old.h:213
int Abc_NtkRemoveDupFanins ( Abc_Ntk_t *  pNtk)

Function*************************************************************

Synopsis [Makes nodes of the network fanin-dup-free.]

Description [Returns the number of pairs of duplicated fanins.]

SideEffects []

SeeAlso []

Definition at line 116 of file abcMinBase.c.

117 {
118  Abc_Obj_t * pNode;
119  int i, Counter;
120  assert( Abc_NtkIsBddLogic(pNtk) );
121  Counter = 0;
122  Abc_NtkForEachNode( pNtk, pNode, i )
123  Counter += Abc_NodeRemoveDupFanins( pNode );
124  return Counter;
125 }
Abc_Obj_t_
Definition: abc.h:128
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
Abc_NodeRemoveDupFanins
int Abc_NodeRemoveDupFanins(Abc_Obj_t *pNode)
Definition: abcMinBase.c:180
Abc_NtkIsBddLogic
static int Abc_NtkIsBddLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:265
assert
#define assert(ex)
Definition: util_old.h:213
int Abc_ObjCompareByNumber ( Abc_Obj_t **  pp1,
Abc_Obj_t **  pp2 
)

Function*************************************************************

Synopsis [Sort nodes in the reverse topo order.]

Description []

SideEffects []

SeeAlso []

Definition at line 689 of file abcMinBase.c.

690 {
691  return Abc_ObjRegular(*pp1)->iTemp - Abc_ObjRegular(*pp2)->iTemp;
692 }
Abc_Obj_t_::iTemp
int iTemp
Definition: abc.h:149
Abc_ObjRegular
static Abc_Obj_t * Abc_ObjRegular(Abc_Obj_t *p)
Definition: abc.h:323
int Abc_ObjFaninNumberNew ( Vec_Ptr_t *  vFanins,
Abc_Obj_t *  pFanin 
)

Function*************************************************************

Synopsis [Returns the index of the new fanin.]

Description []

SideEffects []

SeeAlso []

Definition at line 318 of file abcMinBase.c.

319 {
320  Abc_Obj_t * pObj;
321  int i;
322  Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i )
323  if ( pObj == pFanin )
324  return i;
325  return -1;
326 }
Abc_Obj_t_
Definition: abc.h:128
if
if(last==0)
Definition: sparse_int.h:34
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
void Abc_ObjSortInReverseOrder ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vNodes 
)

Definition at line 693 of file abcMinBase.c.

694 {
695  Vec_Ptr_t * vOrder;
696  Abc_Obj_t * pNode;
697  int i;
698  vOrder = Abc_NtkDfsReverse( pNtk );
699  Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pNode, i )
700  pNode->iTemp = i;
701  Vec_PtrSort( vNodes, (int (*)())Abc_ObjCompareByNumber );
702  Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pNode, i )
703  pNode->iTemp = 0;
704  Vec_PtrFree( vOrder );
705 }
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Vec_PtrSort
static void Vec_PtrSort(Vec_Ptr_t *p, int(*Vec_PtrSortCompare)()) ___unused
Definition: vecPtr.h:851
Abc_NtkDfsReverse
ABC_DLL Vec_Ptr_t * Abc_NtkDfsReverse(Abc_Ntk_t *pNtk)
Definition: abcDfs.c:190
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjCompareByNumber
int Abc_ObjCompareByNumber(Abc_Obj_t **pp1, Abc_Obj_t **pp2)
Definition: abcMinBase.c:689
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223