1 /**CFile****************************************************************
2
3 FileName [giaMuxes.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Multiplexer profiling 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: giaMuxes.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22 #include "misc/util/utilNam.h"
23 #include "misc/vec/vecWec.h"
24 #include "misc/vec/vecHsh.h"
25
26 ABC_NAMESPACE_IMPL_START
27
28
29 ////////////////////////////////////////////////////////////////////////
30 /// DECLARATIONS ///
31 ////////////////////////////////////////////////////////////////////////
32
33 ////////////////////////////////////////////////////////////////////////
34 /// FUNCTION DEFINITIONS ///
35 ////////////////////////////////////////////////////////////////////////
36
37 /**Function*************************************************************
38
39 Synopsis [Counts XORs and MUXes.]
40
41 Description []
42
43 SideEffects []
44
45 SeeAlso []
46
47 ***********************************************************************/
Gia_ManCountMuxXor(Gia_Man_t * p,int * pnMuxes,int * pnXors)48 void Gia_ManCountMuxXor( Gia_Man_t * p, int * pnMuxes, int * pnXors )
49 {
50 Gia_Obj_t * pObj, * pFan0, * pFan1; int i;
51 *pnMuxes = *pnXors = 0;
52 Gia_ManForEachAnd( p, pObj, i )
53 {
54 if ( !Gia_ObjIsMuxType(pObj) )
55 continue;
56 if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
57 (*pnXors)++;
58 else
59 (*pnMuxes)++;
60 }
61 }
Gia_ManPrintMuxStats(Gia_Man_t * p)62 void Gia_ManPrintMuxStats( Gia_Man_t * p )
63 {
64 int nAnds, nMuxes, nXors, nTotal;
65 if ( p->pMuxes )
66 {
67 nAnds = Gia_ManAndNotBufNum(p)-Gia_ManXorNum(p)-Gia_ManMuxNum(p);
68 nXors = Gia_ManXorNum(p);
69 nMuxes = Gia_ManMuxNum(p);
70 nTotal = nAnds + 3*nXors + 3*nMuxes;
71 }
72 else
73 {
74 Gia_ManCountMuxXor( p, &nMuxes, &nXors );
75 nAnds = Gia_ManAndNotBufNum(p) - 3*nMuxes - 3*nXors;
76 nTotal = Gia_ManAndNotBufNum(p);
77 }
78 Abc_Print( 1, "stats: " );
79 Abc_Print( 1, "xor =%8d %6.2f %% ", nXors, 300.0*nXors/nTotal );
80 Abc_Print( 1, "mux =%8d %6.2f %% ", nMuxes, 300.0*nMuxes/nTotal );
81 Abc_Print( 1, "and =%8d %6.2f %% ", nAnds, 100.0*nAnds/nTotal );
82 Abc_Print( 1, "obj =%8d ", Gia_ManAndNotBufNum(p) );
83 fflush( stdout );
84 }
85
86 /**Function*************************************************************
87
88 Synopsis [Derives GIA with MUXes.]
89
90 Description [Create MUX if the sum of fanin references does not exceed limit.]
91
92 SideEffects []
93
94 SeeAlso []
95
96 ***********************************************************************/
Gia_ManDupMuxes(Gia_Man_t * p,int Limit)97 Gia_Man_t * Gia_ManDupMuxes( Gia_Man_t * p, int Limit )
98 {
99 Gia_Man_t * pNew, * pTemp;
100 Gia_Obj_t * pObj, * pFan0, * pFan1, * pFanC, * pSiblNew, * pObjNew;
101 int i;
102 assert( p->pMuxes == NULL );
103 assert( Limit >= 0 ); // allows to create AIG with XORs without MUXes
104 ABC_FREE( p->pRefs );
105 Gia_ManCreateRefs( p );
106 // start the new manager
107 pNew = Gia_ManStart( Gia_ManObjNum(p) );
108 pNew->pName = Abc_UtilStrsav( p->pName );
109 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
110 pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
111 if ( Gia_ManHasChoices(p) )
112 pNew->pSibls = ABC_CALLOC( int, pNew->nObjsAlloc );
113 Gia_ManConst0(p)->Value = 0;
114 Gia_ManHashStart( pNew );
115 Gia_ManForEachObj1( p, pObj, i )
116 {
117 if ( Gia_ObjIsCi(pObj) )
118 pObj->Value = Gia_ManAppendCi( pNew );
119 else if ( Gia_ObjIsCo(pObj) )
120 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
121 else if ( Gia_ObjIsBuf(pObj) )
122 pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
123 else if ( !Gia_ObjIsMuxType(pObj) || Gia_ObjSibl(p, Gia_ObjFaninId0(pObj, i)) || Gia_ObjSibl(p, Gia_ObjFaninId1(pObj, i)) )
124 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
125 else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
126 pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)) );
127 else if ( Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) + Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) > Limit )
128 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
129 else
130 {
131 pFanC = Gia_ObjRecognizeMux( pObj, &pFan1, &pFan0 );
132 pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFanC)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)) );
133 }
134 if ( !Gia_ObjSibl(p, i) )
135 continue;
136 pObjNew = Gia_ManObj( pNew, Abc_Lit2Var(pObj->Value) );
137 pSiblNew = Gia_ManObj( pNew, Abc_Lit2Var(Gia_ObjSiblObj(p, i)->Value) );
138 if ( Gia_ObjIsAnd(pObjNew) && Gia_ObjIsAnd(pSiblNew) && Gia_ObjId(pNew, pObjNew) > Gia_ObjId(pNew, pSiblNew) )
139 pNew->pSibls[Gia_ObjId(pNew, pObjNew)] = Gia_ObjId(pNew, pSiblNew);
140 }
141 Gia_ManHashStop( pNew );
142 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
143 // perform cleanup
144 pNew = Gia_ManCleanup( pTemp = pNew );
145 Gia_ManStop( pTemp );
146 return pNew;
147 }
148
149 /**Function*************************************************************
150
151 Synopsis [Derives GIA without MUXes.]
152
153 Description []
154
155 SideEffects []
156
157 SeeAlso []
158
159 ***********************************************************************/
Gia_ManDupNoMuxes(Gia_Man_t * p,int fSkipBufs)160 Gia_Man_t * Gia_ManDupNoMuxes( Gia_Man_t * p, int fSkipBufs )
161 {
162 Gia_Man_t * pNew, * pTemp;
163 Gia_Obj_t * pObj;
164 int i;
165 assert( p->pMuxes != NULL || Gia_ManXorNum(p) );
166 // start the new manager
167 pNew = Gia_ManStart( 5000 );
168 pNew->pName = Abc_UtilStrsav( p->pName );
169 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
170 Gia_ManConst0(p)->Value = 0;
171 Gia_ManHashStart( pNew );
172 Gia_ManForEachObj1( p, pObj, i )
173 {
174 if ( Gia_ObjIsCi(pObj) )
175 pObj->Value = Gia_ManAppendCi( pNew );
176 else if ( Gia_ObjIsCo(pObj) )
177 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
178 else if ( Gia_ObjIsBuf(pObj) )
179 pObj->Value = fSkipBufs ? Gia_ObjFanin0Copy(pObj) : Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
180 else if ( Gia_ObjIsMuxId(p, i) )
181 pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
182 else if ( Gia_ObjIsXor(pObj) )
183 pObj->Value = Gia_ManHashXor( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
184 else
185 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
186 }
187 Gia_ManHashStop( pNew );
188 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
189 // perform cleanup
190 pNew = Gia_ManCleanup( pTemp = pNew );
191 Gia_ManStop( pTemp );
192 return pNew;
193 }
194
195 /**Function*************************************************************
196
197 Synopsis [Test these procedures.]
198
199 Description []
200
201 SideEffects []
202
203 SeeAlso []
204
205 ***********************************************************************/
Gia_ManDupMuxesTest(Gia_Man_t * p)206 Gia_Man_t * Gia_ManDupMuxesTest( Gia_Man_t * p )
207 {
208 Gia_Man_t * pNew, * pNew2;
209 pNew = Gia_ManDupMuxes( p, 2 );
210 pNew2 = Gia_ManDupNoMuxes( pNew, 0 );
211 Gia_ManPrintStats( p, NULL );
212 Gia_ManPrintStats( pNew, NULL );
213 Gia_ManPrintStats( pNew2, NULL );
214 Gia_ManStop( pNew );
215 // Gia_ManStop( pNew2 );
216 return pNew2;
217 }
218
219
220 /**Function*************************************************************
221
222 Synopsis [Test these procedures.]
223
224 Description []
225
226 SideEffects []
227
228 SeeAlso []
229
230 ***********************************************************************/
Gia_ManMuxRestructure(Gia_Man_t * p)231 Gia_Man_t * Gia_ManMuxRestructure( Gia_Man_t * p )
232 {
233 Gia_Man_t * pNew, * pTemp;
234 Gia_Obj_t * pObj;
235 int i, nNodes = 0;
236 Vec_Bit_t * vUsed = Vec_BitStart( Gia_ManObjNum(p) );
237 assert( !Gia_ManHasChoices(p) );
238 assert( !Gia_ManHasMapping(p) );
239 assert( p->pMuxes != NULL );
240 ABC_FREE( p->pRefs );
241 Gia_ManCreateRefs( p );
242 // start the new manager
243 pNew = Gia_ManStart( Gia_ManObjNum(p) );
244 pNew->pName = Abc_UtilStrsav( p->pName );
245 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
246 pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
247 Gia_ManConst0(p)->Value = 0;
248 Gia_ManHashStart( pNew );
249 Gia_ManForEachObj1( p, pObj, i )
250 {
251 if ( Gia_ObjIsCi(pObj) )
252 pObj->Value = Gia_ManAppendCi( pNew );
253 else if ( Gia_ObjIsCo(pObj) )
254 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
255 else if ( Gia_ObjIsBuf(pObj) )
256 pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
257 else if ( Gia_ObjIsMuxId(p, i) &&
258 Gia_ObjIsMuxId(p, Gia_ObjFaninId0(pObj, i)) && !Vec_BitEntry(vUsed, Gia_ObjFaninId0(pObj, i)) &&
259 Gia_ObjIsMuxId(p, Gia_ObjFaninId1(pObj, i)) && !Vec_BitEntry(vUsed, Gia_ObjFaninId1(pObj, i)) &&
260 Gia_ObjFaninId2(p, Gia_ObjFaninId0(pObj, i)) == Gia_ObjFaninId2(p, Gia_ObjFaninId1(pObj, i)) )
261 {
262 Gia_Obj_t * pFan1 = Gia_ObjFanin1(pObj);
263 int Value0 = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin2Copy(p, pFan1), Gia_ObjFanin0Copy(pObj) );
264 int Value1 = Gia_ManHashMux( pNew, Value0, Gia_ObjFanin1Copy(pFan1), Gia_ObjFanin0Copy(pFan1) );
265 pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Value1, Value0 );
266 Vec_BitWriteEntry( vUsed, Gia_ObjFaninId0(pObj, i), 1 );
267 Vec_BitWriteEntry( vUsed, Gia_ObjFaninId1(pObj, i), 1 );
268 Vec_BitWriteEntry( vUsed, i, 1 );
269 nNodes++;
270 }
271 else if ( Gia_ObjIsMuxId(p, i) )
272 pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
273 else if ( Gia_ObjIsXor(pObj) )
274 pObj->Value = Gia_ManHashXor( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
275 else
276 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
277 }
278 Vec_BitFree( vUsed );
279 Gia_ManHashStop( pNew );
280 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
281 // perform cleanup
282 pNew = Gia_ManCleanup( pTemp = pNew );
283 Gia_ManStop( pTemp );
284 return pNew;
285 }
Gia_ManDupMuxRestructure(Gia_Man_t * p)286 Gia_Man_t * Gia_ManDupMuxRestructure( Gia_Man_t * p )
287 {
288 Gia_Man_t * pTemp, * pNew = Gia_ManDupMuxes( p, 2 );
289 pNew = Gia_ManMuxRestructure( pTemp = pNew ); Gia_ManStop( pTemp );
290 pNew = Gia_ManDupNoMuxes( pTemp = pNew, 0 ); Gia_ManStop( pTemp );
291 return pNew;
292 }
293
294 /**Function*************************************************************
295
296 Synopsis [Returns the size of MUX structure.]
297
298 Description []
299
300 SideEffects []
301
302 SeeAlso []
303
304 ***********************************************************************/
Gia_MuxRef_rec(Gia_Man_t * p,int iObj)305 int Gia_MuxRef_rec( Gia_Man_t * p, int iObj )
306 {
307 Gia_Obj_t * pObj;
308 if ( !Gia_ObjIsMuxId(p, iObj) )
309 return 0;
310 pObj = Gia_ManObj( p, iObj );
311 if ( Gia_ObjRefInc(p, pObj) )
312 return 0;
313 return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) +
314 Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) +
315 Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
316 }
Gia_MuxRef(Gia_Man_t * p,int iObj)317 int Gia_MuxRef( Gia_Man_t * p, int iObj )
318 {
319 Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
320 assert( Gia_ObjIsMuxId(p, iObj) );
321 return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) +
322 Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) +
323 Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
324 }
Gia_MuxDeref_rec(Gia_Man_t * p,int iObj)325 int Gia_MuxDeref_rec( Gia_Man_t * p, int iObj )
326 {
327 Gia_Obj_t * pObj;
328 if ( !Gia_ObjIsMuxId(p, iObj) )
329 return 0;
330 pObj = Gia_ManObj( p, iObj );
331 if ( Gia_ObjRefDec(p, pObj) )
332 return 0;
333 return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) +
334 Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) +
335 Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
336 }
Gia_MuxDeref(Gia_Man_t * p,int iObj)337 int Gia_MuxDeref( Gia_Man_t * p, int iObj )
338 {
339 Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
340 assert( Gia_ObjIsMuxId(p, iObj) );
341 return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) +
342 Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) +
343 Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
344 }
Gia_MuxMffcSize(Gia_Man_t * p,int iObj)345 int Gia_MuxMffcSize( Gia_Man_t * p, int iObj )
346 {
347 int Count1, Count2;
348 if ( !Gia_ObjIsMuxId(p, iObj) )
349 return 0;
350 Count1 = Gia_MuxDeref( p, iObj );
351 Count2 = Gia_MuxRef( p, iObj );
352 assert( Count1 == Count2 );
353 return Count1;
354 }
355
356 /**Function*************************************************************
357
358 Synopsis []
359
360 Description []
361
362 SideEffects []
363
364 SeeAlso []
365
366 ***********************************************************************/
Gia_MuxStructPrint_rec(Gia_Man_t * p,int iObj,int fFirst)367 void Gia_MuxStructPrint_rec( Gia_Man_t * p, int iObj, int fFirst )
368 {
369 Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
370 int iCtrl;
371 if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) )
372 {
373 // printf( "%d", iObj );
374 printf( "<%02d>", Gia_ObjLevelId(p, iObj) );
375 return;
376 }
377 iCtrl = Gia_ObjFaninId2p(p, pObj);
378 printf( " [(" );
379 if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 )
380 Gia_MuxStructPrint_rec( p, iCtrl, 0 );
381 else
382 {
383 printf( "%d", iCtrl );
384 printf( "<%d>", Gia_ObjLevelId(p, iCtrl) );
385 }
386 printf( ")" );
387 if ( Gia_ObjFaninC2(p, pObj) )
388 {
389 Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 );
390 printf( "|" );
391 Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 );
392 printf( "]" );
393 }
394 else
395 {
396 Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 );
397 printf( "|" );
398 Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 );
399 printf( "]" );
400 }
401 }
Gia_MuxStructPrint(Gia_Man_t * p,int iObj)402 void Gia_MuxStructPrint( Gia_Man_t * p, int iObj )
403 {
404 int Count1, Count2;
405 assert( Gia_ObjIsMuxId(p, iObj) );
406 Count1 = Gia_MuxDeref( p, iObj );
407 Gia_MuxStructPrint_rec( p, iObj, 1 );
408 Count2 = Gia_MuxRef( p, iObj );
409 assert( Count1 == Count2 );
410 printf( "\n" );
411 }
412
413 /**Function*************************************************************
414
415 Synopsis []
416
417 Description []
418
419 SideEffects []
420
421 SeeAlso []
422
423 ***********************************************************************/
Gia_MuxStructDump_rec(Gia_Man_t * p,int iObj,int fFirst,Vec_Str_t * vStr,int nDigitsId)424 void Gia_MuxStructDump_rec( Gia_Man_t * p, int iObj, int fFirst, Vec_Str_t * vStr, int nDigitsId )
425 {
426 Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
427 int iCtrl;
428 if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) )
429 return;
430 iCtrl = Gia_ObjFaninId2p(p, pObj);
431 Vec_StrPush( vStr, '[' );
432 Vec_StrPush( vStr, '(' );
433 if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 )
434 Gia_MuxStructDump_rec( p, iCtrl, 0, vStr, nDigitsId );
435 else
436 Vec_StrPrintNumStar( vStr, iCtrl, nDigitsId );
437 Vec_StrPush( vStr, ')' );
438 if ( Gia_ObjFaninC2(p, pObj) )
439 {
440 Gia_MuxStructDump_rec( p, Gia_ObjFaninId0p(p, pObj), 0, vStr, nDigitsId );
441 Vec_StrPush( vStr, '|' );
442 Gia_MuxStructDump_rec( p, Gia_ObjFaninId1p(p, pObj), 0, vStr, nDigitsId );
443 Vec_StrPush( vStr, ']' );
444 }
445 else
446 {
447 Gia_MuxStructDump_rec( p, Gia_ObjFaninId1p(p, pObj), 0, vStr, nDigitsId );
448 Vec_StrPush( vStr, '|' );
449 Gia_MuxStructDump_rec( p, Gia_ObjFaninId0p(p, pObj), 0, vStr, nDigitsId );
450 Vec_StrPush( vStr, ']' );
451 }
452 }
Gia_MuxStructDump(Gia_Man_t * p,int iObj,Vec_Str_t * vStr,int nDigitsNum,int nDigitsId)453 int Gia_MuxStructDump( Gia_Man_t * p, int iObj, Vec_Str_t * vStr, int nDigitsNum, int nDigitsId )
454 {
455 int Count1, Count2;
456 assert( Gia_ObjIsMuxId(p, iObj) );
457 Count1 = Gia_MuxDeref( p, iObj );
458 Vec_StrClear( vStr );
459 Vec_StrPrintNumStar( vStr, Count1, nDigitsNum );
460 Gia_MuxStructDump_rec( p, iObj, 1, vStr, nDigitsId );
461 Vec_StrPush( vStr, '\0' );
462 Count2 = Gia_MuxRef( p, iObj );
463 assert( Count1 == Count2 );
464 return Count1;
465 }
466
467 /**Function*************************************************************
468
469 Synopsis []
470
471 Description []
472
473 SideEffects []
474
475 SeeAlso []
476
477 ***********************************************************************/
Gia_ManMuxCompare(char ** pp1,char ** pp2)478 int Gia_ManMuxCompare( char ** pp1, char ** pp2 )
479 {
480 int Diff = strcmp( *pp1, *pp2 );
481 if ( Diff < 0 )
482 return 1;
483 if ( Diff > 0)
484 return -1;
485 return 0;
486 }
Gia_ManMuxCountOne(char * p)487 int Gia_ManMuxCountOne( char * p )
488 {
489 int Count = 0;
490 for ( ; *p; p++ )
491 Count += (*p == '[');
492 return Count;
493 }
494
495 typedef struct Mux_Man_t_ Mux_Man_t;
496 struct Mux_Man_t_
497 {
498 Gia_Man_t * pGia; // manager
499 Abc_Nam_t * pNames; // hashing name into ID
500 Vec_Wec_t * vTops; // top nodes for each struct
501 };
502
503 /**Function*************************************************************
504
505 Synopsis []
506
507 Description []
508
509 SideEffects []
510
511 SeeAlso []
512
513 ***********************************************************************/
Mux_ManAlloc(Gia_Man_t * pGia)514 Mux_Man_t * Mux_ManAlloc( Gia_Man_t * pGia )
515 {
516 Mux_Man_t * p;
517 p = ABC_CALLOC( Mux_Man_t, 1 );
518 p->pGia = pGia;
519 p->pNames = Abc_NamStart( 10000, 50 );
520 p->vTops = Vec_WecAlloc( 1000 );
521 Vec_WecPushLevel( p->vTops );
522 return p;
523 }
Mux_ManFree(Mux_Man_t * p)524 void Mux_ManFree( Mux_Man_t * p )
525 {
526 Abc_NamStop( p->pNames );
527 Vec_WecFree( p->vTops );
528 ABC_FREE( p );
529 }
530
531 /**Function*************************************************************
532
533 Synopsis []
534
535 Description []
536
537 SideEffects []
538
539 SeeAlso []
540
541 ***********************************************************************/
Gia_ManMuxProfile(Mux_Man_t * p,int fWidth)542 int Gia_ManMuxProfile( Mux_Man_t * p, int fWidth )
543 {
544 int i, Entry, Counter, Total;
545 Vec_Int_t * vVec, * vCounts;
546 vCounts = Vec_IntStart( 1000 );
547 if ( fWidth )
548 {
549 Vec_WecForEachLevelStart( p->vTops, vVec, i, 1 )
550 Vec_IntAddToEntry( vCounts, Abc_MinInt(Vec_IntSize(vVec), 999), 1 );
551 }
552 else
553 {
554 for ( i = 1; i < Vec_WecSize(p->vTops); i++ )
555 Vec_IntAddToEntry( vCounts, Abc_MinInt(atoi(Abc_NamStr(p->pNames, i)), 999), 1 );
556 }
557 Total = Vec_IntCountPositive(vCounts);
558 if ( Total == 0 )
559 return 0;
560 printf( "The distribution of MUX tree %s:\n", fWidth ? "widths" : "sizes" );
561 Counter = 0;
562 Vec_IntForEachEntry( vCounts, Entry, i )
563 {
564 if ( !Entry ) continue;
565 if ( ++Counter == 12 )
566 printf( "\n" ), Counter = 0;
567 printf( " %d=%d", i, Entry );
568 }
569 printf( "\nSummary: " );
570 printf( "Max = %d ", Vec_IntFindMax(vCounts) );
571 printf( "Ave = %.2f", 1.0*Vec_IntSum(vCounts)/Total );
572 printf( "\n" );
573 Vec_IntFree( vCounts );
574 return 1;
575 }
576
577 /**Function*************************************************************
578
579 Synopsis []
580
581 Description []
582
583 SideEffects []
584
585 SeeAlso []
586
587 ***********************************************************************/
Gia_ManMuxProfiling(Gia_Man_t * p)588 void Gia_ManMuxProfiling( Gia_Man_t * p )
589 {
590 Mux_Man_t * pMan;
591 Gia_Man_t * pNew;
592 Gia_Obj_t * pObj;
593 Vec_Str_t * vStr;
594 Vec_Int_t * vFans, * vVec;
595 int i, Counter, fFound, iStructId, nDigitsId;
596 abctime clk = Abc_Clock();
597
598 pNew = Gia_ManDupMuxes( p, 2 );
599 nDigitsId = Abc_Base10Log( Gia_ManObjNum(pNew) );
600
601 pMan = Mux_ManAlloc( pNew );
602
603 Gia_ManLevelNum( pNew );
604 Gia_ManCreateRefs( pNew );
605 Gia_ManForEachCo( pNew, pObj, i )
606 Gia_ObjRefFanin0Inc( pNew, pObj );
607
608 vStr = Vec_StrAlloc( 1000 );
609 vFans = Gia_ManFirstFanouts( pNew );
610 Gia_ManForEachMux( pNew, pObj, i )
611 {
612 // skip MUXes in the middle of the tree (which have only one MUX fanout)
613 if ( Gia_ObjRefNumId(pNew, i) == 1 && Gia_ObjIsMuxId(pNew, Vec_IntEntry(vFans, i)) )
614 continue;
615 // this node is the root of the MUX structure - create hash key
616 Counter = Gia_MuxStructDump( pNew, i, vStr, 3, nDigitsId );
617 if ( Counter == 1 )
618 continue;
619 iStructId = Abc_NamStrFindOrAdd( pMan->pNames, Vec_StrArray(vStr), &fFound );
620 if ( !fFound )
621 Vec_WecPushLevel( pMan->vTops );
622 assert( Abc_NamObjNumMax(pMan->pNames) == Vec_WecSize(pMan->vTops) );
623 Vec_IntPush( Vec_WecEntry(pMan->vTops, iStructId), i );
624 }
625 Vec_StrFree( vStr );
626 Vec_IntFree( vFans );
627
628 printf( "MUX structure profile for AIG \"%s\":\n", p->pName );
629 printf( "Total MUXes = %d. Total trees = %d. Unique trees = %d. Memory = %.2f MB ",
630 Gia_ManMuxNum(pNew), Vec_WecSizeSize(pMan->vTops), Vec_WecSize(pMan->vTops)-1,
631 1.0*Abc_NamMemUsed(pMan->pNames)/(1<<20) );
632 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
633
634 if ( Gia_ManMuxProfile(pMan, 0) )
635 {
636 Gia_ManMuxProfile( pMan, 1 );
637
638 // short the first ones
639 printf( "The first %d structures: \n", 10 );
640 Vec_WecForEachLevelStartStop( pMan->vTops, vVec, i, 1, Abc_MinInt(Vec_WecSize(pMan->vTops), 10) )
641 {
642 char * pTemp = Abc_NamStr(pMan->pNames, i);
643 printf( "%5d : ", i );
644 printf( "Occur = %4d ", Vec_IntSize(vVec) );
645 printf( "Size = %4d ", atoi(pTemp) );
646 printf( "%s\n", pTemp );
647 }
648
649 // print trees for the first one
650 Counter = 0;
651 Vec_WecForEachLevelStart( pMan->vTops, vVec, i, 1 )
652 {
653 char * pTemp = Abc_NamStr(pMan->pNames, i);
654 if ( Vec_IntSize(vVec) > 5 && atoi(pTemp) > 5 )
655 {
656 int k, Entry;
657 printf( "For example, structure %d has %d MUXes and bit-width %d:\n", i, atoi(pTemp), Vec_IntSize(vVec) );
658 Vec_IntForEachEntry( vVec, Entry, k )
659 Gia_MuxStructPrint( pNew, Entry );
660 if ( ++Counter == 5 )
661 break;
662 }
663 }
664 }
665
666 Mux_ManFree( pMan );
667 Gia_ManStop( pNew );
668 }
669
670
671 /**Function*************************************************************
672
673 Synopsis [Compute one-level TFI/TFO structural signatures.]
674
675 Description []
676
677 SideEffects []
678
679 SeeAlso []
680
681 ***********************************************************************/
682
683 // these are object/fanin/fanout attributes
684 // http://stackoverflow.com/questions/9907160/how-to-convert-enum-names-to-string-in-c
685 #define GIA_FOREACH_ITEM(ITEM) \
686 ITEM(C0) \
687 ITEM(PO) \
688 ITEM(PI) \
689 ITEM(FF) \
690 ITEM(XOR) \
691 ITEM(MUX) \
692 ITEM(AND) \
693 ITEM(iC0) \
694 ITEM(iC1) \
695 ITEM(iPI) \
696 ITEM(iFF) \
697 ITEM(iXOR) \
698 ITEM(iMUX) \
699 ITEM(iAND) \
700 ITEM(iANDn) \
701 ITEM(iANDp) \
702 ITEM(oPO) \
703 ITEM(oFF) \
704 ITEM(oXOR) \
705 ITEM(oMUXc) \
706 ITEM(oMUXd) \
707 ITEM(oAND) \
708 ITEM(oANDn) \
709 ITEM(oANDp) \
710 ITEM(GIA_END)
711
712 #define GENERATE_ENUM(ENUM) ENUM,
713 typedef enum { GIA_FOREACH_ITEM(GENERATE_ENUM) } Gia_ObjType_t;
714
715 #define GENERATE_STRING(STRING) #STRING,
716 static const char * GIA_TYPE_STRINGS[] = { GIA_FOREACH_ITEM(GENERATE_STRING) };
717
Gia_ManProfileStructuresTest(Gia_Man_t * p)718 void Gia_ManProfileStructuresTest( Gia_Man_t * p )
719 {
720 int i;
721 for ( i = 0; i < GIA_END; i++ )
722 printf( "%d = %s\n", i, GIA_TYPE_STRINGS[i] );
723 }
724
725
726
727 // find object code
Gia_ManEncodeObj(Gia_Man_t * p,int i)728 int Gia_ManEncodeObj( Gia_Man_t * p, int i )
729 {
730 Gia_Obj_t * pObj = Gia_ManObj( p, i );
731 assert( !Gia_ObjIsRi(p, pObj) );
732 if ( Gia_ObjIsConst0(pObj) )
733 return C0;
734 if ( Gia_ObjIsPo(p, pObj) )
735 return PO;
736 if ( Gia_ObjIsPi(p, pObj) )
737 return PI;
738 if ( Gia_ObjIsCi(pObj) )
739 return FF;
740 if ( Gia_ObjIsXor(pObj) )
741 return XOR;
742 if ( Gia_ObjIsMux(p, pObj) )
743 return MUX;
744 assert( Gia_ObjIsAnd(pObj) );
745 return AND;
746 }
747 // find fanin code
Gia_ManEncodeFanin(Gia_Man_t * p,int iLit)748 int Gia_ManEncodeFanin( Gia_Man_t * p, int iLit )
749 {
750 Gia_Obj_t * pObj = Gia_ManObj( p, Abc_Lit2Var(iLit) );
751 if ( Gia_ObjIsConst0(pObj) )
752 return iC0;
753 if ( Gia_ObjIsPi(p, pObj) )
754 return iPI;
755 if ( Gia_ObjIsCi(pObj) )
756 return iFF;
757 if ( Gia_ObjIsXor(pObj) )
758 return iXOR;
759 if ( Gia_ObjIsMux(p, pObj) )
760 return iMUX;
761 assert( Gia_ObjIsAnd(pObj) );
762 return iAND;
763 // if ( Abc_LitIsCompl(iLit) )
764 // return iANDn;
765 // else
766 // return iANDp;
767 }
768 // find fanout code
Gia_ManEncodeFanout(Gia_Man_t * p,Gia_Obj_t * pObj,int i)769 Gia_ObjType_t Gia_ManEncodeFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i )
770 {
771 // int iLit;
772 if ( Gia_ObjIsPo(p, pObj) )
773 return oPO;
774 if ( Gia_ObjIsCo(pObj) )
775 return oFF;
776 if ( Gia_ObjIsXor(pObj) )
777 return oXOR;
778 if ( Gia_ObjIsMux(p, pObj) )
779 return i == 2 ? oMUXc : oMUXd;
780 assert( Gia_ObjIsAnd(pObj) );
781 return oAND;
782 // iLit = i ? Gia_ObjFaninLit1p(p, pObj) : Gia_ObjFaninLit0p(p, pObj);
783 // if ( Abc_LitIsCompl(iLit) )
784 // return oANDn;
785 // else
786 // return oANDp;
787 }
788
Gia_ManProfileCollect(Gia_Man_t * p,int i,Vec_Int_t * vCode,Vec_Int_t * vCodeOffsets,Vec_Int_t * vArray)789 void Gia_ManProfileCollect( Gia_Man_t * p, int i, Vec_Int_t * vCode, Vec_Int_t * vCodeOffsets, Vec_Int_t * vArray )
790 {
791 int k;
792 Vec_IntClear( vArray );
793 for ( k = Vec_IntEntry(vCodeOffsets, i); k < Vec_IntEntry(vCodeOffsets, i+1); k++ )
794 Vec_IntPush( vArray, Vec_IntEntry(vCode, k) );
795 }
796
Gia_ManProfilePrintOne(Gia_Man_t * p,int i,Vec_Int_t * vArray)797 void Gia_ManProfilePrintOne( Gia_Man_t * p, int i, Vec_Int_t * vArray )
798 {
799 Gia_Obj_t * pObj = Gia_ManObj( p, i );
800 int k, nFanins, nFanouts;
801 if ( Gia_ObjIsRi(p, pObj) )
802 return;
803 nFanins = Gia_ObjIsRo(p, pObj) ? 1 : Gia_ObjFaninNum(p, pObj);
804 nFanouts = Gia_ObjFanoutNum(p, pObj);
805
806 printf( "%6d : ", i );
807 for ( k = 0; k < nFanins; k++ )
808 printf( " %5s", GIA_TYPE_STRINGS[Vec_IntEntry(vArray, k + 1)] );
809 for ( ; k < 3; k++ )
810 printf( " %5s", "" );
811 printf( " ->" );
812 printf( " %5s", GIA_TYPE_STRINGS[Vec_IntEntry(vArray, 0)] );
813 printf( " ->" );
814 if ( nFanouts > 0 )
815 {
816 int Count = 1, Prev = Vec_IntEntry(vArray, 1 + nFanins);
817 for ( k = 1; k < nFanouts; k++ )
818 {
819 if ( Prev != Vec_IntEntry(vArray, k + 1 + nFanins) )
820 {
821 printf( " %d x %s", Count, GIA_TYPE_STRINGS[Prev] );
822 Prev = Vec_IntEntry(vArray, k + 1 + nFanins);
823 Count = 0;
824 }
825 Count++;
826 }
827 printf( " %d x %s", Count, GIA_TYPE_STRINGS[Prev] );
828 }
829 printf( "\n" );
830 }
831
Gia_ManProfileHash(Gia_Man_t * p,Vec_Int_t * vCode,Vec_Int_t * vCodeOffsets)832 Vec_Int_t * Gia_ManProfileHash( Gia_Man_t * p, Vec_Int_t * vCode, Vec_Int_t * vCodeOffsets )
833 {
834 Hsh_VecMan_t * pHash;
835 Vec_Int_t * vRes, * vArray;
836 Gia_Obj_t * pObj;
837 int i;
838 vRes = Vec_IntAlloc( Gia_ManObjNum(p) );
839 pHash = Hsh_VecManStart( Gia_ManObjNum(p) );
840 // add empty entry
841 vArray = Vec_IntAlloc( 100 );
842 Hsh_VecManAdd( pHash, vArray );
843 // iterate through the entries
844 Gia_ManForEachObj( p, pObj, i )
845 {
846 Gia_ManProfileCollect( p, i, vCode, vCodeOffsets, vArray );
847 Vec_IntPush( vRes, Hsh_VecManAdd( pHash, vArray ) );
848 }
849 Hsh_VecManStop( pHash );
850 Vec_IntFree( vArray );
851 assert( Vec_IntSize(vRes) == Gia_ManObjNum(p) );
852 return vRes;
853 }
854
855
Gia_ManProfileStructuresInt(Gia_Man_t * p,int nLimit,int fVerbose)856 void Gia_ManProfileStructuresInt( Gia_Man_t * p, int nLimit, int fVerbose )
857 {
858 Vec_Int_t * vRes, * vCount, * vFirst;
859 Vec_Int_t * vCode, * vCodeOffsets, * vArray;
860 Gia_Obj_t * pObj, * pFanout;
861 int i, k, nFanins, nFanouts, * pPerm, nClasses;
862 assert( p->pMuxes );
863 Gia_ManStaticFanoutStart( p );
864 // create fanout codes
865 vArray = Vec_IntAlloc( 100 );
866 vCode = Vec_IntAlloc( 5 * Gia_ManObjNum(p) );
867 vCodeOffsets = Vec_IntAlloc( Gia_ManObjNum(p) );
868 Gia_ManForEachObj( p, pObj, i )
869 {
870 Vec_IntPush( vCodeOffsets, Vec_IntSize(vCode) );
871 if ( Gia_ObjIsRi(p, pObj) )
872 continue;
873 nFanins = Gia_ObjFaninNum(p, pObj);
874 nFanouts = Gia_ObjFanoutNum(p, pObj);
875 Vec_IntPush( vCode, Gia_ManEncodeObj(p, i) );
876 if ( nFanins == 3 )
877 {
878 int iLit = Gia_ObjFaninLit2p(p, pObj);
879 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Abc_LitRegular(iLit)) );
880 if ( Abc_LitIsCompl(iLit) )
881 {
882 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)) );
883 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit1p(p, pObj)) );
884 }
885 else
886 {
887 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit1p(p, pObj)) );
888 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)) );
889 }
890 }
891 else if ( nFanins == 2 )
892 {
893 int Code0 = Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj));
894 int Code1 = Gia_ManEncodeFanin(p, Gia_ObjFaninLit1p(p, pObj));
895 Vec_IntPush( vCode, Code0 < Code1 ? Code0 : Code1 );
896 Vec_IntPush( vCode, Code0 < Code1 ? Code1 : Code0 );
897 }
898 else if ( nFanins == 1 )
899 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, pObj)) );
900 else if ( Gia_ObjIsRo(p, pObj) )
901 Vec_IntPush( vCode, Gia_ManEncodeFanin(p, Gia_ObjFaninLit0p(p, Gia_ObjRoToRi(p, pObj))) );
902
903 // add fanouts
904 Vec_IntClear( vArray );
905 Gia_ObjForEachFanoutStatic( p, pObj, pFanout, k )
906 {
907 int Index = Gia_ObjWhatFanin( p, pFanout, pObj );
908 Gia_ObjType_t Type = Gia_ManEncodeFanout( p, pFanout, Index );
909 Vec_IntPush( vArray, Type );
910 }
911 Vec_IntSort( vArray, 0 );
912 Vec_IntAppend( vCode, vArray );
913 }
914 assert( Vec_IntSize(vCodeOffsets) == Gia_ManObjNum(p) );
915 Vec_IntPush( vCodeOffsets, Vec_IntSize(vCode) );
916 // print the results
917 if ( fVerbose )
918 {
919 printf( "Showing TFI/node/TFO structures for all nodes:\n" );
920 Gia_ManForEachObj( p, pObj, i )
921 {
922 Gia_ManProfileCollect( p, i, vCode, vCodeOffsets, vArray );
923 Gia_ManProfilePrintOne( p, i, vArray );
924 }
925 }
926
927 // collect statistics
928 vRes = Gia_ManProfileHash( p, vCode, vCodeOffsets );
929 //Vec_IntPrint( vRes );
930
931 // count how many times each class appears
932 nClasses = Vec_IntFindMax(vRes) + 1;
933 vCount = Vec_IntStart( nClasses );
934 vFirst = Vec_IntStart( nClasses );
935 Gia_ManForEachObj( p, pObj, i )
936 {
937 int Entry = Vec_IntEntry( vRes, i );
938 if ( Gia_ObjIsRi(p, pObj) )
939 continue;
940 if ( Vec_IntEntry(vCount, Entry) == 0 )
941 Vec_IntWriteEntry( vFirst, Entry, i );
942 Vec_IntAddToEntry( vCount, Entry, -1 );
943 }
944 // sort the counts
945 pPerm = Abc_MergeSortCost( Vec_IntArray(vCount), Vec_IntSize(vCount) );
946 printf( "Showing TFI/node/TFO structures that appear more than %d times.\n", nLimit );
947 for ( i = 0; i < nClasses-1; i++ )
948 {
949 if ( nLimit > -Vec_IntEntry(vCount, pPerm[i]) )
950 break;
951 printf( "%6d : ", i );
952 printf( "%6d : ", pPerm[i] );
953 printf( "Weight =%6d ", -Vec_IntEntry(vCount, pPerm[i]) );
954 printf( "First obj =" );
955 // print the object
956 Gia_ManProfileCollect( p, Vec_IntEntry(vFirst, pPerm[i]), vCode, vCodeOffsets, vArray );
957 Gia_ManProfilePrintOne( p, Vec_IntEntry(vFirst, pPerm[i]), vArray );
958 }
959
960 // cleanup
961 ABC_FREE( pPerm );
962 Vec_IntFree( vRes );
963 Vec_IntFree( vCount );
964 Vec_IntFree( vFirst );
965
966 Vec_IntFree( vArray );
967 Vec_IntFree( vCode );
968 Vec_IntFree( vCodeOffsets );
969 Gia_ManStaticFanoutStop( p );
970 }
Gia_ManProfileStructures(Gia_Man_t * p,int nLimit,int fVerbose)971 void Gia_ManProfileStructures( Gia_Man_t * p, int nLimit, int fVerbose )
972 {
973 if ( p->pMuxes )
974 Gia_ManProfileStructuresInt( p, nLimit, fVerbose );
975 else
976 {
977 Gia_Man_t * pNew = Gia_ManDupMuxes( p, 2 );
978 Gia_ManProfileStructuresInt( pNew, nLimit, fVerbose );
979 Gia_ManStop( pNew );
980 }
981 }
982
983 ////////////////////////////////////////////////////////////////////////
984 /// END OF FILE ///
985 ////////////////////////////////////////////////////////////////////////
986
987
988 ABC_NAMESPACE_IMPL_END
989
990