1 /**CFile****************************************************************
2
3 FileName [aigIsoFast.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [AIG package.]
8
9 Synopsis [Graph isomorphism package.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: aigIsoFast.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "saig.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 #define AIG_ISO_NUM 16
31
32 typedef struct Iso_Dat_t_ Iso_Dat_t;
33 struct Iso_Dat_t_
34 {
35 unsigned nFiNeg : 3;
36 unsigned nFoNeg : 2;
37 unsigned nFoPos : 2;
38 unsigned Fi0Lev : 3;
39 unsigned Fi1Lev : 3;
40 unsigned Level : 3;
41 unsigned fVisit : 16;
42 };
43
44 typedef struct Iso_Dat2_t_ Iso_Dat2_t;
45 struct Iso_Dat2_t_
46 {
47 unsigned Data : 16;
48 };
49
50 typedef struct Iso_Sto_t_ Iso_Sto_t;
51 struct Iso_Sto_t_
52 {
53 Aig_Man_t * pAig; // user's AIG manager
54 int nObjs; // number of objects
55 Iso_Dat_t * pData; // data for each object
56 Vec_Int_t * vVisited; // visited nodes
57 Vec_Ptr_t * vRoots; // root nodes
58 Vec_Int_t * vPlaces; // places in the counter lists
59 int * pCounters; // counters
60 };
61
62 ////////////////////////////////////////////////////////////////////////
63 /// FUNCTION DEFINITIONS ///
64 ////////////////////////////////////////////////////////////////////////
65
66 /**Function*************************************************************
67
68 Synopsis []
69
70 Description []
71
72 SideEffects []
73
74 SeeAlso []
75
76 ***********************************************************************/
Iso_StoStart(Aig_Man_t * pAig)77 Iso_Sto_t * Iso_StoStart( Aig_Man_t * pAig )
78 {
79 Iso_Sto_t * p;
80 p = ABC_CALLOC( Iso_Sto_t, 1 );
81 p->pAig = pAig;
82 p->nObjs = Aig_ManObjNumMax( pAig );
83 p->pData = ABC_CALLOC( Iso_Dat_t, p->nObjs );
84 p->vVisited = Vec_IntStart( 1000 );
85 p->vPlaces = Vec_IntStart( 1000 );
86 p->vRoots = Vec_PtrStart( 1000 );
87 p->pCounters = ABC_CALLOC( int, (1 << AIG_ISO_NUM) );
88 return p;
89 }
Iso_StoStop(Iso_Sto_t * p)90 void Iso_StoStop( Iso_Sto_t * p )
91 {
92 Vec_IntFree( p->vPlaces );
93 Vec_IntFree( p->vVisited );
94 Vec_PtrFree( p->vRoots );
95 ABC_FREE( p->pCounters );
96 ABC_FREE( p->pData );
97 ABC_FREE( p );
98 }
99
100 /**Function*************************************************************
101
102 Synopsis [Collect statistics about one node.]
103
104 Description []
105
106 SideEffects []
107
108 SeeAlso []
109
110 ***********************************************************************/
Iso_StoCollectInfo_rec(Aig_Man_t * p,Aig_Obj_t * pObj,int fCompl,Vec_Int_t * vVisited,Iso_Dat_t * pData,Vec_Ptr_t * vRoots)111 void Iso_StoCollectInfo_rec( Aig_Man_t * p, Aig_Obj_t * pObj, int fCompl, Vec_Int_t * vVisited, Iso_Dat_t * pData, Vec_Ptr_t * vRoots )
112 {
113 Iso_Dat_t * pThis = pData + Aig_ObjId(pObj);
114 assert( Aig_ObjIsCi(pObj) || Aig_ObjIsNode(pObj) );
115 if ( pThis->fVisit )
116 {
117 if ( fCompl )
118 pThis->nFoNeg++;
119 else
120 pThis->nFoPos++;
121 return;
122 }
123 assert( *((int *)pThis) == 0 );
124 pThis->fVisit = 1;
125 if ( fCompl )
126 pThis->nFoNeg++;
127 else
128 pThis->nFoPos++;
129 pThis->Level = pObj->Level;
130 pThis->nFiNeg = Aig_ObjFaninC0(pObj) + Aig_ObjFaninC1(pObj);
131 if ( Aig_ObjIsNode(pObj) )
132 {
133 if ( Aig_ObjFaninC0(pObj) < Aig_ObjFaninC1(pObj) || (Aig_ObjFaninC0(pObj) == Aig_ObjFaninC1(pObj) && Aig_ObjFanin0(pObj)->Level < Aig_ObjFanin1(pObj)->Level) )
134 {
135 pThis->Fi0Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
136 pThis->Fi1Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
137 }
138 else
139 {
140 pThis->Fi0Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
141 pThis->Fi1Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
142 }
143 Iso_StoCollectInfo_rec( p, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), vVisited, pData, vRoots );
144 Iso_StoCollectInfo_rec( p, Aig_ObjFanin1(pObj), Aig_ObjFaninC1(pObj), vVisited, pData, vRoots );
145 }
146 else if ( Saig_ObjIsLo(p, pObj) )
147 {
148 pThis->Fi0Lev = 1;
149 pThis->Fi1Lev = 0;
150 Vec_PtrPush( vRoots, Saig_ObjLoToLi(p, pObj) );
151 }
152 else if ( Saig_ObjIsPi(p, pObj) )
153 {
154 pThis->Fi0Lev = 0;
155 pThis->Fi1Lev = 0;
156 }
157 else
158 assert( 0 );
159 assert( pThis->nFoNeg + pThis->nFoPos );
160 Vec_IntPush( vVisited, Aig_ObjId(pObj) );
161 }
162
163 //static abctime time_Trav = 0;
164
165 /**Function*************************************************************
166
167 Synopsis [Collect statistics about one output.]
168
169 Description []
170
171 SideEffects []
172
173 SeeAlso []
174
175 ***********************************************************************/
Iso_StoCollectInfo(Iso_Sto_t * p,Aig_Obj_t * pPo)176 Vec_Int_t * Iso_StoCollectInfo( Iso_Sto_t * p, Aig_Obj_t * pPo )
177 {
178 int fVerboseShow = 0;
179 Vec_Int_t * vInfo;
180 Iso_Dat2_t * pData2 = (Iso_Dat2_t *)p->pData;
181 Aig_Man_t * pAig = p->pAig;
182 Aig_Obj_t * pObj;
183 int i, Value, Entry, * pPerm;
184 // abctime clk = Abc_Clock();
185
186 assert( Aig_ObjIsCo(pPo) );
187
188 // collect initial POs
189 Vec_IntClear( p->vVisited );
190 Vec_PtrClear( p->vRoots );
191 Vec_PtrPush( p->vRoots, pPo );
192
193 // mark internal nodes
194 Vec_PtrForEachEntry( Aig_Obj_t *, p->vRoots, pObj, i )
195 if ( !Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) )
196 Iso_StoCollectInfo_rec( pAig, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), p->vVisited, p->pData, p->vRoots );
197 // time_Trav += Abc_Clock() - clk;
198
199 // count how many times each data entry appears
200 Vec_IntClear( p->vPlaces );
201 Vec_IntForEachEntry( p->vVisited, Entry, i )
202 {
203 Value = pData2[Entry].Data;
204 // assert( Value > 0 );
205 if ( p->pCounters[Value]++ == 0 )
206 Vec_IntPush( p->vPlaces, Value );
207 // pData2[Entry].Data = 0;
208 *((int *)(p->pData + Entry)) = 0;
209 }
210
211 // collect non-trivial counters
212 Vec_IntClear( p->vVisited );
213 Vec_IntForEachEntry( p->vPlaces, Entry, i )
214 {
215 assert( p->pCounters[Entry] );
216 Vec_IntPush( p->vVisited, p->pCounters[Entry] );
217 p->pCounters[Entry] = 0;
218 }
219 // printf( "%d ", Vec_IntSize(p->vVisited) );
220
221 // sort the costs in the increasing order
222 pPerm = Abc_MergeSortCost( Vec_IntArray(p->vVisited), Vec_IntSize(p->vVisited) );
223 assert( Vec_IntEntry(p->vVisited, pPerm[0]) <= Vec_IntEntry(p->vVisited, pPerm[Vec_IntSize(p->vVisited)-1]) );
224
225 // create information
226 vInfo = Vec_IntAlloc( Vec_IntSize(p->vVisited) );
227 for ( i = Vec_IntSize(p->vVisited)-1; i >= 0; i-- )
228 {
229 Entry = Vec_IntEntry( p->vVisited, pPerm[i] );
230 Entry = (Entry << AIG_ISO_NUM) | Vec_IntEntry( p->vPlaces, pPerm[i] );
231 Vec_IntPush( vInfo, Entry );
232 }
233 ABC_FREE( pPerm );
234
235 // show the final result
236 if ( fVerboseShow )
237 Vec_IntForEachEntry( vInfo, Entry, i )
238 {
239 Iso_Dat2_t Data = { Entry & 0xFFFF };
240 Iso_Dat_t * pData = (Iso_Dat_t *)&Data;
241
242 printf( "%6d : ", i );
243 printf( "Freq =%6d ", Entry >> 16 );
244
245 printf( "FiNeg =%3d ", pData->nFiNeg );
246 printf( "FoNeg =%3d ", pData->nFoNeg );
247 printf( "FoPos =%3d ", pData->nFoPos );
248 printf( "Fi0L =%3d ", pData->Fi0Lev );
249 printf( "Fi1L =%3d ", pData->Fi1Lev );
250 printf( "Lev =%3d ", pData->Level );
251 printf( "\n" );
252 }
253 return vInfo;
254 }
255
256 /**Function*************************************************************
257
258 Synopsis [Takes multi-output sequential AIG.]
259
260 Description [Returns candidate equivalence classes of POs.]
261
262 SideEffects []
263
264 SeeAlso []
265
266 ***********************************************************************/
Iso_StoCompareVecInt(Vec_Int_t ** p1,Vec_Int_t ** p2)267 int Iso_StoCompareVecInt( Vec_Int_t ** p1, Vec_Int_t ** p2 )
268 {
269 return Vec_IntCompareVec( *p1, *p2 );
270 }
271
272 /**Function*************************************************************
273
274 Synopsis [Takes multi-output sequential AIG.]
275
276 Description [Returns candidate equivalence classes of POs.]
277
278 SideEffects []
279
280 SeeAlso []
281
282 ***********************************************************************/
Saig_IsoDetectFast(Aig_Man_t * pAig)283 Vec_Vec_t * Saig_IsoDetectFast( Aig_Man_t * pAig )
284 {
285 Iso_Sto_t * pMan;
286 Aig_Obj_t * pObj;
287 Vec_Ptr_t * vClasses, * vInfos;
288 Vec_Int_t * vInfo, * vPrev, * vLevel;
289 int i, Number, nUnique = 0;
290 abctime clk = Abc_Clock();
291
292 // collect infos and remember their number
293 pMan = Iso_StoStart( pAig );
294 vInfos = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
295 Saig_ManForEachPo( pAig, pObj, i )
296 {
297 vInfo = Iso_StoCollectInfo(pMan, pObj);
298 Vec_IntPush( vInfo, i );
299 Vec_PtrPush( vInfos, vInfo );
300 }
301 Iso_StoStop( pMan );
302 Abc_PrintTime( 1, "Info computation time", Abc_Clock() - clk );
303
304 // sort the infos
305 clk = Abc_Clock();
306 Vec_PtrSort( vInfos, (int (*)(void))Iso_StoCompareVecInt );
307
308 // create classes
309 clk = Abc_Clock();
310 vClasses = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
311 // start the first class
312 Vec_PtrPush( vClasses, (vLevel = Vec_IntAlloc(4)) );
313 vPrev = (Vec_Int_t *)Vec_PtrEntry( vInfos, 0 );
314 Vec_IntPush( vLevel, Vec_IntPop(vPrev) );
315 // consider other classes
316 Vec_PtrForEachEntryStart( Vec_Int_t *, vInfos, vInfo, i, 1 )
317 {
318 Number = Vec_IntPop( vInfo );
319 if ( Vec_IntCompareVec(vPrev, vInfo) )
320 Vec_PtrPush( vClasses, Vec_IntAlloc(4) );
321 vLevel = (Vec_Int_t *)Vec_PtrEntryLast( vClasses );
322 Vec_IntPush( vLevel, Number );
323 vPrev = vInfo;
324 }
325 Vec_VecFree( (Vec_Vec_t *)vInfos );
326 Abc_PrintTime( 1, "Sorting time", Abc_Clock() - clk );
327 // Abc_PrintTime( 1, "Traversal time", time_Trav );
328
329 // report the results
330 // Vec_VecPrintInt( (Vec_Vec_t *)vClasses );
331 printf( "Devided %d outputs into %d cand equiv classes.\n", Saig_ManPoNum(pAig), Vec_PtrSize(vClasses) );
332
333 Vec_PtrForEachEntry( Vec_Int_t *, vClasses, vLevel, i )
334 if ( Vec_IntSize(vLevel) > 1 )
335 printf( "%d ", Vec_IntSize(vLevel) );
336 else
337 nUnique++;
338 printf( " Unique = %d\n", nUnique );
339
340 // return (Vec_Vec_t *)vClasses;
341 Vec_VecFree( (Vec_Vec_t *)vClasses );
342 return NULL;
343 }
344
345
346
347 ////////////////////////////////////////////////////////////////////////
348 /// END OF FILE ///
349 ////////////////////////////////////////////////////////////////////////
350
351
352 ABC_NAMESPACE_IMPL_END
353
354