1 /**CFile****************************************************************
2
3 FileName [giaFanout.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis []
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaFanout.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 // 0: first iFan
31 // 1: prev iFan0
32 // 2: prev iFan1
33 // 3: next iFan0
34 // 4: next iFan1
35
Gia_FanoutCreate(int FanId,int Num)36 static inline int Gia_FanoutCreate( int FanId, int Num ) { assert( Num < 2 ); return (FanId << 1) | Num; }
Gia_FanoutObj(int * pData,int ObjId)37 static inline int * Gia_FanoutObj( int * pData, int ObjId ) { return pData + 5*ObjId; }
Gia_FanoutPrev(int * pData,int iFan)38 static inline int * Gia_FanoutPrev( int * pData, int iFan ) { return pData + 5*(iFan >> 1) + 1 + (iFan & 1); }
Gia_FanoutNext(int * pData,int iFan)39 static inline int * Gia_FanoutNext( int * pData, int iFan ) { return pData + 5*(iFan >> 1) + 3 + (iFan & 1); }
40
41 // these two procedures are only here for the use inside the iterator
Gia_ObjFanout0Int(Gia_Man_t * p,int ObjId)42 static inline int Gia_ObjFanout0Int( Gia_Man_t * p, int ObjId ) { assert(ObjId < p->nFansAlloc); return p->pFanData[5*ObjId]; }
Gia_ObjFanoutNext(Gia_Man_t * p,int iFan)43 static inline int Gia_ObjFanoutNext( Gia_Man_t * p, int iFan ) { assert(iFan/2 < p->nFansAlloc); return p->pFanData[5*(iFan >> 1) + 3 + (iFan & 1)]; }
44
45 // iterator over the fanouts
46 #define Gia_ObjForEachFanout( p, pObj, pFanout, iFan, i ) \
47 for ( assert(p->pFanData), i = 0; (i < (int)(pObj)->nRefs) && \
48 (((iFan) = i? Gia_ObjFanoutNext(p, iFan) : Gia_ObjFanout0Int(p, Gia_ObjId(p, pObj))), 1) && \
49 (((pFanout) = Gia_ManObj(p, iFan>>1)), 1); i++ )
50
51 ////////////////////////////////////////////////////////////////////////
52 /// FUNCTION DEFINITIONS ///
53 ////////////////////////////////////////////////////////////////////////
54
55 /**Function*************************************************************
56
57 Synopsis [Create fanout for all objects in the manager.]
58
59 Description []
60
61 SideEffects []
62
63 SeeAlso []
64
65 ***********************************************************************/
Gia_ManFanoutStart(Gia_Man_t * p)66 void Gia_ManFanoutStart( Gia_Man_t * p )
67 {
68 Gia_Obj_t * pObj;
69 int i;
70 // allocate fanout datastructure
71 assert( p->pFanData == NULL );
72 p->nFansAlloc = 2 * Gia_ManObjNum(p);
73 if ( p->nFansAlloc < (1<<12) )
74 p->nFansAlloc = (1<<12);
75 p->pFanData = ABC_ALLOC( int, 5 * p->nFansAlloc );
76 memset( p->pFanData, 0, sizeof(int) * 5 * p->nFansAlloc );
77 // add fanouts for all objects
78 Gia_ManForEachObj( p, pObj, i )
79 {
80 if ( Gia_ObjChild0(pObj) )
81 Gia_ObjAddFanout( p, Gia_ObjFanin0(pObj), pObj );
82 if ( Gia_ObjChild1(pObj) )
83 Gia_ObjAddFanout( p, Gia_ObjFanin1(pObj), pObj );
84 }
85 }
86
87 /**Function*************************************************************
88
89 Synopsis [Deletes fanout for all objects in the manager.]
90
91 Description []
92
93 SideEffects []
94
95 SeeAlso []
96
97 ***********************************************************************/
Gia_ManFanoutStop(Gia_Man_t * p)98 void Gia_ManFanoutStop( Gia_Man_t * p )
99 {
100 assert( p->pFanData != NULL );
101 ABC_FREE( p->pFanData );
102 p->nFansAlloc = 0;
103 }
104
105 /**Function*************************************************************
106
107 Synopsis [Adds fanout (pFanout) of node (pObj).]
108
109 Description []
110
111 SideEffects []
112
113 SeeAlso []
114
115 ***********************************************************************/
Gia_ObjAddFanout(Gia_Man_t * p,Gia_Obj_t * pObj,Gia_Obj_t * pFanout)116 void Gia_ObjAddFanout( Gia_Man_t * p, Gia_Obj_t * pObj, Gia_Obj_t * pFanout )
117 {
118 int iFan, * pFirst, * pPrevC, * pNextC, * pPrev, * pNext;
119 assert( p->pFanData );
120 assert( !Gia_IsComplement(pObj) && !Gia_IsComplement(pFanout) );
121 assert( Gia_ObjId(p, pFanout) > 0 );
122 if ( Gia_ObjId(p, pObj) >= p->nFansAlloc || Gia_ObjId(p, pFanout) >= p->nFansAlloc )
123 {
124 int nFansAlloc = 2 * Abc_MaxInt( Gia_ObjId(p, pObj), Gia_ObjId(p, pFanout) );
125 p->pFanData = ABC_REALLOC( int, p->pFanData, 5 * nFansAlloc );
126 memset( p->pFanData + 5 * p->nFansAlloc, 0, sizeof(int) * 5 * (nFansAlloc - p->nFansAlloc) );
127 p->nFansAlloc = nFansAlloc;
128 }
129 assert( Gia_ObjId(p, pObj) < p->nFansAlloc && Gia_ObjId(p, pFanout) < p->nFansAlloc );
130 iFan = Gia_FanoutCreate( Gia_ObjId(p, pFanout), Gia_ObjWhatFanin(p, pFanout, pObj) );
131 pPrevC = Gia_FanoutPrev( p->pFanData, iFan );
132 pNextC = Gia_FanoutNext( p->pFanData, iFan );
133 pFirst = Gia_FanoutObj( p->pFanData, Gia_ObjId(p, pObj) );
134 if ( *pFirst == 0 )
135 {
136 *pFirst = iFan;
137 *pPrevC = iFan;
138 *pNextC = iFan;
139 }
140 else
141 {
142 pPrev = Gia_FanoutPrev( p->pFanData, *pFirst );
143 pNext = Gia_FanoutNext( p->pFanData, *pPrev );
144 assert( *pNext == *pFirst );
145 *pPrevC = *pPrev;
146 *pNextC = *pFirst;
147 *pPrev = iFan;
148 *pNext = iFan;
149 }
150 }
151
152 /**Function*************************************************************
153
154 Synopsis [Removes fanout (pFanout) of node (pObj).]
155
156 Description []
157
158 SideEffects []
159
160 SeeAlso []
161
162 ***********************************************************************/
Gia_ObjRemoveFanout(Gia_Man_t * p,Gia_Obj_t * pObj,Gia_Obj_t * pFanout)163 void Gia_ObjRemoveFanout( Gia_Man_t * p, Gia_Obj_t * pObj, Gia_Obj_t * pFanout )
164 {
165 int iFan, * pFirst, * pPrevC, * pNextC, * pPrev, * pNext;
166 assert( p->pFanData && Gia_ObjId(p, pObj) < p->nFansAlloc && Gia_ObjId(p, pFanout) < p->nFansAlloc );
167 assert( !Gia_IsComplement(pObj) && !Gia_IsComplement(pFanout) );
168 assert( Gia_ObjId(p, pFanout) > 0 );
169 iFan = Gia_FanoutCreate( Gia_ObjId(p, pFanout), Gia_ObjWhatFanin(p, pFanout, pObj) );
170 pPrevC = Gia_FanoutPrev( p->pFanData, iFan );
171 pNextC = Gia_FanoutNext( p->pFanData, iFan );
172 pPrev = Gia_FanoutPrev( p->pFanData, *pNextC );
173 pNext = Gia_FanoutNext( p->pFanData, *pPrevC );
174 assert( *pPrev == iFan );
175 assert( *pNext == iFan );
176 pFirst = Gia_FanoutObj( p->pFanData, Gia_ObjId(p, pObj) );
177 assert( *pFirst > 0 );
178 if ( *pFirst == iFan )
179 {
180 if ( *pNextC == iFan )
181 {
182 *pFirst = 0;
183 *pPrev = 0;
184 *pNext = 0;
185 *pPrevC = 0;
186 *pNextC = 0;
187 return;
188 }
189 *pFirst = *pNextC;
190 }
191 *pPrev = *pPrevC;
192 *pNext = *pNextC;
193 *pPrevC = 0;
194 *pNextC = 0;
195 }
196
197
198
199
200 /**Function*************************************************************
201
202 Synopsis [Compute the map of all edges.]
203
204 Description []
205
206 SideEffects []
207
208 SeeAlso []
209
210 ***********************************************************************/
Gia_ManStartFanoutMap(Gia_Man_t * p,Vec_Int_t * vFanoutNums)211 Vec_Int_t * Gia_ManStartFanoutMap( Gia_Man_t * p, Vec_Int_t * vFanoutNums )
212 {
213 Vec_Int_t * vEdgeMap;
214 Gia_Obj_t * pObj;
215 int i, iOffset;
216 iOffset = Gia_ManObjNum(p);
217 vEdgeMap = Vec_IntStart( iOffset + Gia_ManMuxNum(p) + 2 * Gia_ManAndNum(p) + Gia_ManCoNum(p) - Gia_ManBufNum(p) );
218 Gia_ManForEachObj( p, pObj, i )
219 {
220 Vec_IntWriteEntry( vEdgeMap, i, iOffset );
221 iOffset += Vec_IntEntry( vFanoutNums, Gia_ObjId(p, pObj) );
222 }
223 assert( iOffset <= Vec_IntSize(vEdgeMap) );
224 return vEdgeMap;
225 }
226
227 /**Function*************************************************************
228
229 Synopsis [Allocates static fanout.]
230
231 Description []
232
233 SideEffects []
234
235 SeeAlso []
236
237 ***********************************************************************/
Gia_ManStaticFanoutStart(Gia_Man_t * p)238 void Gia_ManStaticFanoutStart( Gia_Man_t * p )
239 {
240 Vec_Int_t * vCounts;
241 int * pRefsOld;
242 Gia_Obj_t * pObj, * pFanin;
243 int i, iFanout;
244 assert( p->vFanoutNums == NULL );
245 assert( p->vFanout == NULL );
246 // recompute reference counters
247 pRefsOld = p->pRefs; p->pRefs = NULL;
248 Gia_ManCreateRefs(p);
249 p->vFanoutNums = Vec_IntAllocArray( p->pRefs, Gia_ManObjNum(p) );
250 p->pRefs = pRefsOld;
251 // start the fanout maps
252 p->vFanout = Gia_ManStartFanoutMap( p, p->vFanoutNums );
253 // incrementally add fanouts
254 vCounts = Vec_IntStart( Gia_ManObjNum(p) );
255 Gia_ManForEachObj( p, pObj, i )
256 {
257 if ( Gia_ObjIsAnd(pObj) || Gia_ObjIsCo(pObj) )
258 {
259 pFanin = Gia_ObjFanin0(pObj);
260 iFanout = Vec_IntEntry( vCounts, Gia_ObjId(p, pFanin) );
261 Gia_ObjSetFanout( p, pFanin, iFanout, pObj );
262 Vec_IntAddToEntry( vCounts, Gia_ObjId(p, pFanin), 1 );
263 }
264 if ( Gia_ObjIsAnd(pObj) && !Gia_ObjIsBuf(pObj) )
265 {
266 pFanin = Gia_ObjFanin1(pObj);
267 iFanout = Vec_IntEntry( vCounts, Gia_ObjId(p, pFanin) );
268 Gia_ObjSetFanout( p, pFanin, iFanout, pObj );
269 Vec_IntAddToEntry( vCounts, Gia_ObjId(p, pFanin), 1 );
270 }
271 if ( Gia_ObjIsMux(p, pObj) )
272 {
273
274 pFanin = Gia_ObjFanin2(p, pObj);
275 iFanout = Vec_IntEntry( vCounts, Gia_ObjId(p, pFanin) );
276 Gia_ObjSetFanout( p, pFanin, iFanout, pObj );
277 Vec_IntAddToEntry( vCounts, Gia_ObjId(p, pFanin), 1 );
278 }
279 }
280 // double-check the current number of fanouts added
281 Gia_ManForEachObj( p, pObj, i )
282 assert( Vec_IntEntry(vCounts, i) == Gia_ObjFanoutNum(p, pObj) );
283 Vec_IntFree( vCounts );
284 }
285
286 /**Function*************************************************************
287
288 Synopsis [Deallocates static fanout.]
289
290 Description []
291
292 SideEffects []
293
294 SeeAlso []
295
296 ***********************************************************************/
Gia_ManStaticFanoutStop(Gia_Man_t * p)297 void Gia_ManStaticFanoutStop( Gia_Man_t * p )
298 {
299 Vec_IntFreeP( &p->vFanoutNums );
300 Vec_IntFreeP( &p->vFanout );
301 }
302
303
304 /**Function*************************************************************
305
306 Synopsis [Tests static fanout.]
307
308 Description []
309
310 SideEffects []
311
312 SeeAlso []
313
314 ***********************************************************************/
Gia_ManStaticFanoutTest(Gia_Man_t * p)315 void Gia_ManStaticFanoutTest( Gia_Man_t * p )
316 {
317 Gia_Obj_t * pObj, * pFanout;
318 int i, k;
319 Gia_ManStaticFanoutStart( p );
320 Gia_ManForEachObj( p, pObj, i )
321 {
322 Gia_ObjPrint( p, pObj );
323 printf( " Fanouts : " );
324 Gia_ObjForEachFanoutStatic( p, pObj, pFanout, k )
325 printf( "%5d ", Gia_ObjId(p, pFanout) );
326 printf( "\n" );
327 }
328 Gia_ManStaticFanoutStop( p );
329 }
330
331 ////////////////////////////////////////////////////////////////////////
332 /// END OF FILE ///
333 ////////////////////////////////////////////////////////////////////////
334
335
336 ABC_NAMESPACE_IMPL_END
337
338