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
25 ABC_NAMESPACE_IMPL_START
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 ***********************************************************************/
Abc_NtkMarkFanins_rec(Abc_Obj_t * pLut,int nLevMin)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;
55 Abc_NodeSetTravIdCurrent( pLut );
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 ***********************************************************************/
Abc_NtkMarkFanouts_rec(Abc_Obj_t * pLut,int nLevMax,int nFanMax)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;
81 Abc_NodeSetTravIdCurrent( pLut );
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 ***********************************************************************/
Abc_NtkCollectCircle(Vec_Ptr_t * vStart,Vec_Ptr_t * vNext,int nFanMax)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 ***********************************************************************/
Abc_NtkCollectNonOverlapCands(Abc_Obj_t * pLut,Vec_Ptr_t * vStart,Vec_Ptr_t * vNext,Vec_Ptr_t * vCands,Nwk_LMPars_t * pPars)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 {
174 Abc_NodeSetTravIdPrevious( pLut );
175 Abc_NtkMarkFanins_rec( pLut, Abc_ObjLevel(pLut) - pPars->nMaxDistance );
176 Abc_NodeSetTravIdPrevious( pLut );
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 ***********************************************************************/
Abc_NtkCountTotalFanins(Abc_Obj_t * pLut,Abc_Obj_t * pCand)212 int Abc_NtkCountTotalFanins( Abc_Obj_t * pLut, Abc_Obj_t * pCand )
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 ***********************************************************************/
Abc_NtkCollectOverlapCands(Abc_Obj_t * pLut,Vec_Ptr_t * vCands,Nwk_LMPars_t * pPars)232 void Abc_NtkCollectOverlapCands( Abc_Obj_t * pLut, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
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 ***********************************************************************/
Abc_NtkLutMerge(Abc_Ntk_t * pNtk,Nwk_LMPars_t * pPars)282 Vec_Int_t * Abc_NtkLutMerge( Abc_Ntk_t * pNtk, Nwk_LMPars_t * pPars )
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 );
339 Nwk_ManGraphReportMemoryUsage( p );
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
357 ABC_NAMESPACE_IMPL_END
358
359