abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fahout_cut.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcMerge.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis [LUT merging algorithm.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 #include "aig/aig/aig.h"
23 #include "aig/nwk/nwkMerge.h"
24 
26 
27 
28 ////////////////////////////////////////////////////////////////////////
29 /// DECLARATIONS ///
30 ////////////////////////////////////////////////////////////////////////
31 
32 ////////////////////////////////////////////////////////////////////////
33 /// FUNCTION DEFINITIONS ///
34 ////////////////////////////////////////////////////////////////////////
35 
36 /**Function*************************************************************
37 
38  Synopsis [Marks the fanins of the node with the current trav ID.]
39 
40  Description []
41 
42  SideEffects []
43 
44  SeeAlso []
45 
46 ***********************************************************************/
47 void Abc_NtkMarkFanins_rec( Abc_Obj_t * pLut, int nLevMin )
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 }
61 
62 /**Function*************************************************************
63 
64  Synopsis [Marks the fanouts of the node with the current trav ID.]
65 
66  Description []
67 
68  SideEffects []
69 
70  SeeAlso []
71 
72 ***********************************************************************/
73 void Abc_NtkMarkFanouts_rec( Abc_Obj_t * pLut, int nLevMax, int nFanMax )
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 }
89 
90 /**Function*************************************************************
91 
92  Synopsis [Collects the circle of nodes around the given set.]
93 
94  Description []
95 
96  SideEffects []
97 
98  SeeAlso []
99 
100 ***********************************************************************/
101 void Abc_NtkCollectCircle( Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, int nFanMax )
102 {
103  Abc_Obj_t * pObj, * pNext;
104  int i, k;
105  Vec_PtrClear( vNext );
106  Vec_PtrForEachEntry( Vec_Int_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 }
130 
131 /**Function*************************************************************
132 
133  Synopsis [Collects the circle of nodes removes from the given one.]
134 
135  Description []
136 
137  SideEffects []
138 
139  SeeAlso []
140 
141 ***********************************************************************/
142 void Abc_NtkCollectNonOverlapCands( Abc_Obj_t * pLut, Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
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( Vec_Int_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( Vec_Int_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 }
199 
200 
201 /**Function*************************************************************
202 
203  Synopsis [Count the total number of fanins.]
204 
205  Description []
206 
207  SideEffects []
208 
209  SeeAlso []
210 
211 ***********************************************************************/
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 }
220 
221 /**Function*************************************************************
222 
223  Synopsis [Collects overlapping candidates.]
224 
225  Description []
226 
227  SideEffects []
228 
229  SeeAlso []
230 
231 ***********************************************************************/
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 }
270 
271 /**Function*************************************************************
272 
273  Synopsis [Performs LUT merging with parameters.]
274 
275  Description []
276 
277  SideEffects []
278 
279  SeeAlso []
280 
281 ***********************************************************************/
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  clock_t clk = 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( Vec_Int_t *, vCands1, pCand, k )
313  Nwk_ManGraphHashEdge( p, Abc_ObjId(pLut), Abc_ObjId(pCand) );
314  Vec_PtrForEachEntry( Vec_Int_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", clock() - clk );
330  }
331  // solve the graph problem
332  clk = 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", 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 }
350 
351 
352 ////////////////////////////////////////////////////////////////////////
353 /// END OF FILE ///
354 ////////////////////////////////////////////////////////////////////////
355 
356 
358 
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
int nMaxFanout
Definition: nwkMerge.h:52
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_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
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
void Nwk_ManGraphFree(Nwk_Grf_t *p)
Definition: nwkMerge.c:70
int nEdges
Definition: nwkMerge.h:90
void Nwk_ManGraphSolve(Nwk_Grf_t *p)
Definition: nwkMerge.c:621
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
int nVertsMax
Definition: nwkMerge.h:85
void Abc_NtkCollectOverlapCands(Abc_Obj_t *pLut, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
Definition: fahout_cut.c:232
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
void Abc_NtkCollectCircle(Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, int nFanMax)
Definition: fahout_cut.c:101
int nVerts
Definition: nwkMerge.h:91
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
void Nwk_ManGraphHashEdge(Nwk_Grf_t *p, int iLut1, int iLut2)
Definition: nwkMerge.c:119
unsigned fMarkC
Definition: abc.h:136
ABC_NAMESPACE_IMPL_START Nwk_Grf_t * Nwk_ManGraphAlloc(int nVertsMax)
DECLARATIONS ///.
Definition: nwkMerge.c:46
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
int Abc_NtkCountTotalFanins(Abc_Obj_t *pLut, Abc_Obj_t *pCand)
Definition: fahout_cut.c:212
int fVeryVerbose
Definition: nwkMerge.h:55
Vec_Int_t * Abc_NtkLutMerge(Abc_Ntk_t *pNtk, Nwk_LMPars_t *pPars)
Definition: fahout_cut.c:282
int fUseTfiTfo
Definition: nwkMerge.h:54
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_Ntk_t * pNtk
Definition: abc.h:130
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
#define ABC_PRT(a, t)
Definition: abc_global.h:220
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
int nMaxLutSize
Definition: nwkMerge.h:48
Vec_Int_t * vPairs
Definition: nwkMerge.h:98
#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
ABC_NAMESPACE_IMPL_START void Abc_NtkMarkFanins_rec(Abc_Obj_t *pLut, int nLevMin)
DECLARATIONS ///.
Definition: fahout_cut.c:47
static void Vec_PtrShrink(Vec_Ptr_t *p, int nSizeNew)
Definition: vecPtr.h:528
int fVerbose
Definition: nwkMerge.h:56
int nMaxLevelDiff
Definition: nwkMerge.h:51
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Abc_NtkCollectNonOverlapCands(Abc_Obj_t *pLut, Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
Definition: fahout_cut.c:142
void Abc_NtkMarkFanouts_rec(Abc_Obj_t *pLut, int nLevMax, int nFanMax)
Definition: fahout_cut.c:73