abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcMerge.c File Reference
#include "base/abc/abc.h"
#include "aig/aig/aig.h"
#include "opt/nwk/nwkMerge.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START void Abc_NtkMarkFanins_rec (Abc_Obj_t *pLut, int nLevMin)
 DECLARATIONS ///. More...
 
void Abc_NtkMarkFanouts_rec (Abc_Obj_t *pLut, int nLevMax, int nFanMax)
 
void Abc_NtkCollectCircle (Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, int nFanMax)
 
void Abc_NtkCollectNonOverlapCands (Abc_Obj_t *pLut, Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
 
int Abc_NtkCountTotalFanins (Abc_Obj_t *pLut, Abc_Obj_t *pCand)
 
void Abc_NtkCollectOverlapCands (Abc_Obj_t *pLut, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
 
Vec_Int_tAbc_NtkLutMerge (Abc_Ntk_t *pNtk, Nwk_LMPars_t *pPars)
 

Function Documentation

void Abc_NtkCollectCircle ( Vec_Ptr_t vStart,
Vec_Ptr_t vNext,
int  nFanMax 
)

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

Synopsis [Collects the circle of nodes around the given set.]

Description []

SideEffects []

SeeAlso []

Definition at line 101 of file abcMerge.c.

102 {
103  Abc_Obj_t * pObj, * pNext;
104  int i, k;
105  Vec_PtrClear( vNext );
106  Vec_PtrForEachEntry( Abc_Obj_t *, vStart, pObj, i )
107  {
108  Abc_ObjForEachFanin( pObj, pNext, k )
109  {
110  if ( !Abc_ObjIsNode(pNext) )
111  continue;
112  if ( Abc_NodeIsTravIdCurrent( pNext ) )
113  continue;
114  Abc_NodeSetTravIdCurrent( pNext );
115  Vec_PtrPush( vNext, pNext );
116  }
117  Abc_ObjForEachFanout( pObj, pNext, k )
118  {
119  if ( !Abc_ObjIsNode(pNext) )
120  continue;
121  if ( Abc_NodeIsTravIdCurrent( pNext ) )
122  continue;
123  Abc_NodeSetTravIdCurrent( pNext );
124  if ( Abc_ObjFanoutNum(pNext) > nFanMax )
125  continue;
126  Vec_PtrPush( vNext, pNext );
127  }
128  }
129 }
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
void Abc_NtkCollectNonOverlapCands ( Abc_Obj_t pLut,
Vec_Ptr_t vStart,
Vec_Ptr_t vNext,
Vec_Ptr_t vCands,
Nwk_LMPars_t pPars 
)

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

Synopsis [Collects the circle of nodes removes from the given one.]

Description []

SideEffects []

SeeAlso []

Definition at line 142 of file abcMerge.c.

143 {
144  Vec_Ptr_t * vTemp;
145  Abc_Obj_t * pObj;
146  int i, k;
147  Vec_PtrClear( vCands );
148  if ( pPars->nMaxSuppSize - Abc_ObjFaninNum(pLut) <= 1 )
149  return;
150 
151  // collect nodes removed by this distance
152  assert( pPars->nMaxDistance > 0 );
153  Vec_PtrClear( vStart );
154  Vec_PtrPush( vStart, pLut );
155  Abc_NtkIncrementTravId( pLut->pNtk );
156  Abc_NodeSetTravIdCurrent( pLut );
157  for ( i = 1; i <= pPars->nMaxDistance; i++ )
158  {
159  Abc_NtkCollectCircle( vStart, vNext, pPars->nMaxFanout );
160  vTemp = vStart;
161  vStart = vNext;
162  vNext = vTemp;
163  // collect the nodes in vStart
164  Vec_PtrForEachEntry( Abc_Obj_t *, vStart, pObj, k )
165  Vec_PtrPush( vCands, pObj );
166  }
167 
168  // mark the TFI/TFO nodes
169  Abc_NtkIncrementTravId( pLut->pNtk );
170  if ( pPars->fUseTfiTfo )
171  Abc_NodeSetTravIdCurrent( pLut );
172  else
173  {
175  Abc_NtkMarkFanins_rec( pLut, Abc_ObjLevel(pLut) - pPars->nMaxDistance );
177  Abc_NtkMarkFanouts_rec( pLut, Abc_ObjLevel(pLut) + pPars->nMaxDistance, pPars->nMaxFanout );
178  }
179 
180  // collect nodes satisfying the following conditions:
181  // - they are close enough in terms of distance
182  // - they are not in the TFI/TFO of the LUT
183  // - they have no more than the given number of fanins
184  // - they have no more than the given diff in delay
185  k = 0;
186  Vec_PtrForEachEntry( Abc_Obj_t *, vCands, pObj, i )
187  {
188  if ( Abc_NodeIsTravIdCurrent(pObj) )
189  continue;
190  if ( Abc_ObjFaninNum(pLut) + Abc_ObjFaninNum(pObj) > pPars->nMaxSuppSize )
191  continue;
192  if ( Abc_ObjLevel(pLut) - Abc_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
193  Abc_ObjLevel(pObj) - Abc_ObjLevel(pLut) > pPars->nMaxLevelDiff )
194  continue;
195  Vec_PtrWriteEntry( vCands, k++, pObj );
196  }
197  Vec_PtrShrink( vCands, k );
198 }
void Abc_NtkCollectCircle(Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, int nFanMax)
Definition: abcMerge.c:101
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
int nMaxFanout
Definition: nwkMerge.h:52
static void Abc_NodeSetTravIdPrevious(Abc_Obj_t *p)
Definition: abc.h:410
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
int nMaxDistance
Definition: nwkMerge.h:50
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
int nMaxSuppSize
Definition: nwkMerge.h:49
static int Abc_ObjLevel(Abc_Obj_t *pObj)
Definition: abc.h:330
ABC_NAMESPACE_IMPL_START void Abc_NtkMarkFanins_rec(Abc_Obj_t *pLut, int nLevMin)
DECLARATIONS ///.
Definition: abcMerge.c:47
if(last==0)
Definition: sparse_int.h:34
else
Definition: sparse_int.h:55
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
void Abc_NtkMarkFanouts_rec(Abc_Obj_t *pLut, int nLevMax, int nFanMax)
Definition: abcMerge.c:73
Abc_Ntk_t * pNtk
Definition: abc.h:130
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
#define assert(ex)
Definition: util_old.h:213
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
static void Vec_PtrShrink(Vec_Ptr_t *p, int nSizeNew)
Definition: vecPtr.h:528
int nMaxLevelDiff
Definition: nwkMerge.h:51
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
void Abc_NtkCollectOverlapCands ( Abc_Obj_t pLut,
Vec_Ptr_t vCands,
Nwk_LMPars_t pPars 
)

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

Synopsis [Collects overlapping candidates.]

Description []

SideEffects []

SeeAlso []

Definition at line 232 of file abcMerge.c.

233 {
234  Abc_Obj_t * pFanin, * pObj;
235  int i, k;
236  // mark fanins of pLut
237  Abc_ObjForEachFanin( pLut, pFanin, i )
238  pFanin->fMarkC = 1;
239  // collect the matching fanouts of each fanin of the node
240  Vec_PtrClear( vCands );
241  Abc_NtkIncrementTravId( pLut->pNtk );
242  Abc_NodeSetTravIdCurrent( pLut );
243  Abc_ObjForEachFanin( pLut, pFanin, i )
244  {
245  if ( !Abc_ObjIsNode(pFanin) )
246  continue;
247  if ( Abc_ObjFanoutNum(pFanin) > pPars->nMaxFanout )
248  continue;
249  Abc_ObjForEachFanout( pFanin, pObj, k )
250  {
251  if ( !Abc_ObjIsNode(pObj) )
252  continue;
253  if ( Abc_NodeIsTravIdCurrent( pObj ) )
254  continue;
255  Abc_NodeSetTravIdCurrent( pObj );
256  // check the difference in delay
257  if ( Abc_ObjLevel(pLut) - Abc_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
258  Abc_ObjLevel(pObj) - Abc_ObjLevel(pLut) > pPars->nMaxLevelDiff )
259  continue;
260  // check the total number of fanins of the node
261  if ( Abc_NtkCountTotalFanins(pLut, pObj) > pPars->nMaxSuppSize )
262  continue;
263  Vec_PtrPush( vCands, pObj );
264  }
265  }
266  // unmark fanins of pLut
267  Abc_ObjForEachFanin( pLut, pFanin, i )
268  pFanin->fMarkC = 0;
269 }
int nMaxFanout
Definition: nwkMerge.h:52
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
int nMaxSuppSize
Definition: nwkMerge.h:49
static int Abc_ObjLevel(Abc_Obj_t *pObj)
Definition: abc.h:330
int Abc_NtkCountTotalFanins(Abc_Obj_t *pLut, Abc_Obj_t *pCand)
Definition: abcMerge.c:212
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
int nMaxLevelDiff
Definition: nwkMerge.h:51
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
int Abc_NtkCountTotalFanins ( Abc_Obj_t pLut,
Abc_Obj_t pCand 
)

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

Synopsis [Count the total number of fanins.]

Description []

SideEffects []

SeeAlso []

Definition at line 212 of file abcMerge.c.

213 {
214  Abc_Obj_t * pFanin;
215  int i, nCounter = Abc_ObjFaninNum(pLut);
216  Abc_ObjForEachFanin( pCand, pFanin, i )
217  nCounter += !pFanin->fMarkC;
218  return nCounter;
219 }
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Vec_Int_t* Abc_NtkLutMerge ( Abc_Ntk_t pNtk,
Nwk_LMPars_t pPars 
)

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

Synopsis [Performs LUT merging with parameters.]

Description []

SideEffects []

SeeAlso []

Definition at line 282 of file abcMerge.c.

283 {
284  Nwk_Grf_t * p;
285  Vec_Int_t * vResult;
286  Vec_Ptr_t * vStart, * vNext, * vCands1, * vCands2;
287  Abc_Obj_t * pLut, * pCand;
288  int i, k, nVertsMax, nCands;
289  abctime clk = Abc_Clock();
290  // count the number of vertices
291  nVertsMax = 0;
292  Abc_NtkForEachNode( pNtk, pLut, i )
293  nVertsMax += (int)(Abc_ObjFaninNum(pLut) <= pPars->nMaxLutSize);
294  p = Nwk_ManGraphAlloc( nVertsMax );
295  // create graph
296  vStart = Vec_PtrAlloc( 1000 );
297  vNext = Vec_PtrAlloc( 1000 );
298  vCands1 = Vec_PtrAlloc( 1000 );
299  vCands2 = Vec_PtrAlloc( 1000 );
300  nCands = 0;
301  Abc_NtkForEachNode( pNtk, pLut, i )
302  {
303  if ( Abc_ObjFaninNum(pLut) > pPars->nMaxLutSize )
304  continue;
305  Abc_NtkCollectOverlapCands( pLut, vCands1, pPars );
306  if ( pPars->fUseDiffSupp )
307  Abc_NtkCollectNonOverlapCands( pLut, vStart, vNext, vCands2, pPars );
308  if ( Vec_PtrSize(vCands1) == 0 && Vec_PtrSize(vCands2) == 0 )
309  continue;
310  nCands += Vec_PtrSize(vCands1) + Vec_PtrSize(vCands2);
311  // save candidates
312  Vec_PtrForEachEntry( Abc_Obj_t *, vCands1, pCand, k )
313  Nwk_ManGraphHashEdge( p, Abc_ObjId(pLut), Abc_ObjId(pCand) );
314  Vec_PtrForEachEntry( Abc_Obj_t *, vCands2, pCand, k )
315  Nwk_ManGraphHashEdge( p, Abc_ObjId(pLut), Abc_ObjId(pCand) );
316  // print statistics about this node
317  if ( pPars->fVeryVerbose )
318  printf( "Node %6d : Fanins = %d. Fanouts = %3d. Cand1 = %3d. Cand2 = %3d.\n",
319  Abc_ObjId(pLut), Abc_ObjFaninNum(pLut), Abc_ObjFaninNum(pLut),
320  Vec_PtrSize(vCands1), Vec_PtrSize(vCands2) );
321  }
322  Vec_PtrFree( vStart );
323  Vec_PtrFree( vNext );
324  Vec_PtrFree( vCands1 );
325  Vec_PtrFree( vCands2 );
326  if ( pPars->fVerbose )
327  {
328  printf( "Mergable LUTs = %6d. Total cands = %6d. ", p->nVertsMax, nCands );
329  ABC_PRT( "Deriving graph", Abc_Clock() - clk );
330  }
331  // solve the graph problem
332  clk = Abc_Clock();
333  Nwk_ManGraphSolve( p );
334  if ( pPars->fVerbose )
335  {
336  printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
337  p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
338  ABC_PRT( "Solving", Abc_Clock() - clk );
340  }
341  vResult = p->vPairs; p->vPairs = NULL;
342 /*
343  for ( i = 0; i < vResult->nSize; i += 2 )
344  printf( "(%d,%d) ", vResult->pArray[i], vResult->pArray[i+1] );
345  printf( "\n" );
346 */
347  Nwk_ManGraphFree( p );
348  return vResult;
349 }
void Nwk_ManGraphReportMemoryUsage(Nwk_Grf_t *p)
Definition: nwkMerge.c:93
static unsigned Abc_ObjId(Abc_Obj_t *pObj)
Definition: abc.h:329
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
int fUseDiffSupp
Definition: nwkMerge.h:53
static Llb_Mgr_t * p
Definition: llb3Image.c:950
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
void Nwk_ManGraphFree(Nwk_Grf_t *p)
Definition: nwkMerge.c:70
void Nwk_ManGraphSolve(Nwk_Grf_t *p)
Definition: nwkMerge.c:621
static abctime Abc_Clock()
Definition: abc_global.h:279
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
void Abc_NtkCollectNonOverlapCands(Abc_Obj_t *pLut, Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
Definition: abcMerge.c:142
void Nwk_ManGraphHashEdge(Nwk_Grf_t *p, int iLut1, int iLut2)
Definition: nwkMerge.c:119
ABC_NAMESPACE_IMPL_START Nwk_Grf_t * Nwk_ManGraphAlloc(int nVertsMax)
DECLARATIONS ///.
Definition: nwkMerge.c:46
if(last==0)
Definition: sparse_int.h:34
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
#define ABC_PRT(a, t)
Definition: abc_global.h:220
int nMaxLutSize
Definition: nwkMerge.h:48
void Abc_NtkCollectOverlapCands(Abc_Obj_t *pLut, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
Definition: abcMerge.c:232
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
ABC_INT64_T abctime
Definition: abc_global.h:278
int fVerbose
Definition: nwkMerge.h:56
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
ABC_NAMESPACE_IMPL_START void Abc_NtkMarkFanins_rec ( Abc_Obj_t pLut,
int  nLevMin 
)

DECLARATIONS ///.

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

FileName [abcMerge.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [LUT merging algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

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

Synopsis [Marks the fanins of the node with the current trav ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 47 of file abcMerge.c.

48 {
49  Abc_Obj_t * pNext;
50  int i;
51  if ( !Abc_ObjIsNode(pLut) )
52  return;
53  if ( Abc_NodeIsTravIdCurrent( pLut ) )
54  return;
56  if ( Abc_ObjLevel(pLut) < nLevMin )
57  return;
58  Abc_ObjForEachFanin( pLut, pNext, i )
59  Abc_NtkMarkFanins_rec( pNext, nLevMin );
60 }
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
static int Abc_ObjLevel(Abc_Obj_t *pObj)
Definition: abc.h:330
ABC_NAMESPACE_IMPL_START void Abc_NtkMarkFanins_rec(Abc_Obj_t *pLut, int nLevMin)
DECLARATIONS ///.
Definition: abcMerge.c:47
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
void Abc_NtkMarkFanouts_rec ( Abc_Obj_t pLut,
int  nLevMax,
int  nFanMax 
)

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

Synopsis [Marks the fanouts of the node with the current trav ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 73 of file abcMerge.c.

74 {
75  Abc_Obj_t * pNext;
76  int i;
77  if ( !Abc_ObjIsNode(pLut) )
78  return;
79  if ( Abc_NodeIsTravIdCurrent( pLut ) )
80  return;
82  if ( Abc_ObjLevel(pLut) > nLevMax )
83  return;
84  if ( Abc_ObjFanoutNum(pLut) > nFanMax )
85  return;
86  Abc_ObjForEachFanout( pLut, pNext, i )
87  Abc_NtkMarkFanouts_rec( pNext, nLevMax, nFanMax );
88 }
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
static int Abc_ObjLevel(Abc_Obj_t *pObj)
Definition: abc.h:330
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
void Abc_NtkMarkFanouts_rec(Abc_Obj_t *pLut, int nLevMax, int nFanMax)
Definition: abcMerge.c:73
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409