abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
mfsDiv.c File Reference
#include "mfsInt.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START void Abc_MfsWinMarkTfi_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vCone)
 DECLARATIONS ///. More...
 
Vec_Ptr_t * Abc_MfsWinMarkTfi (Abc_Obj_t *pNode)
 
void Abc_MfsWinSweepLeafTfo_rec (Abc_Obj_t *pObj, int nLevelLimit)
 
int Abc_MfsNodeDeref_rec (Abc_Obj_t *pNode)
 
int Abc_MfsNodeRef_rec (Abc_Obj_t *pNode)
 
int Abc_MfsWinVisitMffc (Abc_Obj_t *pNode)
 
Vec_Ptr_t * Abc_MfsComputeDivisors (Mfs_Man_t *p, Abc_Obj_t *pNode, int nLevDivMax)
 BASIC TYPES ///. More...
 

Function Documentation

Vec_Ptr_t* Abc_MfsComputeDivisors ( Mfs_Man_t *  p,
Abc_Obj_t *  pNode,
int  nLevDivMax 
)

BASIC TYPES ///.

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

Synopsis [Computes divisors and add them to nodes in the window.]

Description []

SideEffects []

SeeAlso []

Definition at line 193 of file mfsDiv.c.

194 {
195  Vec_Ptr_t * vCone, * vDivs;
196  Abc_Obj_t * pObj, * pFanout, * pFanin;
197  int k, f, m;
198  int nDivsPlus = 0, nTrueSupp;
199  assert( p->vDivs == NULL );
200 
201  // mark the TFI with the current trav ID
202  Abc_NtkIncrementTravId( pNode->pNtk );
203  vCone = Abc_MfsWinMarkTfi( pNode );
204 
205  // count the number of PIs
206  nTrueSupp = 0;
207  Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, k )
208  nTrueSupp += Abc_ObjIsCi(pObj);
209 // printf( "%d(%d) ", Vec_PtrSize(p->vSupp), m );
210 
211  // mark with the current trav ID those nodes that should not be divisors:
212  // (1) the node and its TFO
213  // (2) the MFFC of the node
214  // (3) the node's fanins (these are treated as a special case)
215  Abc_NtkIncrementTravId( pNode->pNtk );
216  Abc_MfsWinSweepLeafTfo_rec( pNode, nLevDivMax );
217 // Abc_MfsWinVisitMffc( pNode );
218  Abc_ObjForEachFanin( pNode, pObj, k )
219  Abc_NodeSetTravIdCurrent( pObj );
220 
221  // at this point the nodes are marked with two trav IDs:
222  // nodes to be collected as divisors are marked with previous trav ID
223  // nodes to be avoided as divisors are marked with current trav ID
224 
225  // start collecting the divisors
226  vDivs = Vec_PtrAlloc( p->pPars->nWinMax );
227  Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, k )
228  {
229  if ( !Abc_NodeIsTravIdPrevious(pObj) )
230  continue;
231  if ( (int)pObj->Level > nLevDivMax )
232  continue;
233  Vec_PtrPush( vDivs, pObj );
234  if ( Vec_PtrSize(vDivs) >= p->pPars->nWinMax )
235  break;
236  }
237  Vec_PtrFree( vCone );
238 
239  // explore the fanouts of already collected divisors
240  if ( Vec_PtrSize(vDivs) < p->pPars->nWinMax )
241  Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pObj, k )
242  {
243  // consider fanouts of this node
244  Abc_ObjForEachFanout( pObj, pFanout, f )
245  {
246  // stop if there are too many fanouts
247  if ( p->pPars->nFanoutsMax && f > p->pPars->nFanoutsMax )
248  break;
249  // skip nodes that are already added
250  if ( Abc_NodeIsTravIdPrevious(pFanout) )
251  continue;
252  // skip nodes in the TFO or in the MFFC of node
253  if ( Abc_NodeIsTravIdCurrent(pFanout) )
254  continue;
255  // skip COs
256  if ( !Abc_ObjIsNode(pFanout) )
257  continue;
258  // skip nodes with large level
259  if ( (int)pFanout->Level > nLevDivMax )
260  continue;
261  // skip nodes whose fanins are not divisors -- here we skip more than we need to skip!!! (revise later) August 7, 2009
262  Abc_ObjForEachFanin( pFanout, pFanin, m )
263  if ( !Abc_NodeIsTravIdPrevious(pFanin) )
264  break;
265  if ( m < Abc_ObjFaninNum(pFanout) )
266  continue;
267  // make sure this divisor in not among the nodes
268 // Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodes, pFanin, m )
269 // assert( pFanout != pFanin );
270  // add the node to the divisors
271  Vec_PtrPush( vDivs, pFanout );
272 // Vec_PtrPush( p->vNodes, pFanout );
273  Vec_PtrPushUnique( p->vNodes, pFanout );
274  Abc_NodeSetTravIdPrevious( pFanout );
275  nDivsPlus++;
276  if ( Vec_PtrSize(vDivs) >= p->pPars->nWinMax )
277  break;
278  }
279  if ( Vec_PtrSize(vDivs) >= p->pPars->nWinMax )
280  break;
281  }
282  p->nMaxDivs += (Vec_PtrSize(vDivs) >= p->pPars->nWinMax);
283 
284  // sort the divisors by level in the increasing order
285  Vec_PtrSort( vDivs, (int (*)(void))Abc_NodeCompareLevelsIncrease );
286 
287  // add the fanins of the node
288  Abc_ObjForEachFanin( pNode, pFanin, k )
289  Vec_PtrPush( vDivs, pFanin );
290 
291 /*
292  printf( "Node level = %d. ", Abc_ObjLevel(p->pNode) );
293  Vec_PtrForEachEntryStart( Abc_Obj_t *, vDivs, pObj, k, Vec_PtrSize(vDivs)-p->nDivsPlus )
294  printf( "%d ", Abc_ObjLevel(pObj) );
295  printf( "\n" );
296 */
297 //printf( "%d ", p->nDivsPlus );
298 // printf( "(%d+%d)(%d+%d+%d) ", Vec_PtrSize(p->vSupp), Vec_PtrSize(p->vNodes),
299 // nTrueSupp, Vec_PtrSize(vDivs)-nTrueSupp-nDivsPlus, nDivsPlus );
300  return vDivs;
301 }
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_MfsWinSweepLeafTfo_rec
void Abc_MfsWinSweepLeafTfo_rec(Abc_Obj_t *pObj, int nLevelLimit)
Definition: mfsDiv.c:94
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Vec_PtrPushUnique
static int Vec_PtrPushUnique(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:656
Mfs_Man_t_::pPars
Mfs_Par_t * pPars
Definition: mfsInt.h:53
Abc_NodeSetTravIdPrevious
static void Abc_NodeSetTravIdPrevious(Abc_Obj_t *p)
Definition: abc.h:410
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Vec_PtrSort
static void Vec_PtrSort(Vec_Ptr_t *p, int(*Vec_PtrSortCompare)()) ___unused
Definition: vecPtr.h:851
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Abc_NodeIsTravIdPrevious
static int Abc_NodeIsTravIdPrevious(Abc_Obj_t *p)
Definition: abc.h:412
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Mfs_Man_t_::vDivs
Vec_Ptr_t * vDivs
Definition: mfsInt.h:62
Abc_Obj_t_::Level
unsigned Level
Definition: abc.h:142
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NodeCompareLevelsIncrease
ABC_DLL int Abc_NodeCompareLevelsIncrease(Abc_Obj_t **pp1, Abc_Obj_t **pp2)
Definition: abcUtil.c:1649
Abc_MfsWinMarkTfi
Vec_Ptr_t * Abc_MfsWinMarkTfi(Abc_Obj_t *pNode)
Definition: mfsDiv.c:75
if
if(last==0)
Definition: sparse_int.h:34
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Abc_NtkIncrementTravId
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
int Abc_MfsNodeDeref_rec ( Abc_Obj_t *  pNode)

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

Synopsis [Dereferences the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 118 of file mfsDiv.c.

119 {
120  Abc_Obj_t * pFanin;
121  int i, Counter = 1;
122  if ( Abc_ObjIsCi(pNode) )
123  return 0;
124  Abc_NodeSetTravIdCurrent( pNode );
125  Abc_ObjForEachFanin( pNode, pFanin, i )
126  {
127  assert( pFanin->vFanouts.nSize > 0 );
128  if ( --pFanin->vFanouts.nSize == 0 )
129  Counter += Abc_MfsNodeDeref_rec( pFanin );
130  }
131  return Counter;
132 }
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_Obj_t_
Definition: abc.h:128
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_Obj_t_::vFanouts
Vec_Int_t vFanouts
Definition: abc.h:144
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
assert
#define assert(ex)
Definition: util_old.h:213
Abc_MfsNodeDeref_rec
int Abc_MfsNodeDeref_rec(Abc_Obj_t *pNode)
Definition: mfsDiv.c:118
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
int Abc_MfsNodeRef_rec ( Abc_Obj_t *  pNode)

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

Synopsis [References the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 145 of file mfsDiv.c.

146 {
147  Abc_Obj_t * pFanin;
148  int i, Counter = 1;
149  if ( Abc_ObjIsCi(pNode) )
150  return 0;
151  Abc_ObjForEachFanin( pNode, pFanin, i )
152  {
153  if ( pFanin->vFanouts.nSize++ == 0 )
154  Counter += Abc_MfsNodeRef_rec( pFanin );
155  }
156  return Counter;
157 }
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_MfsNodeRef_rec
int Abc_MfsNodeRef_rec(Abc_Obj_t *pNode)
Definition: mfsDiv.c:145
Abc_Obj_t_
Definition: abc.h:128
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_Obj_t_::vFanouts
Vec_Int_t vFanouts
Definition: abc.h:144
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Vec_Ptr_t* Abc_MfsWinMarkTfi ( Abc_Obj_t *  pNode)

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

Synopsis [Marks and collects the TFI cone of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 75 of file mfsDiv.c.

76 {
77  Vec_Ptr_t * vCone;
78  vCone = Vec_PtrAlloc( 100 );
79  Abc_MfsWinMarkTfi_rec( pNode, vCone );
80  return vCone;
81 }
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_MfsWinMarkTfi_rec
ABC_NAMESPACE_IMPL_START void Abc_MfsWinMarkTfi_rec(Abc_Obj_t *pObj, Vec_Ptr_t *vCone)
DECLARATIONS ///.
Definition: mfsDiv.c:45
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_NAMESPACE_IMPL_START void Abc_MfsWinMarkTfi_rec ( Abc_Obj_t *  pObj,
Vec_Ptr_t *  vCone 
)

DECLARATIONS ///.

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

FileName [mfsDiv.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [The good old minimization with complete don't-cares.]

Synopsis [Procedures to compute candidate divisors.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Marks and collects the TFI cone of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file mfsDiv.c.

46 {
47  Abc_Obj_t * pFanin;
48  int i;
49  if ( Abc_NodeIsTravIdCurrent(pObj) )
50  return;
51  Abc_NodeSetTravIdCurrent( pObj );
52  if ( Abc_ObjIsCi(pObj) )
53  {
54  Vec_PtrPush( vCone, pObj );
55  return;
56  }
57  assert( Abc_ObjIsNode(pObj) );
58  // visit the fanins of the node
59  Abc_ObjForEachFanin( pObj, pFanin, i )
60  Abc_MfsWinMarkTfi_rec( pFanin, vCone );
61  Vec_PtrPush( vCone, pObj );
62 }
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_MfsWinMarkTfi_rec
ABC_NAMESPACE_IMPL_START void Abc_MfsWinMarkTfi_rec(Abc_Obj_t *pObj, Vec_Ptr_t *vCone)
DECLARATIONS ///.
Definition: mfsDiv.c:45
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
assert
#define assert(ex)
Definition: util_old.h:213
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
void Abc_MfsWinSweepLeafTfo_rec ( Abc_Obj_t *  pObj,
int  nLevelLimit 
)

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

Synopsis [Marks the TFO of the collected nodes up to the given level.]

Description []

SideEffects []

SeeAlso []

Definition at line 94 of file mfsDiv.c.

95 {
96  Abc_Obj_t * pFanout;
97  int i;
98  if ( Abc_ObjIsCo(pObj) || (int)pObj->Level > nLevelLimit )
99  return;
100  if ( Abc_NodeIsTravIdCurrent(pObj) )
101  return;
102  Abc_NodeSetTravIdCurrent( pObj );
103  Abc_ObjForEachFanout( pObj, pFanout, i )
104  Abc_MfsWinSweepLeafTfo_rec( pFanout, nLevelLimit );
105 }
Abc_MfsWinSweepLeafTfo_rec
void Abc_MfsWinSweepLeafTfo_rec(Abc_Obj_t *pObj, int nLevelLimit)
Definition: mfsDiv.c:94
Abc_Obj_t_::Level
unsigned Level
Definition: abc.h:142
Abc_ObjIsCo
static int Abc_ObjIsCo(Abc_Obj_t *pObj)
Definition: abc.h:352
Abc_Obj_t_
Definition: abc.h:128
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
int Abc_MfsWinVisitMffc ( Abc_Obj_t *  pNode)

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

Synopsis [Labels MFFC of the node with the current trav ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 170 of file mfsDiv.c.

171 {
172  int Count1, Count2;
173  assert( Abc_ObjIsNode(pNode) );
174  // dereference the node (mark with the current trav ID)
175  Count1 = Abc_MfsNodeDeref_rec( pNode );
176  // reference it back
177  Count2 = Abc_MfsNodeRef_rec( pNode );
178  assert( Count1 == Count2 );
179  return Count1;
180 }
Abc_MfsNodeRef_rec
int Abc_MfsNodeRef_rec(Abc_Obj_t *pNode)
Definition: mfsDiv.c:145
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
assert
#define assert(ex)
Definition: util_old.h:213
Abc_MfsNodeDeref_rec
int Abc_MfsNodeDeref_rec(Abc_Obj_t *pNode)
Definition: mfsDiv.c:118